【正文】 ”或 0； 否則， rchild域的指針指向其“后繼”， 且右標(biāo)志的值為“ 線索 Thread”或 1。 首先分析 二叉樹(shù)的深度 和它的 左 、 右子樹(shù)深度 之間的關(guān)系。 void CountLeaf (BiTree T, intamp。 if (ch＝＝’’ ) T=NULL。 if(!Visit(pdata)) return ERROR。 if(!Visit(pdata)) return ERROR。// 遍歷右子樹(shù) visit(Tdata)。 中（根）序的遍歷算法： void Inorder (BiTree T, void( *visit)(TElemTypeamp。 二、按層次遍歷二叉樹(shù) 實(shí)現(xiàn)方法為從上層到下層，每層中從左側(cè)到右側(cè)依次訪問(wèn)每個(gè)結(jié)點(diǎn)。 struct TriTNode *lchild, *rchild。 證明： 設(shè) 完全二叉樹(shù)的深度為 k 則根據(jù)第二條性質(zhì)得 2k1≤ n 2k 即 k1 ≤ log2 n k 因?yàn)? k 只能是整數(shù)，因此， k =?log2n? + 1 。 (i≥ 1) 用歸納法證明 ： 歸納基 ： 歸納假設(shè)： 歸納證明： i = 1 層時(shí)，只有一個(gè)根結(jié)點(diǎn)： 2i1 = 20 = 1； 假設(shè)對(duì)所有的 j， 1≤ j ? i， 命題成立； 二叉樹(shù)上每個(gè)結(jié)點(diǎn)至多有兩棵子樹(shù)， 則第 i 層的結(jié)點(diǎn)數(shù) = 2i2? 2 = 2i1 。T, definition)。 InOrderTraverse(T, Visit())。 Parent(T, e)。T) // 銷(xiāo)毀樹(shù)的結(jié)構(gòu) DeleteChild(amp。 若 D為空集，則稱(chēng)為空樹(shù) 。T, amp。 任何一棵非空樹(shù)是一個(gè)二元組 Tree = （ root， F） 其中： root 被稱(chēng)為根結(jié)點(diǎn) F 被稱(chēng)為子樹(shù)森林 森林： 是 m（ m≥ 0）棵互 不相交的樹(shù)的集合 A root B C D E F G H I J M K L F 二叉樹(shù)的類(lèi)型定義 二叉樹(shù)或?yàn)?空樹(shù) ，或是由一個(gè) 根結(jié)點(diǎn) 加上 兩棵 分別稱(chēng)為 左子樹(shù) 和 右子樹(shù)的、 互不交的 二叉樹(shù) 組成。 BiTreeEmpty(T)。 Assign(T, amp。T)。 兩類(lèi) 特殊 的二叉樹(shù)： 滿(mǎn)二叉樹(shù) ： 指的是深度為 k且含有 2k1個(gè)結(jié)點(diǎn)的二叉樹(shù)。 struct BiTNode *lchild, *rchild。 “遍歷 ”是任何類(lèi)型均有的操作， 對(duì)線性結(jié)構(gòu)而言，只有一條搜索路 徑 (因?yàn)槊總€(gè)結(jié)點(diǎn)均只有一個(gè)后繼 )， 故不需要另加討論。 // 訪問(wèn)結(jié)點(diǎn) Preorder(Tlchild, visit)。 后（根）序的遍歷算法： void Postorder (BiTree T, void( *visit)(TElemTypeamp。 p) Push(S,plchild)。 while(p||!StackEmpty(S)){ if(p) {Push(S,p)。 Status CreateBiTree (BiTree amp。 //構(gòu)造右子樹(shù) } return(OK)。 CountLeaf( Trchild, count)。 } return depthval。 // 左右指針 PointerThr LTag, RTag。 若 無(wú)右子樹(shù)， 則為 后繼線索 所指結(jié)點(diǎn)； 否則為 對(duì)其 右子樹(shù) 進(jìn)行中序 遍歷 時(shí)訪問(wèn)的 第一個(gè)結(jié)點(diǎn)。 } // 訪問(wèn)后繼結(jié)點(diǎn) p = prchild。 } pre = p。 else { Thrtlchild = T。 int parent。 孩子結(jié)點(diǎn)結(jié)構(gòu) : child next C語(yǔ)言的類(lèi)型描述 : typedef struct { Elem data。 } CSNode, *CSTree。 樹(shù)和森林的遍歷 一、樹(shù)的遍歷 二、森林的遍歷 樹(shù)的遍歷可有三條搜索路徑 : 按層次遍歷 : 先根 (次序 )遍歷 : 后根 (次序 )遍歷 : 若樹(shù)不空，則先訪問(wèn)根結(jié)點(diǎn)，然后依次先根遍歷各棵子樹(shù)。 B C D E F G H I J K 例如 ： 先序遍歷時(shí)頂點(diǎn)的訪問(wèn)次序： B E F C D G H I J K 后序遍歷時(shí)頂點(diǎn)的訪問(wèn)次序： E F B C I J K H G D 樹(shù)的遍歷和二叉樹(shù)遍歷的對(duì)應(yīng)關(guān)系 ？ 先根遍歷 后根遍歷 樹(shù) 二叉樹(shù) 森林 先序遍歷 先序遍歷 中序遍歷 中序遍歷 哈 夫 曼 樹(shù) 與 哈 夫 曼 編 碼 ? 最優(yōu)樹(shù) (哈夫曼樹(shù) )的定義 ? 如何構(gòu)造最優(yōu)樹(shù) ? 前綴編碼 ? 哈夫曼編碼 一、最優(yōu)樹(shù)的定義 樹(shù)的路徑長(zhǎng)度 定義為： 樹(shù)中每個(gè)結(jié)點(diǎn)的路徑長(zhǎng)度之和。 ③ 哈夫曼樹(shù)是嚴(yán)格的二叉樹(shù)，沒(méi)有度數(shù)為 1的分支結(jié)點(diǎn)。 這種編碼的特點(diǎn) : 譯碼簡(jiǎn)單且具有唯一性，但編碼長(zhǎng)度并不是 最短的。 哈夫曼編碼的存儲(chǔ)結(jié)構(gòu) Weight parent lchild rchild 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 5 29 7 8 14 23 3 11 0 1 2 3 4 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 求哈夫曼編碼過(guò)程的實(shí)例 : HT數(shù)組 if(n=1) return。 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。c=f,f=HT[f].parent if(HT[f].lchild==c cd[start]=“0”。實(shí)現(xiàn)二叉樹(shù)遍歷的具體算法與所采用的存儲(chǔ)結(jié)構(gòu)有關(guān)。 7. 了解 最優(yōu)樹(shù)的特性 ，掌握 建立最優(yōu)樹(shù)和哈夫曼編碼 的方法。 層次遍歷 是按另一種搜索策略進(jìn)行的遍歷。 HC[i]=(char * )malloc((nstart)*sizeof(char))。HC, int *w,int n){ //從葉子到根逆向求每個(gè)字符的赫夫曼編碼 HC=(Huffmancode)malloc((n+1)*sizeof(char *))。 HT=(HuffmanTree)malloc((m+1)*sizeof(HTNode))。例如，可以為 A， B， C， D四個(gè)字符分別分配 0， 00， 1， 01，并可將上述電文用二進(jìn)制序列： 000011010發(fā)送，其長(zhǎng)度只有 9個(gè)二進(jìn)制位，但隨 之帶來(lái)了一個(gè)問(wèn)題，接收方接到這段電文后無(wú)法 進(jìn)行譯碼，因?yàn)闊o(wú)法斷定前面 4個(gè) 0是 4個(gè) A， 1個(gè) B、 2個(gè) A，還是 2個(gè) B，即譯碼不唯一，因此這種編碼 方法不可使用。在設(shè)計(jì)編碼時(shí)需要遵守兩個(gè)原則： （ 1）發(fā)送方傳輸?shù)亩M(jìn)制編碼，到接收方解碼后