Nginx配置 wordpress Quartz MongoDB gps canvas razor mvvm arduino controller insert 手机banner常用尺寸 docker的安全特性有哪些 html好看的字体 bootstrap滚动条 小程序下拉刷新样式 python网络编程 python多线程编程 python程序实例 python程序代码 java简介 java连接mysql java日期 java文件流 java链接mysql数据库 java对象序列化 linuxsleep java游戏制作 java项目下载 战地2单机地图 alphacam gilisoft 视频字幕提取器 免费脚本 京东钱包客户端 苹果手机总是自动重启 appsync补丁 lol无限视野 小米手环怎么连接手机 苹果手机怎么滚动截屏
当前位置: 首页 > 学习教程  > 编程语言

赫夫曼树

2020/8/31 14:49:44 文章标签:

赫夫曼树

赫夫曼树是带权路径长度(WPL)最小的树,,这样的树称为最优二叉树,也称为赫夫曼树。
路径和路径长度:
在一棵树中,从一个节点往下可以达到的孩子或孙子节点之间的通路称为路径,通路之间的分支的数目称为路径长度,从根节点到第L层的路径长度通常为L-1
结点的权及带权路径长度:
给结点赋一个某种原因的值,这个值称为结点的权,权*路径程度=带权路径长度
树的带权路径长度:
所有的叶子结点的带权路径长度之和为树的带权路径长度,权值最大的结点离根节点最近的二叉树是最优二叉树
wpl最小的树就是赫夫曼树
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述
在这里插入图片描述

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

public class huffmanTree {

	public static void main(String[] args) {
		// TODO 自动生成的方法存根
		int arr[]= {1, 5 ,9 ,3, 15, 13};
		creatHuffmanTree(arr);
	}
	
	//创建赫夫曼树
	// 为每一个元素形成Node 放入 list
	public static Node creatHuffmanTree(int arr[]) {
		List<Node> nodes=new ArrayList<Node>();
		for( int value:arr) {
			nodes.add(new Node(value));
		}	
		
		while(nodes.size()>1) {
		//排序
		Collections.sort(nodes);
		
		//System.out.println(nodes);
		
		//取出根节点权值最小的两颗二叉树
		Node left =nodes.get(0);
		//取出次小的二叉树
		Node right=nodes.get(1);
		//构建一个新的二叉树
		Node parent=new Node(left.value+right.value);
		parent.left=left;
		parent.right=right;
		
		//从List中删除处理过的二叉树
		nodes.remove(left);
		nodes.remove(right);
		nodes.add(parent);
		
		//Collections.sort(nodes);
		
		System.out.println(nodes); //调用 ToString
		}
		return nodes.get(0);
	}

}

//创建结点类
// Node comparable 接口 实现Node 排序
class Node implements Comparable<Node>{
	int value;
	Node left;
	Node right;
	
	public Node(int value) {
		this.value=value;
	}
	
	public String toString() {
		return "value="+value+"";
	}

	@Override
	public int compareTo(Node o) {
		// TODO 自动生成的方法存根
		return this.value-o.value;
	}
}
[value=5, value=9, value=13, value=15, value=4]
[value=9, value=13, value=15, value=9]
[value=13, value=15, value=18]
[value=18, value=28]
[value=46]


本文链接: http://www.dtmao.cc/news_show_150291.shtml

附件下载

相关教程

    暂无相关的数据...

共有条评论 网友评论

验证码: 看不清楚?