哈夫曼树
主要是记录一道九度的哈夫曼树的题目题目
[html]
题目描述：
哈夫曼树，第一行输入一个数n，表示叶结点的个数。需要用这些叶结点生成哈夫曼树，根据哈夫曼树的概念，这些结点有权值，即weight，题目需要输出所有结点的值与权值的乘积之和。
输入：
输入有多组数据。
每组第一行输入一个数n，接着输入n个叶节点（叶节点权值不超过100，2<=n<=1000）。
输出：
输出权值。
样例输入：
5
1 2 2 5 9
样例输出：
37
ac代码
[cpp]
#include <stdio.h>
#include <stdlib.h>
#define max 1001
struct htree
{
int weight;
struct htree *lchild;
struct htree *rchild;
struct htree *next;
};
void addNode(struct htree *, struct htree *);
struct htree* createHfmtree(int *, int);
int getWpl(struct htree *, int);
int main()
{
int w[max];
int i, n, wpl;
struct htree *ht;
while(scanf("%d", &n) != EOF)
{
for(i = 0; i < n; i ++)
{
scanf("%d", &w[i]);
}
ht = createHfmtree(w, n);
wpl = getWpl(ht, 0);
printf("%d\n", wpl);
}
return 0;
}
struct htree* createHfmtree(int *w, int n)
{
int i;
struct htree *head, *pl, *pr, *proot;
head = (struct htree *)malloc(sizeof(struct htree));
head->next = NULL;
for(i = 0; i < n; i ++)
{
struct htree *pnode = malloc(sizeof(struct htree));
pnode->weight = *(w + i);
pnode->lchild = pnode->rchild = pnode->next = NULL;
addNode(head, pnode);
}
while(head->next)
{
if(head->next->next == NULL)
break;
pl = head->next;
pr = pl->next;
head->next = pr->next;
proot = (struct htree *)malloc(sizeof(struct htree));
proot->weight = pl->weight + pr->weight;
proot->lchild = pl;
proot->rchild = pr;
addNode(head, proot);
}
return head->next;
}
void addNode(struct htree *head, struct htree *pnode)
{
struct htree *t = head;
while(t->next && t->next->weight < pnode->weight)
t = t->next;
pnode->next = t->next;
t->next = pnode;
} www.zzzyk.com
int getWpl(struct htree *ht, int level)
{
if(ht == NULL)
return 0;
if(!ht->lchild && !ht->rchild)
{
return ht->weight * level;
}
return getWpl(ht->lchild, level + 1) + getWpl(ht->rchild, level + 1);
}
补充：软件开发 , C++ ,
