【正文】 8. 輸入一個(gè)正整數(shù)序列{55,34,18,88,119,11,76,9,97,99,46}，試構(gòu)造一個(gè)二叉排序樹。 p=b。 f=ht[k].parent。 } for(i=0。 圖 Huffman編碼樹 C S T _ A 000 001 01 10 11 0 13 ① ② ③ ④ ⑥ ⑦ ③ ③ 0 0 0 1 1 1 1 C S T _ A 000 001 01 10 11 ?從根結(jié)點(diǎn)起每輸入一個(gè)數(shù)碼即沿二叉樹下移一層，數(shù)碼為 0時(shí)移向左分支，數(shù)碼為 1時(shí)移向右分支，待達(dá)到葉子結(jié)點(diǎn)時(shí)即譯出一個(gè)字符，再輸入的數(shù)碼又從根結(jié)點(diǎn)開始重新做起。 ○ B ○ C ○ D ○ E ○ F ○ G ○ A ○ H ○ I ○ J ?由于樹根沒有兄弟，所以樹轉(zhuǎn)換為二叉樹后，二叉樹的根結(jié)點(diǎn)的右子樹必為空。 樹 森林與二叉樹的轉(zhuǎn)換 雙親表示法： 每個(gè)結(jié)點(diǎn)除了信息字段外，另設(shè)一個(gè)指向其父親的字段。 在中序線索二叉樹中插入結(jié)點(diǎn)的算法 Bithrtree insert(bithrtree *thrt,*s,*t) { bithrtree *p。 if (prtag==1) return(prchild)。 if( plchild== null) { plchild=pre。 線索二叉樹 (續(xù)） （以中序遍歷為例） 若結(jié)點(diǎn)的左指針為空，則存放其前驅(qū)結(jié)點(diǎn)；若結(jié)點(diǎn)的右指針為空，則存放其后繼結(jié)點(diǎn)。 s[top]=p。該標(biāo)志與指針同時(shí)進(jìn)出棧。 inorder(BTRchild)。 ○ B ○C ○ D ○ E ○ F ○ G ○ A ○ H ○ I 先序遍歷遞歸算法 void preorder(btree *BT) { if (BT！ =NULL) { printf(%d,BTdata)。 5可表示成： Lchild data Rchild Lchild data Parent Rchild A ∧ B ∧ E C ∧ D ∧ ∧ G ∧ ∧ F ∧ 結(jié)點(diǎn)定義 ?鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)的結(jié)點(diǎn)定義如下： typedef struct BTnode { elementtype data。（ k=1) . 性質(zhì) 3. 對任一二叉樹 BT，若其末端結(jié)點(diǎn)數(shù)為 n0，度為 2的結(jié)點(diǎn)數(shù)為 n2，則 n0=n2+1 證 : 設(shè)二叉樹有 n個(gè)結(jié)點(diǎn) , 度為 1的結(jié)點(diǎn)數(shù)為 n1, 則 n = n0+n1+n2 。 ? 4. 兒子結(jié)點(diǎn) 和 父親結(jié)點(diǎn) ：一個(gè)結(jié)點(diǎn)的 子樹的根 或者 后繼結(jié)點(diǎn) 稱為該結(jié)點(diǎn)的 兒子結(jié)點(diǎn)，反之，該結(jié)點(diǎn)則稱為其后繼結(jié)點(diǎn)的 父親 結(jié)點(diǎn)。 ? 5. 兄弟 結(jié)點(diǎn)：同一個(gè)結(jié)點(diǎn)的兒子結(jié)點(diǎn)之間互稱為兄弟結(jié)點(diǎn)。 另一方面 , 度為 1的結(jié)點(diǎn)有 1個(gè)兒子 , 度為 2的結(jié)點(diǎn)有 2個(gè)兒子 , 故二叉樹中兒子總數(shù) (除根結(jié)點(diǎn)外 )為 n1+2*n2, 所以二叉樹的結(jié)點(diǎn)總數(shù)又可表示成 n=n1+2*n2+1 所以 n0=n2+1 滿二叉樹 ?在一個(gè)二叉樹中，若第 I 層的結(jié)點(diǎn)數(shù)為 2i1，則稱該層的結(jié)點(diǎn)數(shù)是滿的，當(dāng)樹中的每一層都是滿的，則稱此二叉樹為 滿二叉樹。 struct BTnode *Lchild。 preorder(BTlchild)。 } } 中序遍歷 非 遞歸算法 void Nrinorder(btree *BT) { btree *S[maxsize],*p。 取左兒子時(shí)， flag=0 取右兒子時(shí)， flag=1 在第二次出棧時(shí)訪問該結(jié)點(diǎn)。 L[top]=level。用這種方法構(gòu)造的二叉樹叫 線索二叉樹。 pltag=1 } if( prerchild== null) { prerchild=p。 /*由后繼線索得到 */ else { q=prchild。 Trtag=srtag。 Typedef struct node { elementtype data。 森林轉(zhuǎn)換成二叉樹 ?森林 : 樹的集合 ?轉(zhuǎn)換方法 : 1. 先把森林中的每棵樹轉(zhuǎn)換成二樹 F={ T1, T2,……, T m} 2. 若 m=0, 則森林 F為空 , 那么對應(yīng)的二叉 樹為空樹 . 3. 若 m≠0, 則 F對應(yīng)的二叉樹的根為 T1的根 , 左子樹為 T1去掉根后剩余部分 , 右子樹為 F?={T2,……, T m}轉(zhuǎn)換而成的二叉樹 . 例 : ?二叉樹轉(zhuǎn)換成森林 例 樹的遍歷 ?先根遍歷 : 先訪問根 , 然后依次先根遍歷樹的每一棵子樹 . ?后根遍歷 : 先依次后根遍歷樹的每一棵子樹 , 然后訪問根 . 例 : 森林的遍歷 ? 先序遍歷 : 1. 訪問森林的第一棵樹的根結(jié)點(diǎn) , 2. 先序遍歷第一棵樹中根結(jié)點(diǎn)的子樹 , 3. 先序遍歷去掉第一棵樹之后的剩余部分 . 例 ? 后序遍歷 哈夫曼樹及其應(yīng)用 ? 1. 哈夫曼樹基本術(shù)語： 路徑 ：從樹中一個(gè)結(jié)點(diǎn)到另一個(gè)結(jié)點(diǎn)之 間的邊構(gòu)成的通路。 ?將此二叉樹與相應(yīng)的編碼方式對照可以發(fā)現(xiàn)，每個(gè)葉子結(jié)點(diǎn)至根的路徑長度即等于該葉子結(jié)點(diǎn)所代表字符的編碼位數(shù)。 in。 /*f是 K的父親 while (f != 1) /*若 f=1，則一個(gè)字符個(gè)編碼已經(jīng)結(jié)束 { hcd [i]. start 。 do { while(p!=NULL) /*掃描左結(jié)點(diǎn) */ { top++。 9. 有一份電文中共使用 5個(gè)字符： a、 b、 c、 d、 e，它們的出現(xiàn)頻率依次為 4。 7. 一個(gè)二叉樹如圖 ,分別寫出其前序、中序、后序的遍歷序列。 int top=0。 /*從 n起遞減 */ k=i。 ht[i].rch]=1。用頻度 {1， 2， 3， 3， 4}為權(quán)生成哈夫曼樹，并在每個(gè)葉結(jié)點(diǎn)上注明對應(yīng)的字符。 圖 樹轉(zhuǎn)化為二叉樹 ○ B ○ C ○ D ○ E ○ F ○ G ○ A ○ H ○ I ○ J ?圖 樹轉(zhuǎn)化為二叉樹 ○ B ○ C ○ D ○ E ○ F ○ G ○ A ○ H ○ I ○ J 得到的已是一棵二叉樹，若按順時(shí)針方向?qū)⑺D(zhuǎn)就更清楚地變?yōu)橄旅嫠镜亩鏄洹? ? 按照一定的原則將普通樹用二叉樹來表示，是較好的表示方法。 } } 返回 在中序線索二叉樹中插入結(jié)點(diǎn) 插入結(jié)點(diǎn) T, 使其成為 S 的右兒子 . 插入過程： 1. 若 S的右子樹為空，則 T為 S的右兒子， S的后繼為 T的后繼， S成為 T的前趨； 2. 若 S的右子樹為非空，則當(dāng) T插入后， S 的右子樹成為 T的右子樹， S為 T的前 趨， S原來的后繼中的 lchild指針改為 T。 /*取其右兒子 */ } } } 中序線索樹求 后繼 結(jié)點(diǎn) ?在中序遍歷線索樹過程中，按下述兩條原則即可找到后繼結(jié)點(diǎn)： 1) 如果結(jié)點(diǎn)的 rtag=1，說明其右指針域是線索，這個(gè)線索所指的即是該結(jié)點(diǎn)的后繼結(jié)點(diǎn)； 2) 如果結(jié)點(diǎn)的 rtag=0，則其右指針指向的是右兒子 , 其后繼是其右子樹最左下方的結(jié)點(diǎn) . 中序線索二叉樹求 后繼 算法 tbtree *next (bithrtree *p) { bithrtree *q。 （以中序遍歷），在遍歷算法的輸出語句處加入下列語句即可。 ?以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到其左右兒子，而不能直接找到它的前趨或后繼； ?另一方面，對有 n個(gè)結(jié)點(diǎn)的二叉鏈表，有 n+1個(gè)指針域是空的，能否利用這些空指針域來存儲(chǔ)結(jié)點(diǎn)的前趨或后繼呢？ ?艾 .（ ）和查 .桑頓（ ） 提出了巧妙地利用這些空鏈的方法。 whi