2013-01-04 13:15:00      个评论

n个叶子结点的哈夫曼树需要经过n-1次合并，产生n-1个新结点。最终求得的哈夫曼树共有2n-1个结点

[cpp]

#include <stdio.h>

#include <stdlib.h>

#include <string.h>

#define MAX_SIZE 100

#define MIN_NUM 1000000

struct hfmcode

{

int weight;

int lchild;

int rchild;

int parent;

};

parent域的作用：其一是查找双亲结点更为简单。其二是可通过判定parent值是否为-1来区分根和非根结点。

（1）初始化，将T[0..m-1]中的2n-1个结点里的三个指针均置空（==-1）,权值置为0.

[cpp]

void initHuffmantree(struct hfmcode *tree, int len)

{

int i;

for(i = 0; i < len; i ++)

{

tree[i].weight = 0;

tree[i].lchild = -1;

tree[i].rchild = -1;

tree[i].parent = -1;

}

}

（2）输入，读入n个叶子的权值存于向量的前n个分量（即T[0..n-1]）中。

[cpp]

int main()

{

int n, m, i;

struct hfmcode hfmtree[MAX_SIZE];

while(scanf("%d", &n) != EOF)

{

/*哈夫曼树总共结点数*/

m = 2 * n - 1;

/*初始化哈夫曼树*/

initHuffmantree(hfmtree, m);

/*权限赋值*/

for(i = 0; i < n; i ++)

{

scanf("%d", &hfmtree[i].weight);

}

/*构造哈夫曼树*/

createHuffmantree(hfmtree, n, m);

printf("%d\n", hfmtree[m - 1].weight);

}

return 0;

}

（3）合并，对森林中的树共进行n-1次合并，所产生的新结点依次放入向量T的第i个分量中(n<=i<=m-1).每次合并分两步：

[cpp]

void createHuffmantree(struct hfmcode *tree, int n, int m)

{

int m1, m2, i, loc1, loc2, k;

for(i = n; i < m; i ++)

{

/*初始化最小值、次小值*/

m1 = m2 = MIN_NUM;

loc1 = loc2 = -1;

/*在尚未构造二叉树的节点中查找权值最小的两棵树*/

for(k = 0; k < i; k ++)

{

if(tree[k].parent == -1)

{

if(tree[k].weight < m1)

{

m2 = m1;

loc2 = loc1;

m1 = tree[k].weight;

loc1 = k;

}else if(tree[k].weight < m2)

{

m2 = tree[k].weight;

loc2 = k;

}

}

}

/*修改2个小权重节点的双亲*/

tree[loc1].parent = i;

tree[loc2].parent = i;

/*修改parent的权重*/

tree[i].weight = tree[loc1].weight + tree[loc2].weight;

/*修改parent的孩子*/

tree[i].lchild = loc1;

tree[i].rchild = loc2;

}

}