数据结构09|数据结构09 哈夫曼树数据结构09哈夫曼树

作者：nnngu
GitHub：https://github.com/nnngu
博客园：http://www.cnblogs.com/nnngu
：https://www.jianshu.com/users/1df20d76ea5c
知乎：https://www.zhihu.com/people/nnngu/posts
这一篇要总结的是树中的哈夫曼树(Huffman Tree)，我想从以下几点对其进行总结：
1、什么是哈夫曼树
2、如何构建哈夫曼树
3、哈夫曼编码
4、代码实现
1、什么是哈夫曼树什么是哈夫曼树呢？
哈夫曼树是一种带权路径长度最短的二叉树，也称为最优二叉树。下面用一幅图来说明。

文章图片
【数据结构09|数据结构09 哈夫曼树】它们的带权路径长度分别为：
图a： WPL=5*2+7*2+2*2+13*2=54
图b： WPL=5*3+2*3+7*2+13*1=48
可见，图b的带权路径长度较小，我们可以证明图b就是哈夫曼树(也称为最优二叉树)。
2、如何构建哈夫曼树一般可以按下面步骤构建：
（1）将所有左，右子树都为空的节点作为根节点。
（2）在森林中选出两棵根节点的权值最小的树作为一棵新树的左，右子树，且置新树的根节点的权值为其左，右子树上根节点的权值之和。注意，左子树的权值应小于右子树的权值。
（3）从森林中删除这两棵树，同时把新树加入到森林中。
（4）重复2、3步骤，直到森林中只有一棵树为止，此树便是哈夫曼树。
下面是构建哈夫曼树的图解过程：

文章图片
3、哈夫曼编码利用哈夫曼树求得的用于通信的二进制编码称为哈夫曼编码。树中从根到每个叶子节点都有一条路径，对路径上的各分支约定指向左子树的分支表示”0”码，指向右子树的分支表示“1”码，取每条路径上的“0”或“1”的序列作为各个叶子节点对应的字符编码，即是哈夫曼编码。
就拿上图例子来说：
A，B，C，D对应的哈夫曼编码分别为：111，10，110，0
用图说明如下：

文章图片
4、代码实现代码：
节点类 Node.java

/** * 节点类 */ public class Node implements Comparable { private int value; private Node leftChild; private Node rightChild; public Node(int value) { this.value = https://www.it610.com/article/value; }public int getValue() { return value; }public void setValue(int value) { this.value = value; }public Node getLeftChild() { return leftChild; }public void setLeftChild(Node leftChild) { this.leftChild = leftChild; }public Node getRightChild() { return rightChild; }public void setRightChild(Node rightChild) { this.rightChild = rightChild; }public int compareTo(Object o) { Node that = (Node) o; double result = that.value - that.value; return result> 0 ? 1 : result == 0 ? 0 : -1; } }

HuffmanTreeBuilder.java

import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; /** * 哈夫曼树构造类 */ public class HuffmanTreeBuilder { public static void main(String[] args) { List nodes = Arrays.asList( new Node(1), new Node(3), new Node(5), new Node(7) ); Node node = HuffmanTreeBuilder.build(nodes); printTree(node); }/** * 构造哈夫曼树 * * @param nodes 节点集合 * @return 构造出来的树的根节点 */ private static Node build(List nodes) { nodes = new ArrayList(nodes); sortList(nodes); while (nodes.size() > 1) { createAndReplace(nodes); } return nodes.get(0); }/** * 组合两个权值最小节点，并在节点列表中用它们的父节点替换它们 * * @param nodes 节点集合 */ private static void createAndReplace(List nodes) { Node left = nodes.get(0); Node right = nodes.get(1); Node parent = new Node(left.getValue() + right.getValue()); parent.setLeftChild(left); parent.setRightChild(right); nodes.remove(0); nodes.remove(0); nodes.add(parent); sortList(nodes); }/** * 将节点集合由小到大排序 * * @param nodes */ private static void sortList(List nodes) { Collections.sort(nodes); }/** * 打印树结构，显示的格式是node(left,right) * * @param node */ public static void printTree(Node node) { Node left = null; Node right = null; if (node != null) { System.out.print(node.getValue()); left = node.getLeftChild(); right = node.getRightChild(); System.out.println("(" + (left != null ? left.getValue() : " ") + "," + (right != null ? right.getValue() : " ") + ")"); } if (left != null) { printTree(left); } if (right != null) { printTree(right); } } }

运行结果：