樹的路徑長度 樹的路徑長度是從樹根到樹中每一結點的路徑長度之和。在結點數目相同的二叉樹中，完全二叉樹的路徑長度最短。 樹的帶權路徑長度(weighted path length of tree,wpl) 結點的權值：在一些應用中，賦予樹中結點的一個有某種意義的實數、 結點的帶權路徑長度：結點到樹根之間的路徑長度與該結點上權的乘積 樹的帶權路徑長度(wpl)：定義為樹中所有結點的帶權路徑長度之和 最優二叉樹 在權為w1,w2,...,wn的n個葉子結點所構成的所有二叉樹中，帶權路徑長度最小(即代價最小)的二叉樹成為最優二叉樹。 注意： 葉子上的權值均相同時，完全二叉樹一定是最優二叉樹，否則完全二叉樹不一定是最優二叉樹。 最優二叉樹中，權值越大的葉子結點離根越近 最優二叉樹的形態不唯一，wpl最小 構造最優二叉樹 哈夫曼算法 根據給定的n個權值w1,w2,...,wn構成n棵二叉樹的森林F={T1,T2,..,Tn},其中每棵二叉樹Ti中只有一個權值為wi的根節點，其左右子樹均為空。 在森林F中選出兩棵根結點權值最小的樹(當這種的樹不止兩棵時，可以從中任選兩棵)，將這兩棵樹和並稱一棵新樹，為了保證新樹仍是二叉樹，需要增加一個新結點作為新樹的根，並將所選的兩棵樹根分別作為新樹的左右孩子，將這兩個孩子的權值之和作為新樹根的權值 對新的森林F重復2,直到森林F只剩一棵樹為止。 注意 初始森林中的n棵二叉樹，每棵樹都有一個孤立的結點，它們既是根，又是葉子 n個葉子結點的哈夫曼樹需要經過n-1次合並，產生n-1個新結點。最終求得的哈夫曼樹共有2n-1個結點 哈夫曼樹是嚴格的二叉樹，沒有度數為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; }; 注意： 因此數組下界為0,因此用-1表示空指針。樹中某結點的lchild,rchild,parent不等於-1時，它們分別是該結點的左、右孩子和雙親結點在向量中的下標。 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).每次合並分兩步： 在當前森林T[0..i-1]的所有結點中，選取權最小和次小的兩個根節點T[p1]和T[p2]作為合並對象，這裡0<=p1,p2<=i-1 將根為T[p1]和T[p2]的兩棵樹作為左右子樹合並為一棵新的樹，新的樹根是新節點T[i].具體操作是：將T[p1]和T[p2]的parent置為i,將T[i]的lchild和rchild分別置為p1和p2.新結點T[i]的權值置為T[p1]和T[p2]的權值之和。 合並後，T[p1]和T[p2]在當前森林中已不再是根，因為它們的雙親指針均已指向了T[i],所以下次合並時不會被選中為合並對象。 [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; } } 哈夫曼編碼 編碼和解碼 數據壓縮的過程成為編碼。即將文件中的每個字符均轉換為一個唯一的二進制位串 數據解壓過程成為解碼。即將二進制位串轉換位對應的字符 前綴碼&&最優前綴碼 對字符集進行編碼時，要求字符集中任一字符的編碼都不是其它字符的編碼的前綴，這種編碼成為前綴編碼 平均碼長或文件總長最小的前綴編碼成為最優前綴編碼，最優前綴編碼對文件的壓縮效果亦最佳。
