C語言 資料結構與算法---哈夫曼樹(編碼)

文章目錄

• 一. 關于哈夫曼樹
• 二. 哈夫曼樹的實作
• 三. 哈夫曼編碼
• • 1.哈夫曼編碼的定義
  • 2. 哈夫曼編碼的實作

一. 關于哈夫曼樹

• 路徑：從樹中一個結點到另一個結點之間的分支構成兩個結點之間的路徑。
• 路徑長度：路徑上的分支數目
• 樹的路徑長度：從樹根到每一結點的路徑之和
• 結點的權：樹結點間的邊相關數
• 結點的帶權路徑長度：從根結點到該結點之間的路徑長度與該結點的權的乘積
• 樹的帶權路徑長度（WPL）：樹中所有葉子結點的帶權路徑長度之和
• 哈夫曼樹：帶權路徑最短二叉樹。（也稱為最優二叉樹）

實作思路：

• 構造森林全是根：

  森林裡的樹隻有一個帶權的根結點

• 選用兩小造新樹：
  1. 在森林中選取兩顆結點的權值最小的樹作為左右子樹
  2. 設定新的二叉樹的根結點的權值為其左右子樹根結點的權值之和

• 删除兩小造新人：

  在森林中删除這兩棵樹，同時将得到的二叉樹加入森林

• 重複上述步驟，直到森林中隻有一棵樹為止，這棵樹即為哈夫曼樹

1. 哈夫曼樹結點的度為0或2，沒有度為1的結點
2. 包含 n 個葉子結點的哈夫曼樹中共有 2n-1 個結點（包含n棵樹的森林要經過n-1次合并才能形成哈夫曼樹，共産生n-1個新結點）

二. 哈夫曼樹的實作

注意：為了使得到的哈夫曼樹的結構盡量唯一，通正常定生成的哈夫曼樹中的每個結點左子樹的根結點小于等于右子樹根結點的權

1. 哈夫曼樹的構造

哈夫曼樹沒有使用真正的樹結構，而是用數組來控制相應的結構

typedef struct
{
	int weight; //權值
	int parent, lchild, rchild;//雙親，左右孩子的下标
}HTNode, *HuffmanTree;
           

哈夫曼樹中共有2n-1個結點，不使用0為下标，數組大小為2n ----> 結點下标為1~2n-1

2. 找出最小的兩個值：

//HT數組中存放的哈夫曼樹
//end表示 HT 數組中存放結點的最終位置
//s1和s2傳遞的是 HT 數組中權重值最小的兩個結點在數組中的下标
void Select(HuffmanTree HT, int end, int* s1, int* s2)
{
	//分别對應s1,s2的權值,保持 min1 < min2
	int min1, min2;
	//周遊數組初始下标為 1
	int i = 1;
	//找到一個最近的，還沒有建構樹的結點
	while (HT[i].parent != 0 && i <= end)
	{
		i++;
	}
	min1 = HT[i].weight;
	*s1 = i;
	i++;

	//再尋找一個最近的，
	while (HT[i].parent != 0 && i <= end)
	{
		i++;
	}

	//對比找到的兩個結點的大小，min2為大的，min1為小的
	if (HT[i].weight < min1)
	{
		min2 = min1;
		*s2 = *s1;
		min1 = HT[i].weight;
		*s1 = i;
	}
	else
	{
		min2 = HT[i].weight;
		*s2 = i;
	}

	//兩個結點和後續的所有未建構成樹的結點做比較
	for (int j = i + 1; j <= end; j++)
	{
		//如果有父結點，直接跳過，進行下一個
		if (HT[j].parent != 0)
		{
			continue;
		}
		//如果比最小的還小，将min2=min1，min1指派新的結點的下标
		if (HT[j].weight < min1)
		{
			min2 = min1;
			min1 = HT[j].weight;
			*s2 = *s1;
			*s1 = j;
		}
		//如果介于兩者之間，min2指派為新的結點的位置下标
		else if (HT[j].weight >= min1 && HT[j].weight < min2)
		{
			min2 = HT[j].weight;
			*s2 = j;
		}
	}
}
           

3. 建構哈夫曼樹

//HT為位址傳遞的存儲哈夫曼樹的數組
//w為存儲結點權重值的數組
//n為結點個數
void CreateHuffmanTree(HuffmanTree* HT, int* w, int n)
{
	if (n <= 1)
	{
		return;   //如果隻有一個結點無意義	
	}
	//哈夫曼樹總節點數，n是葉子結點
	int m = 2 * n - 1;  
	//數組下标為 0 不用，使用1~2n-1
	*HT = (HuffmanTree)malloc((m + 1) * sizeof(HTNode));
	HuffmanTree p = *HT;

	// 初始化哈夫曼樹中的所有葉結點
	for (int i = 1; i <= n; i++)
	{
		(p + i)->weight = *(w + i - 1);//w數組下标是從0開始的
		(p + i)->parent = 0;
		(p + i)->lchild = 0;
		(p + i)->rchild = 0;
	}

	//從樹組的下标 n+1 開始初始化哈夫曼樹中除葉結點外的結點
	for (int i = n + 1; i <= m; i++)
	{
		(p + i)->weight = 0;
		(p + i)->parent = 0;
		(p + i)->lchild = 0;
		(p + i)->rchild = 0;
	}

	//建構哈夫曼樹
	for (int i = n + 1; i <= m; i++)
	{
		//儲存最小值的下标，且s1<s2
		int s1, s2;
		Select(*HT, i - 1, &s1, &s2);
		(*HT)[s1].parent = (*HT)[s2].parent = i;
		(*HT)[i].lchild = s1;
		(*HT)[i].rchild = s2;
		(*HT)[i].weight = (*HT)[s1].weight + (*HT)[s2].weight;
	}
}
           

三. 哈夫曼編碼

1.哈夫曼編碼的定義

關鍵：要設計長度不等的編碼，則必須使得任一字元的編碼都不是另一個字元編碼的字首------字首編碼

哈夫曼編碼：使得電文總長最短的字首編碼

1. 統計字元集中每個字元在電文中出現的平均機率（機率越大，要求編碼越短）
2. 利用哈夫曼樹的特點：權越大的葉子離根更近；将每個字元的機率作為權值，構造哈夫曼樹。則機率越大的結點，路徑越短

3. 在哈夫曼樹的每個分支上表上0或1：

   ① 結點左分支标為 0，右分支标為 1；

   ② 把從根到每個葉子的路徑上的标号連接配接起來，作為該葉子代表字元的編碼

為什麼哈夫曼編碼能夠保證是字首編碼？

答：因為沒有一片樹葉是另一片樹葉的祖先，是以每個葉結點的編碼就不可能是其他葉結點編碼的字首。

為什麼哈夫曼編碼能夠保證字元編碼總長最短？

答：因為哈夫曼樹的帶權路徑長度最短

2. 哈夫曼編碼的實作

從葉子結點出發更為簡便：

typedef char** HuffmanCode;

//HC為存儲結點哈夫曼編碼的 二維 動态數組，n為結點的個數
//n 個元素，哈夫曼樹最高為 n-1，即編碼最多 n-1 位，加上‘\0’,共 n 位
void  HuffmanCoding(HuffmanTree HT, HuffmanCode* HC, int n)
{
	//配置設定了 n+1 行，下标使用1~n
	*HC = (HuffmanCode)malloc((n + 1) * sizeof(char*));
	//存放哈夫曼編碼的字元串數組
	char* cd = (char*)malloc(n * sizeof(char)); 
	cd[n - 1] = '\0';
	//從葉子結點出發，得到的哈夫曼編碼是逆序的
	for (int i = 1; i <= n; i++)
	{
		int start = n - 1; //目前結點在數組中的位置
		int c = i;//目前結點的雙親結點在數組中的位置
		int j = HT[i].parent;
		while (j != 0)
		{
			//該結點是雙親結點的左孩子,對應路徑編碼為0
			if (HT[j].lchild == c)
			{
				cd[--start] = '0';
			}
			//該結點是雙親結點的右孩子,對應路徑編碼為1
			else
			{
				cd[--start] = '1';
			}
			c = j; //以雙親結點為孩子結點，繼續朝樹根的方向周遊
			j = HT[j].parent;
		}
		//跳出循環後，cd數組中從下标 start 開始，存放的就是該結點的哈夫曼編碼
		(*HC)[i] = (char*)malloc((n - start) * sizeof(char));//給每一行配置設定列
		strcpy((*HC)[i], &cd[start]);
	}
	free(cd);
}