哈夫曼树以及哈夫曼编码的构造步骤
热效率
注意：哈夫曼树并不唯⼀，但带权路径长度⼀定是相同的。 刘智仁（2）从19，21，2，3，6，7，10，32中选择两个权⼩结点。选中2，3。同时算出这两个结点的和5。
（3）从19，21，6，7，10，32，5中选出两个权⼩结点。选中5，6。同时计算出它们的和11。
（4）从19，21，7，10，32，11中选出两个权⼩结点。选中7，10。同时计算出它们的和17。
（BTW：这时选出的两个数字都不是已经构造好的⼆叉树⾥⾯的结点，所以要另外开⼀棵⼆叉树；或者说，如果两个数的和正好是下⼀步的两个最⼩数的其中的⼀个，那么这个树直接往上⽣长就可以了，如果这两个数的和⽐较⼤，不是下⼀步的两
个最⼩数的其中⼀个，那么就并列⽣长。）
2019十大经济年度人物
（5）从19，21，32，11，17中选出两个权⼩结点。选中11，17。同时计算出它们的和28。
（6）从19，21，32，28中选出两个权⼩结点。选中19，21。同时计算出它们的和40。另起⼀颗⼆叉树。
（7）从32，28， 40中选出两个权⼩结点。选中28，32。同时计算出它们的和60。
（8）从 40， 60中选出两个权⼩结点。选中40，60。同时计算出它们的和100。好了，此时哈夫曼树
已经构建好了。
大接访
第⼆部分：由上述所得哈夫曼树写出哈夫曼编码
⾸先我们来看这棵构造好的哈夫曼树：（经过左边路径为0，经过右边路径为1）
则可直接写出编码，例如：
A:11 B:001 C:011 D E：0000 F：0001 G：0100 H：0101 I：1000 J：1001
为了简便起见，我们从树的左边开始考虑，即B,E,F节点。 对于节点B，其深度为3，权值为5，那么其带权路径长度为5*3 = 15；
那么我们再看⼀下节点B的⽗亲节点，其权值为9，是由权值为4和权值为5的节点B构造⽽成，那么即是9 = 4 + 5；
同样的再往上⼀层，节点B的爷爷节点，其权值为16，是由权值为9和权值为7的节点构造⽽成，⽽权值为9的节点的构造前⾯已经说明，则有16 = 4 + 5 + 7；再往上⼀层就到根节点了。
那么到这⾥我们可以看到，节点B的⽗亲节点和爷爷节点的组成部分都有节点B的“功劳”，即节点B的
权值是其另外两个的“组成部分”，那么节点B的带权路径长度即为其到根节点路径上（不包含根节点），与其（或者说是与其⽗节点，爷爷节点等）有⽗⼦关系的节点抽取出节点B的组成部分（包括节点B本⾝），再全部相加，这样的话就得到了节点B的带权路径长度为5 + 5 + 5 = 15；
⾝），再全部相加，这样的话就得到了
同样的，节点E,F按照同样的⽅法进⾏推导。
排球在线论坛所以我们从上⾯的分析得出：
每个带权叶节点到根节点的带权路径长度等于其到根节点路径上所有节点的包含该带权叶节点权值组成部分之和。
辽宁警网因此，最后我们推导出，所有叶节点，即整棵哈夫曼树的带权路径长度 WPL即为：
因此，最后我们推导出，所有叶节点，即整棵
除了根节点以外，所有节点的权值之和。
如上图哈夫曼树的带权路径长度 WPL即为：
如上图
WPL = 16 + 10 + 9 + 7 + 5 + 5 + 4 + 5 + 3 + 4 + 2 + 3 + 2 + 2 + 2 + 1 + 1 + 1 = 82
有了这样的判断之后，我们便很容易计算出⼀颗哈夫曼树的带权路径WPL了。
因此我们可以借助⼀个叫做优先队列的数据结构，⽽优先队列的实现往往是借助于⼆叉堆的结构实现，在这⾥我们要实现的是⼩根堆的数据结构。⼀开始的时候，我们可以将所有的节点⼀个⼀个的压⼊队列中，每次有节点⼊队，队列都会进⾏⾃调整，使其保持⼀个⼩根堆的状态。当所有的节点全部⼊队之后，这时候我们根据以上推导出来的结论，每次取两个权值最⼩的节点，将其值计算之后，然后再将两个节点权值之和的节点压⼊队列中，直到队列中只剩下⼀个节点（即根节点），跳出循环体，输出最后的答案。即整棵哈夫曼树的带权路径WPL。
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议