Question

有七个带权结点，其权值分别为3,5,7,2,6,12,15。构造哈夫曼树，计算带权路径长度。

有七个带权结点，其权值分别为3,5,7,2,6,12,15。构造哈夫曼树，计算带权路径长度。求解题过程，跪求！

Answer 1

深度6先序：EBADCFHGIKJ 

中序：ABCDEFGHIJK 

后序：ACDBGJKIHFE。

哈夫曼树是：

100

/ \

42 58

/ \ / \

17 25 26 32

/ \ / \

8 9 12 13

/ \ / \

3 5 6 7

树的带权路径长度为WPL = （3+5 + 6 +7）*4 + （9+ 12）*3 + （26+32）*2 = 263

扩展资料：

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

WPL是衡量一个带权二叉树优劣的关键。

无论如何，对于n个带权节点，总可以用他们作为叶节点构造出一颗最小WPL值得树，并称满足这个条件的二叉树为哈夫曼树。

参考资料来源：百度百科-wpl

Answer 2

深度6 先序：EBADCFHGIKJ 中序：ABCDEFGHIJK 后序：ACDBGJKIHFE

追问

能不能给个答案和过程，赶ddl，最近期中考试，网课没怎么看，这部分看不懂。万分感谢！！！