樹與二叉樹——哈夫曼樹及哈夫曼編碼

哈弗曼樹的有關概念和定義這裡省略，這裡主要是展示如何用代碼構造哈夫曼樹以及哈夫曼編碼。

#include <stdio.h>           
#define SIZE 5                           /*假設字元集中有5個字元*/
typedef struct                         /*定義哈夫曼樹的結點結構*/
{
  int weight;                         /*假定權值為整數*/
  int parent, lchild, rchild;/*parent為父節點的下标， lchild為左子樹的下标， rchild為右子樹的下标*/
} ElemType;
char ch[SIZE] = {'A', 'B', 'C', 'D', 'E'};         /*定義字元集*/
int w[SIZE] = {35, 25, 15, 15, 10};           /*每個字元出現的頻率*/
void HuffmanTree(ElemType huffTree[ ]);              /*函數聲明，建哈夫曼樹*/
void Select(ElemType huffTree[ ], int k, int *i1, int *i2);   /*求兩個最小值*/
void HuffmanCode(ElemType huffTree[ ]);               /*求哈夫曼編碼*/
                                               
int main( )
{
	ElemType huffTree[2 * SIZE - 1];        /*數組huffTree存儲哈夫曼樹*/
	HuffmanTree(huffTree);           /*調用函數HuffmanTree求哈夫曼樹*/
	HuffmanCode(huffTree);          /*調用函數HuffmanCode求哈夫曼編碼*/
	return 0;                    
}
                                    
void HuffmanTree(ElemType huffTree[ ]) 
{         /*求哈夫曼樹，形參是數組huffTree[2 * n - 1]，其中n是符号常量*/
    int i, k, i1, i2;           
	for (i = 0; i < 2 * SIZE - 1; i++)       /*初始化，所有結點均沒有雙親和孩子*/
    {
		 huffTree[i].parent = -1;
		 huffTree[i].lchild = -1;
		 huffTree[i].rchild = -1;
    }
	for (i = 0; i < SIZE; i++)         /*初始化，構造n棵隻含有根結點的二叉樹*/
    	 huffTree[i].weight = w[i];
	for (k = SIZE; k < 2 * SIZE - 1; k++)        /*進行n-1次合并*/
	{      
		 Select(huffTree, k, &i1, &i2);  /*查找權值最小的兩個根結點，下标為i1和i2*/
		 huffTree[k].weight = huffTree[i1].weight + huffTree[i2].weight;
		 huffTree[i1].parent = k;huffTree[i2].parent = k; //左右子樹的父節點的下标都是 k 
		 huffTree[k].lchild = i1;//父節點的左子樹的下标是i1. 
		 huffTree[k].rchild = i2;//父節點的右子樹的下标是i2. 
	}
}

//出入數組，選擇兩個權值最小的兩個元素，并記錄其下标，k為這兩個最小權值的元素的父節點 
void Select(ElemType huffTree[ ], int k, int *i1, int *i2)
{                       /*查找權值最小的兩個根結點，形參i1和i2為傳引用*/
	int min1 = 100;
	int min2 = 100;
	int i;                  /*初始化，假設頻率均小于100*/
	for (i = 0; i < k; i++)                  /*查找權值最小的兩個根結點*/
	{
		if (huffTree[i].parent == -1) {                  /*結點i是根結點*/
			if (huffTree[i].weight < min1) {            /*小于最小值*/
				min2 = min1; 
				*i2 = *i1; 
				min1 = huffTree[i].weight; 
				*i1 = i;
			}
			else if (huffTree[i].weight < min2) {        /*小于次最小值*/
               	min2 = huffTree[i].weight;
				*i2 = i;
            }
		}
	}	
}
void HuffmanCode(ElemType huffTree[ ])     /*求哈夫曼編碼*/
{         
	int i, j, k;
	int S[SIZE], top = -1;                     /*順序棧S存放求得的哈夫曼編碼*/
	for (i = 0; i < SIZE; i++)                   /*求每一個葉子結點的哈夫曼編碼*/
	{
		printf("字元%c的編碼是：", ch[i]);
		k = i;                   
		while (huffTree[k].parent != -1)      /*求結點k的雙親，直到根結點*/
		{
			j = huffTree[k].parent;          /* j為結點k的雙親*/
			if (huffTree[j].lchild == k)
				S[++top] = 0;             /*左分支編碼為0*/
			else
				S[++top] = 1;             /*右分支編碼為1*/
			k = j;
		}
		while (top != -1)                  /*逆序輸出棧S中的編碼*/
			printf("%d", S[top--]);
		printf("\n");
	}
}