赫夫曼树
赫夫曼树介绍：
赫夫曼树是有n个叶子节点并且这些叶子节点都有 【权值】，若一颗二叉树的带权路径长度【wpl】最小，那这棵树称为最优二叉树，又叫赫夫曼树
带权路径长度【wpl】介绍
首先要知道路径与路径长度
- 路径：从某个节点开始往下可达到某个节点的之间的路线就是【路径】
- 路径长度：指的是从某个节点到达某个节点中间所经过的所有节点为【路径长度】 若：某个节点层数为1，从这个节点到达第L层节点的路径长度称为L-1
-
节点的权值&带权路径长度：在树中的某个节点被赋予一个含有某种意义的值，则这个数值称为该节点的【权值】。而节点的【带权路径长度】为：从根节点到该节点的【路径长度】乘上该节点的【权值】。
如图：
- 里面的某个叶子节为13，而它距离根节点的路径长度有2层，所以这个节点的【带权路径长度】为13*2=26。
- 而该整个二叉树的【带权路径长度】为所有叶子节点的【带权路径长度】之和 即 132 + 72 + 82 + 32 = 62
- 而经过尝试性计算该二叉树的【带权路径长度】最短为最优二叉树及【赫夫曼树】
构建【赫夫曼树】
-
如指定一个数列来构建赫夫曼树，数列的每一个数据可看做一个最简单的二叉树或节点
-
构建赫夫曼树首先要让数列升序排序 如：如：【13，7，8，3，29，6，1】排序后 ：【1，3，6，7，8，13，29】
-
然后取出根节点最小的两个节点，这两个节点的权值相加得到一个新的权值作为根节点，而相加的节点为两边子节点，构成一颗新的二叉树
-
该新的二叉树的根节点又依次与数列后面数据的权值相加，得出新的根节点，两边路径链接上相加的两个节点成为新的二叉树
-
再以这颗二叉树的根节点的权值大小进行排序，并重复以上步骤，直到把数列里的全部数据构建完，成为二叉树为止。
代码编写
构建赫夫曼树节点类 & 包含前序遍历方法
//为了让Node 对象支持排序集合排序，让Node 实现自定义名为Comparable接口
public class Node implements Comparable<Node> {
int value; // 节点权值
Node left; // 左子节点
Node right; // 右子节点
public Node(int value) {
this.value = value;
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
@Override
public int compareTo(Node o) {
// TODO Auto-generated method stub
// 此方法表示顺序排序，-(this.value - o.value):为降序排序
return this.value - o.value;
}
//前序遍历
public void preOrder() {
System.out.println(this);
if(this.left != null) {
this.left.preOrder();
}
if(this.right != null) {
this.right.preOrder();
}
}
}
构建赫夫曼树核心代码 & 调用创建节点类里的前序遍历方法
一，首先我们需要把数列里的每一个数构建成节点（Node）,并把该节点放进ArrayList中方便管理
1.遍历arr数组
1.2将arr的每一个元素构成一个节点（Node）
1.3再放入到ArrayList中,其中在add 添加时将数据new成Node节点： nodes.add(new Node(value));
二，然后使用Cllections.sort() 方法将集合放进去进行升序排序
三，定义节点变量leftNode与rightNode保存集合中的最小值和次小值，也就是排序后集合的第0个与第1个节点
3.2并创建 new出根节点parent，权值为leftNode与rightNode权值相加:
Node parent = new Node(leftNode.value + rightNode.value)
3.3并且根节点左右路径链接上leftNode与rightNode
3.4然后使用集合中的方法，从集合中去除掉处理过的节点，并加入相加出来的根节点parent到集合中
四，以上环节只是赫夫曼树构建一次的核心代码，要完成数列所有节点的构建需要最外层套上一层循环，
因为数列里的节点一直相加 去除 新增 到最后只剩下最后的一个节点，就是根节点，所以使用while
循环的条件为：当集合的长度大于1时循环
五，返回集合唯一一个节点即头节点 return nodes.get(0)
public static Node createHuffmanTree(int[] arr) {
// 一，
ArrayList<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 =" + nodes);
// 三，
Node leftNode = nodes.get(0);
Node rightNode = nodes.get(1);
Node parent = new Node(leftNode.value + rightNode.value);
parent.left = leftNode;
parent.right = rightNode;
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parent);
}
// 五，
return nodes.get(0);
}
// 调用前序遍历
public static void preOrder(Node root) {
if(root == null) {
System.out.println("树空");
}
root.preOrder();
}