数据结构有关于最优二叉树——最优哈夫曼树的建立过程和哈夫曼编码

  好,现在就来复习一下哈夫曼树的建立过程和哈夫曼编码怎么看,其实很简单,不对,是相当简单~~~~直接用例子来做比较容易理解一点

  问:求画出下面数字的哈夫曼树和所有子节点的哈夫曼编码,数字有:

 

答:

哈夫曼树的建立过程:

(1)在这些数字当中,3和5是最小的,执行相加运算,则:

(2)然后剩下数字:

(3)这些数字中6和7是最小的,执行相加运算,则:

(4)剩下数字:

(5)那么8和9是最小的,执行相加,则:

(6)剩下数字:

 

(7)数字11和13最小,执行相加,则:

(8)剩下数字:

(9)那么只剩17和24了,执行相加,则:

(10)那么我们就看到啦,这就是哈夫曼树,根节点是最顶端的那个数字:41,是不是简单的不行!!!学会了吧,那我们接下来还有哈夫曼编码呢,那就更加简单了,看!

哈夫曼编码:

(1)我们把建立成功的哈夫曼树进行一个标记,标记规则:左子树统统标0,右子树统统标1,则:

(2)标好了之后呢,我们就可以吧那些子节点的编码哦,看的一清二楚,比如:

编号3的编码为:000

编号5的编码为:100

编号6的编码为:011

编号7的编码为:111

编号8的编码为:00

编号9的编码为:10

编号11的编码为:01

    ...

所以,我们看到了规则,为:子节点到根节点的所有标记相加就对啦!!是不是很简单,简单的不要不要的??不客气!

                                                                END

原文地址:https://www.cnblogs.com/finalanddistance/p/7001583.html