前几篇文章咱们学习二叉树、程序二叉树、线索化二叉树、堆，接下来咱们持续学习有对于树的下一个利用构造：哈夫曼树
一、什么是哈夫曼树
根本介绍
1. 给定 n 个权值 作为 n 个叶子结点，结构一棵 二叉树 ，若该树的 带权门路长度 1(wpl)达到最小 ，称这样的二叉树为 最优叉树 。也称为 哈夫曼树 (HuffmanTree)，还有的书翻译为 霍夫曼树。
wpl：weight pathI ength
2. 哈夫曼树是 带权门路长度最短的树，权值较大的结点离根较近。
问题剖析
那么这时就有新的问题呈现！须要咱们解决了
1. 什么是门路呢？门路长度是什么？
2. 什么是权和带权门路长度是什么？
3. 带权门路长度最短的树，那么树的带权门路长度是什么？
什么是门路和门路长度？
在一棵树中，从 一个结点 往下能够达到的 孩子或孙子结点 之间的通路，称为 门路。
通路中分支的 数目 称为 门路长度 。若规定 根结点 的层数为 1，则 从根结点到第 L 层结点 的门路长度为L-1。
什么是结点的权和带权门路长度？
若将树中结点赋给一个 有着某种含意的数值 ，则 这个数值 称为该结点的 权。
结点的带权门路长度为：从根结点到 该结点之间的门路长度 与该结点的权的乘积。
什么是树的带权门路长度？
树的带权门路长度规定为：所有叶子结点 的带权门路长度之和 ，记为WPL(weighted path length)， 权值越大的结点离根结点越近的二叉树才是最优二叉树。
通过不同的 WPL 意识哈弗曼树
若该树的 带权门路长度 1(wpl)达到最小 ，称这样的二叉树为 最优叉树 。也称为 哈夫曼树(HuffmanTree)
哈夫曼树是 带权门路长度最短的树，权值较大的结点离根较近
如上图所示咱们发现 两头的树 其实就是 哈夫曼树 (HuffmanTree)，并且满足 权值较大的结点离根较近
权值越大的叶子节点越凑近根节点，权值越小的叶子节点越远离根节点。
二、通过示例意识哈夫曼树
将一个权重数列 {13, 7, 8,3,29,6,1}，求 转成一颗赫夫曼树.
思路图解剖析
1. 将数列{13, 7, 8, 3, 29, 6, 1}，进行从小到大排序
2. 新数列的每个数看成最简略根节点的二叉树
3. 取出权值最小的两颗二叉树组成新的二叉树，为两最小的树之和
4. 将新二叉树以跟节点的权重值再次从小到大排序，一直反复步骤
咱们发现 每次都须要依据节点权重值进行大小排序 ，那么咱们能不能使得 对象节点自身就具备比拟 的性能呢？
答案是有的：咱们的自定义对象 Node 实现 Comparable 接口
同时当咱们发现排序后，数列的前两个就是最小的权值。
那么依据图所示咱们来上节点的代码把
// 创立节点类
// 为了让 Node 对象继续排序 Conllections 汇合排序
// 让 Node 实现 Comparable 接口
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) {
// 示意从小到大进行排序
// 从大到小进行排序 - (this.value - o.value)；return this.value - o.value;
}
}外围代码剖析
public static void createHuffmanTree(int[] arr ){
/**
* 操作思路
* 1. 遍历 arr 数组
* 2. 将 arr 数组里的元素形成 Node 节点
* 3. 将 Node 放入 ArrayList 中
* 4. 进行从小到大排序
*/
List<Node> nodes = new ArrayList<Node>();
for (int itme:arr) {nodes.add(new Node(itme));
}
// 进行排序，ArrayList 里的 sort 排序 Node 须要实现 Comparable 接口
Collections.sort(nodes);
System.out.println(nodes);
}咱们先来测试看看第一步：将数列形成节点并进行从小到大排序
public static void main(String[] args) {int arr[] = {13,7,8,3,29,6,1};
createHuffmanTree(arr);
}
运行后果如下：[Node[value=1], Node[value=3], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]
如上所示，第一步看来还是胜利了的，那么接下来进行第二步
进行第二步：取出权值最小的两颗二叉树组成新的二叉树，为两最小的树之和
public static void createHuffmanTree(int[] arr ){
// 省略第一步：将数列形成节点并进行从小到大排序代码
/**
* 操作思路
* 1. 取出两个权值最小的节点二叉树
* 2. 依据两个权值最小的二叉树构建成一个新的二叉树
* 3. 删除原先两个权值最小的节点二叉树
* 4. 将新的二叉树放入队列，并构建新的队列
* 5. 新的队列进行从小到大排序 */
// 取出第一个权值最小的二叉树
Node leftNode = nodes.get(0);
// 取出第二个权值最小的二叉树
Node rightNode = nodes.get(1);
// 依据两个权值最小的二叉树构建成一个新的二叉树 同时构建连贯
Node parentNode = new Node(leftNode.value + rightNode.value);
parentNode.left = leftNode;
parentNode.right = rightNode;
// 删除原先两个权值最小的节点二叉树
nodes.remove(leftNode);
nodes.remove(rightNode);
// 将新的二叉树放入队列，并构建新的队列
nodes.add(parentNode);
Collections.sort(nodes);
System.out.println("第一次解决后："+nodes);
}
运行后果如下：[Node[value=1], Node[value=3], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]
第一次解决后：[Node[value=4], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]
细节法则小结
1. 新的二叉树增加后、就会删除原两个权值最小的二叉树
2. 解决完后须要从新排序从小到大
3. 如思路剖析图所示反复步骤操作后队列里只剩下一个节点
整合外围代码
public static Node createHuffmanTree(int[] arr ){
/**
* 操作思路
* 1. 遍历 arr 数组
* 2. 将 arr 数组里的元素形成 Node 节点
* 3. 将 Node 放入 ArrayList 中
* 4. 进行从小到大排序
*/
List<Node> nodes = new ArrayList<Node>();
for (int itme:arr) {nodes.add(new Node(itme));
}
while(nodes.size() >1){
// 进行排序从小到大
Collections.sort(nodes);
System.out.println(nodes);
/**
* 操作思路
* 1. 取出两个权值最小的节点二叉
* 2. 依据两个权值最小的二叉树构建成一个新的二叉树
* 3. 删除原先两个权值最小的节点二叉树
* 4. 将新的二叉树放入队列，并构建新的队列
* 5. 新的队列进行从小到大排序
*/
// 取出第一个权值最小的二叉树
Node leftNode = nodes.get(0);
// 取出第二个权值最小的二叉树
Node rightNode = nodes.get(1);
// 依据两个权值最小的二叉树构建成一个新的二叉树 同时构建连贯
Node parentNode = new Node(leftNode.value + rightNode.value);
parentNode.left = leftNode;
parentNode.right = rightNode;
// 删除原先两个权值最小的节点二叉树
nodes.remove(leftNode);
nodes.remove(rightNode);
// 将新的二叉树放入队列，并构建新的队列
nodes.add(parentNode);
}
// 因为队列只剩下最初一个节点所以间接返回即可
return nodes.get(0);
}接下来让咱们验证一下是否如图所示胜利绘制成哈夫曼树
应用前序遍历打印留在队列的 root 节点，还记得前序遍历吗？
前序遍历特点：前序是先输入父节点，再遍历左子树和右子树
class Node implements Comparable<Node>{
// 省略 Node 逻辑代码
// 增加前序遍历代码
public void preOrder(){System.out.println(this);
if(this.left!=null){this.left.preOrder();
}
if(this.right!=null){this.right.preOrder();
}
}
}// 增加根节点遍历办法
public static void preOrder(Node root){if(root!=null){root.preOrder();
}else{System.out.println("该哈弗曼树为空！无奈遍历");
}
}咱们的数列{13, 7, 8,3,29,6,1}，组装成哈弗曼树后的前序遍历，思考一下是什么呢？
public static void main(String[] args) {int arr[] = {13,7,8,3,29,6,1};
Node root = createHuffmanTree(arr);
preOrder(root);
}
运行后果如下：[Node[value=1], Node[value=3], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]
[Node[value=4], Node[value=6], Node[value=7], Node[value=8], Node[value=13], Node[value=29]]
[Node[value=7], Node[value=8], Node[value=10], Node[value=13], Node[value=29]]
[Node[value=10], Node[value=13], Node[value=15], Node[value=29]]
[Node[value=15], Node[value=23], Node[value=29]]
[Node[value=29], Node[value=38]]
Node[value=67]
Node[value=29]
Node[value=38]
Node[value=15]
Node[value=7]
Node[value=8]
Node[value=23]
Node[value=10]
Node[value=4]
Node[value=1]
Node[value=3]
Node[value=6]
Node[value=13]