|
1. 基本介绍：  二叉树路径：从一个节点到达其后辈节点的通路，称为路径。通路中分支的数目称为路径长度。上面这棵二叉树，黄色的线就是50这个节点到15这个节点的路径，路径长度为3。树有n层，那么根节点到第n层节点的路径长度为(n-1)。 带权路径长度：就是路径长度乘以该节点的值。比如50到15的带权路径长度就是 3 * 15 = 45。 树的带权路径长度：所有叶子结点的带权路径长度之和，记作wpl。 赫夫曼树：树的带权路径长度最小的的树称为最优二叉树，也称为赫夫曼树。也就说，**wpl最小的树就叫做赫夫曼树。**从树的带权路径长度的定义可以知道，要想该值最小，离根节点越近的值应该越大，才能使带权路径长度最小。
给定13, 7, 8, 3这四个数作为叶子结点，构建成二叉树，部分情况如下：  二叉树这种情况，权值为 2 * 13 + 2 * 7 + 2 * 8 + 2 * 3 = 62。  二叉树这种情况，权值为1 * 13 + 2 * 8 + 3 * 7 + 3 * 3 = 59。 显然第二种情况权值更小，确保没有更小的情况下，这棵二叉树就叫做赫夫曼树。 2. 构建赫夫曼树： 假如现在要将13, 7, 8, 3, 29, 6, 1构建成赫夫曼树，步骤如下： 首先将数组升序排序；结果就是1, 3, 6, 7, 8,13, 29。 取出排序后的前两个数，构建成一棵二叉树，根节点为两个子节点之和；即取出1和3，构建出如下二叉树：
 第一步此时数组中的1和3就已经用掉了，将上一步构建的二叉树的根节点4放入数组中排序，结果就是：4, 6, 7, 8, 13, 29。 再从序列中取出两个数，即4和6，构建成一棵二叉树，如下图：
 第二步再将10放到序列中，此时的序列就是这样的：7, 8, 10, 13, 29。
 第三步将15放到序列中，此时序列就变成了：10, 13, 15, 29，并且此时构建出了两棵二叉树，还没关联起来，先不用急。 取出10和13，构建成二叉树，此时二叉树就变成了：
 第四步将23放到序列中，序列就变成了：15, 23, 29。 取出15和23，构建成二叉树，15和23是两棵树的根节点，经过这一步，两棵树就合并了：
 第五步- 现在序列中就剩下
29和38了，所以将29加到这棵树上就好了，如下图：
 第六步- 经过上面的步骤，就将给定的这个序列构建成了赫夫曼树。
3. 代码实现： /**
* 赫夫曼树
* @author zhu
*
*/
public class HuffmanTree {
/**
* 构建赫夫曼树
* @param arr
* @return
*/
public static Node buildHufmanTree(int[] arr) {
// 将数组转成集合，方便增删元素
List<Node> nodes = new ArrayList<>();
for (int i=0; i<arr.length; i++) {
nodes.add(new Node(arr[i]));
}
// 对集合进行排序
Collections.sort(nodes);
// 循环构建
while (nodes.size() > 1) {
// 取出前两个节点，构建二叉树
Node leftNode = nodes.get(0);
Node rightNode = nodes.get(1);
Node parentNode = new Node(leftNode.getValue() + rightNode.getValue());
parentNode.setLeft(leftNode);
parentNode.setRight(rightNode);
// 移除用掉了的元素，将parent的值添加进集合
nodes.remove(leftNode);
nodes.remove(rightNode);
nodes.add(parentNode);
// 重新排序
Collections.sort(nodes);
}
// 返回赫夫曼树的根节点
return nodes.get(0);
}
/**
* 前序遍历
*
* @param root
*/
public static void preOrder(Node root) {
// 先输出当前节点
System.out.println(root.getValue());
// 判断左子节点是否为空，不为空就递归
if (root.getLeft() != null) {
preOrder(root.getLeft());
}
// 判断右子节点是否为空，不为空就递归
if (root.getRight() != null) {
preOrder(root.getRight());
}
}
/**
* 节点内部类，实现compareble接口，方便对node排序
* @author zhu
*
*/
static class Node implements Comparable<Node>{
private int value;
private Node left;
private Node right;
public Node(int val) {
this.value = val;
}
public int getValue() {
return value;
}
public void setValue(int value) {
this.value = value;
}
public Node getLeft() {
return left;
}
public void setLeft(Node left) {
this.left = left;
}
public Node getRight() {
return right;
}
public void setRight(Node right) {
this.right = right;
}
@Override
public String toString() {
return "Node [value=" + value + "]";
}
@Override
public int compareTo(Node o) {
// 升序
return this.value - o.value;
}
}
public static void main(String[] args) {
int[] arr = {13, 7, 8, 3, 29, 6, 1};
Node node = buildHufmanTree(arr);
preOrder(node);
}
}
上面是创建赫夫曼树的完整代码，构件好之后，用前序遍历方法遍历一下，然后看看与上面图中的赫夫曼树前序遍历结果是否一致，如果一致，表示构建成功。
|
