用huffman算法求带权为2,3,5,7,8的最优2元树,要求画出中间过程...

发布网友发布时间：2024-05-30 21:42

共3个回答

热心网友时间：2024-06-19 18:43

7/8应该一起作为同一父的叶这样才是最优，权为55

把最小的两个数2、3放在最下面作为左右叶子节点，得出他们的父节点权值5，然后它和剩余里最小的数5做成左右兄弟节点，得出父节点10，以此类推啊，10和7得出17，17和8，得到跟节点25完成。

例如：

先将所有的权值选出最小的两个值，为1，4，这两个的和为5，那么再从5，9，25，36，49中选出两个最小的，为5和9，然后再从14，25，36，49中选出两个最小的，为14，25，依次进行下去。那么就可以得到最优二叉树为：（） / \ () 49 / \ () 36 / \ () 25 / \ () 9 / \ 1 4

扩展资料：

所谓树的带权路径长度，就是树中所有的叶结点的权值乘上其到根结点的路径长度（若根结点为0层，叶结点到根结点的路径长度为叶结点的层数）。

树的路径长度是从树根到每一结点的路径长度之和，记为WPL=（W1*L1+W2*L2+W3*L3+...+Wn*Ln），N个权值Wi（i=1,2,...n）构成一棵有N个叶结点的二叉树，相应的叶结点的路径长度为Li（i=1,2,...n）。可以证明哈夫曼树的WPL是最小的。

参考资料来源：百度百科-哈夫曼树

热心网友时间：2024-06-19 18:45

7/8应该一起作为同一父的叶这样才是最优，权为55

热心网友时间：2024-06-19 18:47

过程就是：首先把最小的两个数2、3放在最下面作为左右叶子节点，得出他们的父节点权值5，然后它和剩余里最小的数5做成左右兄弟节点，得出父节点10，以此类推啊，10和7得出17，17和8，得到跟节点25.完成！