数据结构之哈夫曼树

一些基本概念

树的带权路径长度只与叶子节点的路径长度的权值有关！！！
带权路径长=路径长×权值

给定n个叶子节点
让我们构造二叉树，其中带权路径长度最小的二叉树叫哈夫曼树

对应每一个给定权值的n个叶子节点（比如图中四个叶子节点分别为1 3 4 5）都有一个最小的带权路径长度
1 3 4 5的最小就是25
所以中间的两个图就是哈夫曼树

构造哈夫曼树

给定你固定的叶子节点
怎么构造？
1.挑出对应权值最小的两个节点构成一棵树
2.然后吧这棵树的权值算为对应叶子节点权值之和，把这棵树当做一个节点
3.再找权值最小的组合就完了
4.最后组合成的二叉树就是哈夫曼树

由上面的推导可以得出一些哈夫曼树的性质

哈夫曼编码

二进制长度=带权路径长度

但是右边这颗树显然不是哈夫曼树
可以用更少的动作传播信息
这棵树显然要动200次奥

把右边这棵树化成哈夫曼树

ok然后把对应编码写出来就ok
这样的话只需要动130次奥

错误奥

你可能想把A化成1更简单
但是编码可能是有重复的奥
比如你想发送CAAABD
按照A为1的话
01111111110
可能翻译成CBBD
而不是原来的了
所以一定要按照哈夫曼树，对应节点一定要是叶子节点不能是分支节点

总结