【正文】 5 6 7 W 5 29 8 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 14 23 3 11 9991 78 10 10 3 415 11 11 12 819 14 14 12 13 13 15 15 529 42 58 100 210 11 614 12 13 HC 0 cd 0 1 2 3 4 5 6 7 1 2 3 4 5 6 7 8 0 0 1 1 ↑ start 0 0 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 0 0 0 0 0 0 0 1 求哈夫曼編碼過程的實(shí)例 : HT數(shù)組 if(n=1) return。i=n。 HT[s2].parent=i； HTIi].1child=s1； HT[j].rchild=s2； HT[i].weight=T[s1].weight+T[s2].weight； } // end for void HuffmanCoding(HuffmanTree amp。 cd[n1]=“\0”； for(i=1。c=f,f=HT[f].parent if(HT[f].lchild==c cd[start]=“0”。cd[start])； } free(cd)。實(shí)現(xiàn)二叉樹遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。二叉樹的 線索化過程 是 基于 對(duì)二叉樹進(jìn)行 遍歷 ，而線索二叉樹上的 線索又為相應(yīng)的遍歷提供了 方便 。 7. 了解 最優(yōu)樹的特性 ，掌握 建立最優(yōu)樹和哈夫曼編碼 的方法。建立存儲(chǔ)結(jié)構(gòu)是進(jìn)行其它操作的前提，因此讀者應(yīng) 掌握 1 至 2 種 建立 二叉樹和樹的 存儲(chǔ)結(jié)構(gòu)的方法 。 層次遍歷 是按另一種搜索策略進(jìn)行的遍歷。 2. 熟悉二叉樹的各種 存儲(chǔ)結(jié)構(gòu) 的特點(diǎn)及適用范圍。 HC[i]=(char * )malloc((nstart)*sizeof(char))。i++){ start=n1； for(c=i,f=HT[i].parent。HC, int *w,int n){ //從葉子到根逆向求每個(gè)字符的赫夫曼編碼 HC=(Huffmancode)malloc((n+1)*sizeof(char *))。i=m。 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))。 為方便計(jì)算，將所有字符的頻度乘以 100，使 其轉(zhuǎn)換成整型數(shù)值集合，得到 {5,29,7,8,14,23, 3,11}； 哈夫曼編碼設(shè)計(jì)如下圖： 11 5 29 7 8 14 23 3 100 0 1 15 58 29 0 0 0 1 1 1 8 42 19 0 0 0 1 1 1 00 010 0110 0111 1110 1111 110 10 哈夫曼樹的存儲(chǔ)結(jié)構(gòu) 用一個(gè)大小為 2n1的向量來存儲(chǔ)哈夫曼樹中 的結(jié)點(diǎn)，其存儲(chǔ)結(jié)構(gòu)為： typedef struct { //結(jié)點(diǎn)類型 int weight； //權(quán)值，不妨設(shè)權(quán)值均大于零 int lchild， rchild， parent； //左右孩子及雙親指針 }HTNode， *HuffmanTree。例如，可以為 A， B， C， D四個(gè)字符分別分配 0， 00， 1， 01，并可將上述電文用二進(jìn)制序列： 000011010發(fā)送，其長(zhǎng)度只有 9個(gè)二進(jìn)制位，但隨 之帶來了一個(gè)問題，接收方接到這段電文后無法 進(jìn)行譯碼，因?yàn)闊o法斷定前面 4個(gè) 0是 4個(gè) A， 1個(gè) B、 2個(gè) A，還是 2個(gè) B，即譯碼不唯一，因此這種編碼 方法不可使用。若現(xiàn)在電文為： ABACCDA， 則應(yīng)發(fā)送二進(jìn)制序列： 00010010101100， 總長(zhǎng)度為 14位。在設(shè)計(jì)編碼時(shí)需要遵守兩個(gè)原則： （ 1）發(fā)送方傳輸?shù)亩M(jìn)制編碼，到接收方解碼后必須具有 唯一性 ，即解碼結(jié)果與發(fā)送方發(fā)送的電文完全一樣； （ 2）發(fā)送的二進(jìn)制編碼 盡可能地短 。這棵樹便是哈夫 曼樹 (3) (4)9 例如 : 已知權(quán)值 W={ 5, 6, 2, 9, 7 } 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 6 7 13 9 5 2 7 9 5 2 7 16 6 7 13 29 注意： ? ① 初始森林中的 n棵二叉樹，每棵樹有一個(gè)孤立的結(jié)點(diǎn)，它們既是根，又是葉子 ② n個(gè)葉子的哈夫曼樹要經(jīng)過 n1次合并，產(chǎn)生 n1個(gè)新結(jié)點(diǎn)。 結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度 定義為： 從根結(jié)點(diǎn)到該結(jié)點(diǎn)的路徑 長(zhǎng)度與 結(jié)點(diǎn)上權(quán)的乘積。 ２．中序遍歷 若森林不空，則 中序遍歷 森林中第一棵樹的子樹森林； 訪問 森林中第一棵樹的根結(jié)點(diǎn)； 中序遍歷 森林中 (除第一棵樹之外 )其 余樹構(gòu)成的森林。 若樹不空，則自上而下自左至右訪問樹中每個(gè)結(jié)點(diǎn)。 例如 ： B E C F D G H I J K B C D E F G H I J K 由此，樹的各種操作均可對(duì)應(yīng)二叉樹的操作來完成。 T1 = (root， t11, t12, …, t 1m)。 樹結(jié)構(gòu) : 三、樹的二叉鏈表 (孩子 兄弟）存儲(chǔ)表示法 A B C D E F G A B C E D F G root A B C E D F G typedef struct CSNode{ Elem data。 // 孩子鏈的頭指針 } CTBox。 struct CTNode *next。 data parent define MAX_TREE_SIZE 100 結(jié)點(diǎn)結(jié)構(gòu) : C語言的類型描述 : typedef struct { PTNode nodes [MAX_TREE_SIZE]。 } return OK。 InThreading(T)。 Thrtrchild = Thrt。 // 右子樹線索化 } // if } // InThreading Status InOrderThreading(BiThrTree amp。 } if (!prerchild) // 建后繼線索 { preRTag = Thread。遍歷過 程中，附設(shè)指針 pre, 并始終保持指 針 pre指向當(dāng)前訪問的、指針 p所指 結(jié)點(diǎn)的前驅(qū)。 prchild!=T) { p = prchild。 // p指向根結(jié)點(diǎn) while (p != T) { // 空樹或遍歷結(jié)束時(shí)， p==T while (pLTag==Link) p = plchild。 由于在線索鏈表中添加了遍歷中得到的“前驅(qū)”和“后繼”的信息，從而簡(jiǎn)化了遍歷的算法。 線索鏈表 的類型描述： typedef enum { Link, Thread } PointerThr。 lchild LTag data RTag rchild ??????0 l c h i l dL T ag =1 l c h i l d0 r c h i l dRT ag =1 r c h i l d域指向結(jié)點(diǎn)的左孩子域指向結(jié)點(diǎn)的前驅(qū)域指向結(jié)點(diǎn)的右孩子域指向結(jié)點(diǎn)的后繼typ