【正文】 E C I K J 70 由遍歷序列確定二叉樹 由 中序 和 后序 序列恢復(fù)二叉樹 中序序列： D C B G E A H F I J K 后序序列： D C E G B F H K J I A A 練習(xí)： I J K H F B G E C D 71 樹、森林和二叉數(shù)的關(guān)系及轉(zhuǎn)換 1. 樹和森林的表示方法 2. 樹、森林和二叉樹的轉(zhuǎn)換 72 樹的三種存儲(chǔ)結(jié)構(gòu) 一、 雙親表示法 二、 孩子鏈表表示法 三、 樹的二叉鏈表 (孩子 兄弟） 存儲(chǔ)表示法 1. 樹和森林的表示方法 73 A B C D E F G 0 A 1 1 B 0 2 C 0 3 D 0 4 E 2 5 F 2 6 G 5 data parent 一、雙親表示法 : 結(jié)點(diǎn)結(jié)構(gòu) : data parent 74 用一組連續(xù)的空間來存儲(chǔ)樹中的結(jié)點(diǎn)，每個(gè)結(jié)點(diǎn)附設(shè)一個(gè)指示器指示其雙親結(jié)點(diǎn)在表中的位置，其結(jié)點(diǎn)的結(jié)構(gòu)如下： 雙親表示法的優(yōu)點(diǎn)： 利用了樹中每個(gè)結(jié)點(diǎn)（根結(jié)點(diǎn)除外）只有一個(gè)雙親結(jié)點(diǎn)的性質(zhì)，使得查找某個(gè)結(jié)點(diǎn)的雙親結(jié)點(diǎn)非常容易。 結(jié)點(diǎn)結(jié)構(gòu) : firstchild data nextsibling 三、樹的二叉鏈表 (孩子 兄弟）存儲(chǔ)表示法 孩子兄弟表示法 又稱 二叉鏈表表示法 ，表中每個(gè)結(jié)點(diǎn)設(shè)有兩個(gè)鏈域，分別指向該結(jié)點(diǎn)的第一個(gè)孩子結(jié)點(diǎn)和下一個(gè)兄弟（右兄弟）結(jié)點(diǎn)。 歸整化 ：將圖形歸整化，使各結(jié)點(diǎn) 按層次 排列且將加上去的虛線變成實(shí)線。 A B D C F E G H I J G H I J A B C D E F 90 哈夫曼樹與哈夫曼編碼 ?哈夫曼樹的定義 ?如何構(gòu)造最優(yōu)樹 ?前綴編碼 91 哈夫曼樹 哈夫曼樹最典型、最廣泛的應(yīng)用是在編碼技術(shù)上，利用哈夫曼樹，可以得到平均長(zhǎng)度最短的編碼。 結(jié)點(diǎn)的權(quán)： 給樹中每個(gè)結(jié)點(diǎn)賦予一個(gè)具有實(shí)際意義的數(shù)值，我們稱該數(shù)值為這個(gè)結(jié)點(diǎn)的權(quán)。 weight parent Lchild Rchild 權(quán)值 雙親序號(hào) 左孩子序號(hào) 右孩子序號(hào) 100 靜態(tài)三叉鏈表結(jié)構(gòu)定義 define N 20 define M 2*N1 typedef struct { int weight 。i=n。i++) /*分支結(jié)點(diǎn)初始化 */ { ht[i].weight=0。s2)。 /*m2存放 次小權(quán)值 ,s2是 m2在數(shù)組的 下標(biāo) */ for(j=1。 } else if(ht[j].weightm2 amp。 107 哈夫曼編碼 : 對(duì) 哈夫曼樹 中每個(gè)左分支賦予 0，右分支賦予 1，則從根到每個(gè)葉子的路徑上，各分支的值構(gòu)成該葉子的 哈夫曼編碼。 設(shè) w={5,29,7, 8, 14, 23, 3, 11} 3 5 8 ,8} 7 8 15 ,15} 11 19 ,19} 14 29 ,29} 23 42 ,42} 29 58 ,58} 100 ,100} 0 1 0 1 0 1 0 1 0 1 0 1 0 1 10 110 1110 1111 01 001 0000 0001 哈夫曼編碼應(yīng)用舉例 哈夫曼編碼算法 利用哈夫曼樹求編碼時(shí)，編碼是由后向前生成的，需要走一條從葉子到根的路徑： 當(dāng)前結(jié)點(diǎn)若是其雙親的左子樹時(shí)，則置當(dāng)前編碼位為 0，否則置為 1。 用字符出現(xiàn)的頻率 (Pi)為權(quán)值構(gòu)造哈夫曼樹 ,并以此來構(gòu)造字符的哈夫曼編碼，由于哈夫曼樹的 WPL最?。? 所以傳輸?shù)膱?bào)文長(zhǎng)度： 必定最小。 前綴碼： 同一字符集中任何一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴（最左子串） 。 *s1=j。 } 4. 哈夫曼算法的實(shí)現(xiàn) —?jiǎng)?chuàng)建哈夫曼樹 2 3 5 105 4. Huffman算法實(shí)現(xiàn) —選擇函數(shù) define MAXINT 32767 select(HuffmanTree ht, int pos, int *s1, int *s2 ) { int j , m1, m2。i++) { select(ht,i1,amp。 for(i=n+1。 102 i i s2 i i s1 s1 s2 s1 s2 5 7 3 2 8 F: 2 3 5 5 7 8 15 10 5 10 15 25 25 1 2 3 4 5 6 7 8 9 √ √ √ √ √ √ √ √ 9 8 7 6 5 4 3 2 1 RChild LChild parent weight 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 2 0 0 0 3 0 0 0 7 0 0 0 5 87 25 5 2 9 15 6 1 9 10 3 4 7 5 8 6 6 8 7 4. 哈夫曼算法的實(shí)現(xiàn) —?jiǎng)?chuàng)建哈夫曼樹 s1 s2 葉子結(jié)點(diǎn) 分支結(jié)點(diǎn) 初始化完畢 選擇、合并 n1次 直至只含一棵樹為止 4. 哈夫曼算法的實(shí)現(xiàn) —?jiǎng)?chuàng)建哈夫曼樹 void CrtHuffmanTree(HuffmanTree ht,int w[ ],int n) { int i, j ,k , s1 , s2。 98 例如 : 已知權(quán)值 W={ 5, 6, 2, 9, 7 } 9 5 6 2 7 5 2 7 6 9 7 6 7 13 9 5 2 7 構(gòu)造哈夫曼樹如下： 9 5 2 7 16 6 7 13 29 哈夫曼算法的實(shí)現(xiàn) n個(gè)葉子結(jié)點(diǎn) 的哈夫曼樹共有 2n1個(gè)結(jié)點(diǎn) ,因此可用有 2n1個(gè)元素的 數(shù)組 來存儲(chǔ)哈夫曼樹 , 結(jié)點(diǎn)間的 關(guān)系用游標(biāo)表示 ，即采用 靜態(tài)鏈表 來存儲(chǔ)哈夫曼樹。 a 例： PL(a)=1+1+2+2+2+2=10 b PL(b)=1+1+2+2+3+3=12 一、基本概念： 93 帶權(quán)路徑長(zhǎng)度： 在樹形結(jié)構(gòu)中，我們把從樹根到某一結(jié)點(diǎn)的路徑長(zhǎng)度與該結(jié)點(diǎn)權(quán)的乘積，稱做該結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度。 89 二叉樹 → 森林 舉例： 抹線： 將 二叉樹的根結(jié)點(diǎn) 與其右孩子 i的連線當(dāng)且僅當(dāng)連續(xù)地沿著 i的 右鏈 不斷搜索到的所有右孩子間的連線全部抹掉 ,這樣得到若干棵孤立的二叉樹。 84 森林轉(zhuǎn)化成二叉樹 ① 將森林中的每棵樹轉(zhuǎn)換成對(duì)應(yīng)的二叉樹； ② 按照給出的森林中樹的次序，依次將 后一棵 二叉樹插入 為前一棵 二叉樹根結(jié)點(diǎn) 的右子樹 ； 85 森林 → 二叉樹 舉例： 將森林中的每棵樹轉(zhuǎn)換成對(duì)應(yīng)的二叉樹； 按照給出的森林中樹的次序，依次將 后一棵二叉樹插入 為前一棵 二叉樹根結(jié)點(diǎn) 的右子樹 ； G H I J A B C D E F A B D C F E G H I J A B D C F E G H I J 86 二叉樹轉(zhuǎn)化成樹 前提：二叉樹的根結(jié)點(diǎn) 無右孩子 加線 ：若某結(jié)點(diǎn) i是雙親結(jié)點(diǎn)的左孩子，則將該結(jié)點(diǎn)的右孩子以及連續(xù)地沿著此右孩子的 右鏈 不斷搜索到的所有右孩子都分別與結(jié)點(diǎn) i的 雙親用虛線連起來 。 struct CSNode *firstchild, *nextsibling。 對(duì) 左子樹 及 右子樹 仍可按此方式進(jìn)一步分解 . 依次類推，便可遞歸得到整棵二叉樹。 if (ch==??) return NULL。 } return depthval。} return (LeafCount)。 Int leaf (BiTree root) { int LeafCount,L,R。 /* 先序遍歷右子樹 */ } } 54 統(tǒng)計(jì)二叉樹中葉子結(jié)點(diǎn)的個(gè)數(shù) 算法基本思想 : 先序 (或中序或后序 )遍歷二叉樹，在遍歷過程中查找葉子結(jié)點(diǎn)，并計(jì)數(shù)。 Preorder(rootlchild)。