哈夫曼树，类似于算法中的二叉树，说白了哈夫曼树就是一种二叉树，只是是一种最优二叉树。我们准备一组数以 1，7，3，4，9，8为例子吧
第一步，我们对这一组数字进行排序。规则是从小到大排列。排列之后的顺序是 1，3，4，7，8，9
第一步，我们对这一组数字进行排序。规则是从小到大排列。排列之后的顺序是 1，3，4，7，8，9
第一步，我们对这一组数字进行排序。规则是从小到大排列。排列之后的顺序是 1，3，4，7，8，9
如果两个数的和正好是下一步的两个最小数的其中的一个那么这个树直接往上生长就可以了。如果这两个数的和比较大不是下一步的两个最小数的其中一个那么，就并列生长
类似于步骤四。我们继续用倒V型的树杈，向上延伸。
算出来最后一个结果 就证明我们的哈夫曼树构建成功了。
image.png
| nX2-1=6X2-1=11 | parent | lchild | rchild | |
|---|---|---|---|---|
| 1 | 1 | 7 | 0 | 0 |
| 2 | 7 | 9 | 0 | 0 |
| 3 | 3 | 7 | 0 | 0 |
| 4 | 4 | 8 | 0 | 0 |
| 5 | 9 | 10 | 0 | 0 |
| 6 | 8 | 9 | 0 | 0 |
| 7 | 4 | 8 | 1 | 3 |
| 8 | 8 | 10 | 4 | 7 |
| 9 | 15 | 11 | 2 | 6 |
| 10 | 17 | 11 | 5 | 8 |
| 11 | 32 | 0 | 9 | 10 |
网友评论