給定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[1]);
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;
}
[email protected]:~/code# gcc -o huffman_tree huffman_tree.c
[email protected]:~/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,