C语言程序 二叉树 ---- 哈夫曼树的生成

给定n个权值作为n的叶子结点，构造一棵二叉树，若带权路径长度达到最小，称这样的二叉树为最优二叉树，也称为哈夫曼树(Huffman tree)。

哈夫曼树是带权路径长度最短的树，权值较大的结点离根较近。

ubuntu 14.04 linux c

gcc (Ubuntu 4.8.2-19ubuntu1) 4.8.2

#include

#include

#define MAX_WEIGHT 100

typedef struct ht_tree{

int weight;

int parent;

int lchild;

int rchild;

}ht;

void create_huffman_tree(ht data[],int size)

{

int lnode_index=0,rnode_index=0,weight=0;

int lvalue_min=0,rvalue_min=0;

int i = 0,j = 0;

for(i = size;i<2*size-1;i++)

{

lvalue_min = rvalue_min = MAX_WEIGHT*size*2;

lnode_index = rnode_index= -1;

for(j=0;j

{

if(data[j].parent == -1)

{

if(data[j].weight < lvalue_min)

{

rvalue_min = lvalue_min;

rnode_index = lnode_index;

lvalue_min = data[j].weight;

lnode_index = j;

}

else if(data[j].weight < rvalue_min)

{

rvalue_min = data[j].weight;

rnode_index = j;

}

}

}

data[i].weight = data[lnode_index].weight + data[rnode_index].weight;

data[lnode_index].parent = i;

data[rnode_index].parent = i;

data[i].lchild = lnode_index;

data[i].rchild = rnode_index;

}

}

int main(int argc,char *argv[])

{

int i = 0,j = 0,size = 0,huffman_tree_size = 0;

ht *array = NULL;

if(argc != 2)

{

printf("input error,exit !!\n");

return -1;

}

size =atoi(argv);

huffman_tree_size = size*2-1;

array =(ht*)malloc(sizeof(ht)*huffman_tree_size);

printf("the original array is :\n");

for(i=0;i

{

if(i

array[i].weight = rand()%MAX_WEIGHT;

else

array[i].weight = 0;

array[i].parent = -1;

array[i].lchild = -1;

array[i].rchild = -1;

printf("%d,",array[i].weight);

}

printf("\n");

create_huffman_tree(array,size);

printf("the huffman tree is : \n");

for(i=0;i

{

printf("%d,",array[i].weight);

}

printf("\n");

free(array);

return 0;

}

root@linux:~/code# gcc -o huffman_tree huffman_tree.c

root@linux:~/code# ./huffman_tree 4

the original array is :

83,86,77,15,0,0,0,

the huffman tree is :

83,86,77,15,92,169,261,