7-1 哈夫曼树
分数 15
作者 李廷元
单位 中国民用航空飞行学院
哈夫曼树，第一行输入一个数n，表示叶结点的个数。
需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出哈夫曼树的带权路径长度（WPL）。
输入格式:
第一行输入一个数n，第二行输入n个叶结点（叶结点权值不超过1000，2<=n<=1000）。
输出格式:
在一行中输出WPL值。
输入样例:
5
1 2 2 5 9
输出样例:
37
我的问题：
我们老师上课讲解过如何构造哈夫曼树这是方法：
结点结构如下。
define MAXBIT 10
define MAXVALUE 1000
typedef struct HNode /定义结点结构/
{ int weight;
int parent , lchild , rchild;
}HNode, *HTree;
HTree HuffmanTree( int w , int n) /给定n个权值构造哈夫曼树/
{ / w存储n个字符的权值，构造哈夫曼树HT*/
int m, m1, m2, x1, x2, i, j; HTree ht;
HNode *p;
if (n <= 1) return NULL;
m= 2*n-1;
ht = (HNode *)malloc (m*sizeof(HNode) ); /*哈夫曼树的构造*/
if(ht==NULL) return ht;
for(p = ht, i =0; i < n; ++ i, ++ p, ++w) /*初始化叶子结点信息*/
{ p->weight = *w; p->lchild = -1;
p->rchild = -1; p->parent = -1;
}
for( ; i < m; ++ i, ++ p) /*初始化分支结点信息*/
{ p->weight = 0; p->lchild = -1;
p->rchild = -1; p->parent = -1;
}
for( i = n; i < m; ++ i) /*构造哈夫曼树 */
{ m1 = m2 = MAXVALUE;
x1 = x2 = 0; /寻找parent为-1且权值最小的两棵子树/
for(j = 0; j < i; ++ j)
{ if( ht[j].parent == -1 && ht[j].weight < m1)
{ m2 = m1; x2 = x1; m1 = ht[j].weight; x1 = j; }
else if( ht[j].parent == -1 && ht[j].weight < m2)
{ m2 = ht[j].weight; x2 = j; }
}
/合并成一棵新的子树/
ht[x1].parent = i; ht[x2].parent = i;
ht[i].lchild = x1; ht[i].rchild = x2;
ht[i].weight = m1 + m2;
}
return ht;
}
说实话看的有的云里雾里的能不能用中文描述下思路
而且题中要让求最短路径长度，我这上面只有构造哈夫曼树这一块，求解最短路径长度这块有点不知道如何下手，还有主函数也不太知道咋写，希望能同时提供解题思路以及完整运行结果，感谢感谢，因为基础太差了，我就算知道思路自己也打不出来，答案错误看半天也找不出错误，辛苦
