UC知道求助有关哈夫曼树的问题！急！满意的答案再加!
来源：百度知道 编辑：UC知道 时间：2024/05/14 06:43:03
问题如下（注意不是静态数组的方法）：
1、用动态生成结点的方法构造哈夫曼树,按先根序列输出您生成的哈夫曼树的结点的权值。
2、用您构造哈夫曼树的程序，给26个英文字母编码，26个英文字母的权可按如下方法给出：在任一英文字典中，该字母开始的单词的数量占总单词量的比（不必很准确）。
这两个问题是放在一个程序里头的。
麻烦各位给我编一下，越快越好，谢谢！！满意的答案我会再追加100分
是C语言的。其实我需要第一个问题就可以了。
哈夫曼树
一、 基本术语
1. 路径与路径长度
若在一棵树中存在一个结点序列 k1, k2, …., kj ，使得kj是kj+1的双亲（1<=i<j），则称结点序列是从k1到kj 的路径（如树中的某个结点到它的某个祖先，或者到它的某个后代的的包括它本身的一系列按顺序的结点序列称为路径），因树中的每个结点只有一个双亲结点，所以这是两个结点间的唯一路径，从k1到kj 所经过的分支数称为这两点之间的路径长度。它等于结点数-1。
如： 从结点A到结点J的结点序
列为A，B，E，J。
路径长度为3。
8 10
4 5 3
2. 结点的权和带权路径长度
如果根据需要给树中的结点赋予一个有某中意义的实数，则称此实数为该结点的权，结点带权路径长度规定为从树根结点到该结点之间的路径长度乘上该结点的权值所得到的乘积。
3. 树的带权路径长度
树的带权路径长度定义为树中所有叶结点的带权路径长度之和，通常记为：
n
WPL=∑ wili wi和li 分别代表叶结点ki的权值和ki到
i=1 根结点的路径长度
例如：上图的WPL=（4+5+3）*3+（8+10）*2=72
4. 哈夫曼树
哈夫曼树又称为最优二叉树，它是由n个带权叶结点构成的所有二叉树中带权路径长度WPL最小的二叉树。
例如：有四个叶结点a，b，c，d，分别带权为9，4，5，2，可以构成三棵不同的二叉树（当然可以构成更多的二叉树）见下图：
9 4 5 2 WPL=（9+4+5+2）*2=40
4
2
5 9
WPL=（9+5）*3+2