求大神帮忙解答此题哈夫曼树 最好能附上注释 思路 本人新手 谢谢了
1. 哈夫曼算法问题描述: 带权路径长度达到最小的扩充二叉树即为哈夫曼树。
在哈夫曼树中,权值大的结点离根最近。
哈夫曼算法
(1) 由给定的 n 个权值 {w0, w1, w2, …, wn-1},构造具有 n 棵扩充二叉树的森林 F = { T0, T1, T2, …, Tn-1 },其中每棵扩充二叉树 Ti 只有一 个带权值 wi 的根结点, 其左、右子树均为空。
(2) 重复以下步骤, 直到 F 中仅剩下一棵树为止:
① 在 F 中选取两棵根结点的权值最小的扩充二叉树, 做为左、右子树
构造一棵新的二叉树。置新的二叉树的根结点的权值为其左、右子树
上根结点的权值之和。
② 在 F 中删去这两棵二叉树。
③ 把新的二叉树加入 F。
请根据以下的根结点编写一个构建哈夫曼树的程序。
7 9 2 6 32 3 21 10