【正文】 NULL) { inorder(BTlchild)。 p=plchild。 后序遍歷時(shí)，每個(gè)結(jié)點(diǎn)要 2次進(jìn)棧，也就是說，每個(gè)結(jié)點(diǎn)要進(jìn) 2次，出 2次。 hight2=BTreeheight(btreerchild)。 level=0。 p=s[top]。 線索二叉樹 ?從上節(jié)可知：遍歷二叉樹就是按一定規(guī)則將二叉樹中的結(jié)點(diǎn)排列成一個(gè)線性序列，把一個(gè)非線性結(jié)構(gòu)線性化。 elementtype data。 為了記下遍歷過程中訪問結(jié)點(diǎn)的先后次序，附設(shè)兩個(gè)指針： pre指向 剛訪問過 的結(jié)點(diǎn) , p指向 正在訪問的 結(jié)點(diǎn)。 while ((p!=null) || (top!=0)） { while(p!=null) { s[top]=p。 p=prchild。 else { q=pLchild。 }while(p!=NULL)。 /*T成為 S的右子樹 */ Srchild=t。這樣較浪費(fèi)存儲(chǔ)空間。 struct node *sptr[degree]。 2. 樹轉(zhuǎn)換成二叉樹 具體方法如下： 1) 在所有兄弟結(jié)點(diǎn)之間加一連線； 2) 對(duì)每個(gè)結(jié)點(diǎn)，除了保留與其左兒子結(jié)點(diǎn)的連線外，去掉該結(jié)點(diǎn)與其它兒子結(jié)點(diǎn)的連線。 樹的帶權(quán)路徑長(zhǎng)度： 樹中所有葉子結(jié)點(diǎn)的帶權(quán)路徑長(zhǎng)度之和，通常記為： 其中 n表示葉子結(jié)點(diǎn)個(gè)數(shù)， wi和 li分別表示葉子結(jié)點(diǎn) ki的權(quán)值和根到 ki之間的路徑長(zhǎng)度。 ?設(shè)有一段電文“ CAST_TAT_A_AS”，統(tǒng)計(jì)電文中字母的頻度 f(?C?)=1， f(?S?)=2， f=(?T?)=3，f=(?_?)=3， f=(?A?)=4。 我們用大小為 2n1的向量作為哈夫曼樹的存儲(chǔ)結(jié)構(gòu)，由于在構(gòu)成哈夫曼樹之后，為求編碼需走一條從葉子結(jié)點(diǎn)到根結(jié)點(diǎn)的路徑，而譯碼需走一條從根到葉子結(jié)點(diǎn)的路徑，所一對(duì)每一結(jié)點(diǎn)而言，既要知道其父親的信息，又要知道其兒子的信息 ，因此結(jié)點(diǎn)定義如下： define n 字符個(gè)數(shù) define m 樹中結(jié)點(diǎn)數(shù)目 /*m=2n1*/ Typedef struct nodetype { int weight, parent, lch, rch。 ht[i].lch=1。 /*在 ht[k]（ 0=k=i1)中，選擇兩 ht[s1].parent=i。 i++) /*求哈夫曼編碼 */ { hcd[i]. start=n。 /*繼續(xù)向上找，直到根 } } } ?例：已知某系統(tǒng)在通迅中只出現(xiàn) 8個(gè)字符，其頻率為 , , , , , , , . 試設(shè)計(jì)哈夫曼編碼。 例6.4算法 void inorder (btree *b) { btree stack[m0], *p。 printf(“%d”,pdata)。 2)已知一個(gè)二叉樹的前序和中序分別為ABCDEFGH和 BDCEAFHG，請(qǐng)畫出此二叉樹。 4. 假設(shè)二叉排序樹 t的各元素值均不相同，設(shè)計(jì)一個(gè)算法按遞增次序打印各元素值。試畫出對(duì)應(yīng)的哈夫曼樹，并求出每個(gè)字符的哈夫曼編碼。 3. 高度為 h的完全二叉樹至少有多少個(gè)結(jié)點(diǎn)？最多有多少個(gè)結(jié)點(diǎn)？ 4. 采用順序存儲(chǔ)方法和鏈?zhǔn)酱鎯?chǔ)方法分別畫出圖。 stack[top]=p。 12 1 5 13 8 3 10 7 9 例 ?假設(shè)用于通信的電文由字符集 {a， b， c，d， e， f， g， h}中的字母構(gòu)成，這 8個(gè)字母在電文中出現(xiàn)的概率分別為{,}試為這 8個(gè)字母設(shè)計(jì)哈夫曼編碼。 If (ht[f]. lch==k) /*判斷 k是 f的左兒子 ? 右兒子 ? hcd[i]. bits [hcd [i]. start]=?0?。 ht[i]. rch]=s2。 i++) /*初始化 */ ht[i].weight=w[i]。 }Hcode。由于將每種字符出現(xiàn)的次數(shù)作為對(duì)應(yīng)葉子結(jié)點(diǎn)的權(quán)，則計(jì)算出的帶權(quán)路徑長(zhǎng)度 wpl即為整個(gè)字符串的編碼長(zhǎng)度。 ⑦ ⑤ ④ ② wpl=36 圖 不同 wpl的二叉樹 wpl=46 ② ④ ⑤ ⑦ ② ④ ⑦ ⑤ wpl=35 2. 哈夫曼樹的構(gòu)造算法 ?將 n個(gè)權(quán)值 {w1， w2， … ， wn}按遞增次序排列，設(shè)其順序?yàn)?w1， w2， … ， wn，取出最小的兩個(gè)w1和 w2，分別作為根結(jié)點(diǎn)的左、右兒子結(jié)點(diǎn)的權(quán)組成一個(gè)二叉樹，并認(rèn)為其根結(jié)點(diǎn)的權(quán)w12=w1+w2； ?將 w12按其數(shù)值大小插入到 w3至 wn之間，使數(shù)值仍保持為遞增的次序； ?再取出最小的兩個(gè)作為根的左、右兒子的權(quán)組成二叉樹，也令根的權(quán)等于此兩數(shù)值之和，并同樣將此根結(jié)點(diǎn)按權(quán)值大小插入到剩下的數(shù)據(jù)中，保持?jǐn)?shù)值的遞增次序。 路徑長(zhǎng)度 ：路徑上邊的數(shù)目。 Typedef struct node { elementtype data。 struct node *parent。 /*最左下方的結(jié)點(diǎn)的 lchild return(thrt)。 /*S的后繼 Trchild=srchild。 ?由此結(jié)點(diǎn)開始，反復(fù)進(jìn)行尋找后繼結(jié)點(diǎn)的過程，并訪問這些結(jié)點(diǎn)，直至結(jié)束。 while(qltag==0) q=qlchild。 p=s[top]。 prertag=1} 以中序?yàn)槔?構(gòu)造 線索二叉樹算法 void Nrinorder(bithrtree *BT) { bithrtree *S[maxsize],*p,*pre。 圖 中序線索樹 ?與圖 示二叉樹對(duì)應(yīng)的中序線索樹如左圖所示。 把一個(gè)二叉樹變成一個(gè)線索二叉樹的過程叫作二叉樹的線索化。 } 求二叉樹葉子結(jié)點(diǎn)的個(gè)數(shù)。 /*進(jìn)棧 top++。 /*定義棧 S[ ],中間變量 P */ p=bt。 例：求二叉樹深度的 遞歸算法 int BTreeheight(Btree *BT) { int hight1。 p=prchild。 /*定義棧 S[ ],中間變量 P */ int top=0。 /*輸出 p=plchild。 preorder(BTRchild)。 ?三種遍歷次序以遞歸的形式定義： ? (1) 中序（ Inorder）遍歷 若遍歷的二叉樹為空，執(zhí)行空操作；否則依次執(zhí)行下列操作： 中序遍歷左子樹； 訪問根結(jié)點(diǎn)； 中序遍歷右子樹。 struct BTnode *Rchild。 例 : 二叉樹的存儲(chǔ)結(jié)構(gòu) 1. 二叉樹的 順序存儲(chǔ)結(jié)構(gòu)： 對(duì)于滿二叉樹和完全二叉樹來說，可以采用“以編號(hào)為地址”的方法，將編號(hào)為 i的結(jié)點(diǎn)存入一維數(shù)組的第 i個(gè)單元。 ?例 ?如果一個(gè)二叉樹中，除最下一層的各結(jié)點(diǎn)度數(shù)為 0以外，其它各層結(jié)點(diǎn)的度數(shù)均等于 2，則此二叉樹為滿二叉樹。 樹中只有根結(jié)點(diǎn)無(wú)前趨，它是開始結(jié)點(diǎn)； 葉結(jié)點(diǎn)無(wú)后繼，它們是末端結(jié)點(diǎn)。 ? 6. 子孫 結(jié)點(diǎn)和 祖先 結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的子樹中所有結(jié)點(diǎn)均稱之為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。 ? 當(dāng) n=0時(shí)，稱為 空樹 。 ? 3. 樹的度 ：一棵樹中各個(gè) 結(jié)點(diǎn)度數(shù)的最大值 叫做這個(gè)樹的度。一棵樹中結(jié)點(diǎn)的最大層數(shù)叫做此樹的 深度 或 高度 。 性質(zhì) 2. 深度為 k 的二叉樹至多有 2k 1個(gè)結(jié) 點(diǎn)。 性質(zhì) 5. 把一棵 n的結(jié)點(diǎn)的完全二叉樹 , 按層編號(hào) , 則編號(hào)為 i 的結(jié)點(diǎn)滿足： 1) 如果 i=1，則它是整個(gè)樹的根結(jié)點(diǎn)，無(wú)父結(jié)點(diǎn)；若i1，則其父結(jié)點(diǎn)編號(hào)為 ?i/2? 。 也可以增加一個(gè)指向父親的指針，如下： 圖 6。 ?對(duì)于用順序法表示的二叉樹，各結(jié)點(diǎn)在數(shù)組中的編號(hào)很有規(guī)律，其遍歷較容易進(jìn)行，但對(duì)于用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的二叉樹，進(jìn)行遍歷就復(fù)雜一些，故本節(jié)僅討論鏈?zhǔn)酱鎯?chǔ)形式的二叉樹遍歷過程。 ?后序遍歷序列：H， I， D， E， B，F(xiàn)， G， C， A。 while ((p!=null)||(top!=0) { while(p!=null) { s[top]=p。 printf(%d,BTdata)。 /*取其左兒子 */