百度百科定义
给定n个权值作为n个叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman Tree)。哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。
image.png
哈夫曼树数据结构
- 左子树
- 右子树
- 父节点
- 权重
- 数据
public static class TreeNode<T> implements Comparable<TreeNode<T>>{
T data;
int weight;
TreeNode leftChild;
TreeNode rightChild;
TreeNode parent;
public TreeNode(T data, int wei) {
this.data = data;
this.weight = wei;
leftChild = null;
rightChild = null;
parent = null;
}
@Override
public int compareTo(TreeNode<T> o) {
if (this.weight > o.weight) {
return -1;
} else if (this.weight < o.weight) {
return 1;
}
return 0;
}
}
哈夫曼树构建
假设有n个权值，则构造出的哈夫曼树有n个叶子结点。 n个权值分别设为 w1、w2、…、wn，则哈夫曼树的构造规则为：
- (1) 将w1、w2、…，wn看成是有n 棵树的森林(每棵树仅有一个结点)；
- (2) 在森林中选出两个根结点的权值最小的树合并，作为一棵新树的左、右子树，且新树的根结点权值为其左、右子树根结点权值之和；
- (3 )从森林中删除选取的两棵树，并将新树加入森林；
- (4) 重复(2)、(3)步，直到森林中只剩一棵树为止，该树即为所求得的哈夫曼树。
举个例子
有这样权值数组 {13,6,8,19,2,36,5,25 }
- 1 排序
{2,5,6,8,13,19,25,36} -
2 在这些数中 选择两个最小的权值，作为一棵新树node的左右节点（小的在做，大的在右），node的权值为其左、右子树根结点权值之和
步骤1.png - 3 把新节点node的权值加入数组，重新排序
{7,6,8,13,19,25,36}
重复步骤2
步骤2.png
-
4 重复步骤3
排序后的权值数组 {8,13,13,19,25,36}
image.png
排序后的权值数组{13,19,21,25,36}
image.png
排序后的权值数组{21,25,32,36}
image.png
排序后的权值数组 {32,36,46}
image.png
排序后的权值数组{46,68}
image.png
排序后的权值数组{114}
public TreeNode createHaffManTree(ArrayList<TreeNode> list) {
while (list.size() > 1) {
Collections.sort(list);
TreeNode left = list.get(list.size()-1);
TreeNode right = list.get(list.size()-2);
TreeNode parent = new TreeNode("p", left.weight + right.weight);
parent.leftChild = left;
left.parent = parent;
parent.rightChild = right;
right.parent = parent;
list.remove(left);
list.remove(right);
list.add(parent);
}
root = list.get(0);
return list.get(0);
}
哈夫曼树遍历
层次遍历 ：使用队列实现层次遍历
我们遍历这棵树
image.png
步骤
- 1 把根节点加入到队列]
list.offer(root);
队列{114}
- 2 队列list不为空，弹出队头，输出
TreeNode node = list.pop();
System.out.println(node.data);
- 3 读取队头node 的左孩子，和右孩子，如果孩子不为空，孩子加入队列
if (node.leftChild != null) {
list.offer(node.leftChild);
}
if (node.rightChild != null) {
list.offer(node.rightChild);
}
- 现在队列的数据{46,68}
- 弹出46 ，队尾加入46的左孩子，右孩子，队列现在的数据{68,21,25}
- 弹出68 ，队尾加入68的左孩子，右孩子，队列现在的数据{21,25,32,36}
- 弹出21 ，队尾加入21的左孩子，右孩子，队列现在的数据{25,32,36,8,13}
- 弹出25 ，队尾加入25的左孩子，右孩子，25没有左右孩子，队列现在的数据{32,36,8,13}
- 弹出32 ，队尾加入32的左孩子，右孩子，队列现在的数据{36,8,13,13,19}
- 弹出36 ，队尾加入32的左孩子，右孩子，36没有左右孩子,队列现在的数据{8,13,13,19}
- 弹出8 ，队尾加入8的左孩子，右孩子, 没有左右孩子，队列现在的数据{13,13,19}
- 弹出13 ，队尾加入13的左孩子，右孩子，队列现在的数据{13,19,6,7}
- 弹出13 ，队尾加入13的左孩子，右孩子，队列现在的数据{19,6,7}
- 弹出19 ，队尾加入19的左孩子，右孩子，队列现在的数据{6,7}
- 弹出6，队尾加入6的左孩子，右孩子，队列现在的数据{7}
- 弹出7，队尾加入7的左孩子，右孩子，队列现在的数据{2,5}
- 弹出2，队尾加入2的左孩子，右孩子，队列现在的数据{5}
- 弹出5，队尾加入5的左孩子，右孩子，队列现在的数据{}
- 队列为空，遍历结束
image.png
public void showHaffman(TreeNode root) {
LinkedList<TreeNode> list = new LinkedList<>();
ArrayList<TreeNode> arrayList = new ArrayList<>();
list.offer(root);
while (!list.isEmpty()) {
TreeNode node = list.pop();
System.out.println(node.data);
if (node.leftChild != null) {
list.offer(node.leftChild);
}
if (node.rightChild != null) {
list.offer(node.rightChild);
}
}
}
获取哈夫曼编码
image.png
- 8 的哈夫曼编码：000
- 6 的哈夫曼编码：0010
- 2 的哈夫曼编码：00110
- 5 的哈夫曼编码：00111
- 25 的哈夫曼编码：01
- 13 的哈夫曼编码：100
- 19 的哈夫曼编码：101
- 19 的哈夫曼编码：11
image.png
public void getCode(TreeNode node) {
Stack<String> stack = new Stack<>();
TreeNode tNode = node;
while (tNode != null && tNode.parent != null) {
// left 0, right 1
if (tNode.parent.leftChild == tNode) {
stack.push("0");
} else if (tNode.parent.rightChild == tNode) {
stack.push("1");
}
tNode = tNode.parent;
}
while (!stack.isEmpty()) {
System.out.print(stack.pop());
}
}
测试
public static void main(String[] args) {
ArrayList<TreeNode> list = new ArrayList<>();
TreeNode<String> node = new TreeNode("good", 54);
list.add(node);
list.add(new TreeNode("morning", 10));
list.add(new TreeNode("afternoon", 20));
list.add(new TreeNode("hello", 100));
list.add(new TreeNode("hi", 200));
HaffmanTree tree = new HaffmanTree();
tree.createHaffManTree(list);
tree.showHaffman(tree.root);
tree.getCode(node);
}
