【正文】 形態(tài) ? (a) 空二叉樹 ? (b) 僅有一個(gè)根結(jié)點(diǎn)的二叉樹 ? (c) 右子樹為空的二叉樹 ? (d)左子樹為空的二叉樹 ? (e)左、右子樹均非空的二叉樹 ( a ) ○ A (b ) ○ B ○ A (c ) ○ B ○ A (d ) ○ B ○ A ○ C (e ) ?二叉樹的基本術(shù)語 . ?二叉樹的基本操作 二叉樹的性質(zhì) 性質(zhì) 1. 在二叉樹第 k 層上至多有 2k1個(gè)結(jié) 點(diǎn)。 樹中只有根結(jié)點(diǎn)無前趨，它是開始結(jié)點(diǎn)； 葉結(jié)點(diǎn)無后繼，它們是末端結(jié)點(diǎn)。其余各結(jié)點(diǎn)的層數(shù)逐層由上而下計(jì)算。 ? 6. 子孫 結(jié)點(diǎn)和 祖先 結(jié)點(diǎn)：一個(gè)結(jié)點(diǎn)的子樹中所有結(jié)點(diǎn)均稱之為該結(jié)點(diǎn)的子孫結(jié)點(diǎn)。 ? 0的結(jié)點(diǎn) (即沒有子樹的結(jié)點(diǎn) )叫作 末端結(jié)點(diǎn) 或 葉子結(jié)點(diǎn) ,其它結(jié)點(diǎn)稱為 內(nèi)部結(jié)點(diǎn) 。 ? 當(dāng) n=0時(shí)，稱為 空樹 。 ? 有限集合 T1， T2……T m “互不相交”，即任意兩個(gè)集合不能有相同的結(jié)點(diǎn)。 ? 3. 樹的度 ：一棵樹中各個(gè) 結(jié)點(diǎn)度數(shù)的最大值 叫做這個(gè)樹的度。反之，從根結(jié)點(diǎn)到達(dá)一個(gè)結(jié)點(diǎn)的路徑上的所有結(jié)點(diǎn)，都叫做該結(jié)點(diǎn)的祖先結(jié)點(diǎn)。一棵樹中結(jié)點(diǎn)的最大層數(shù)叫做此樹的 深度 或 高度 。 ?樹形結(jié)構(gòu)是非線性結(jié)構(gòu)。 性質(zhì) 2. 深度為 k 的二叉樹至多有 2k 1個(gè)結(jié) 點(diǎn)。 ?滿二叉樹的第一層有一個(gè)結(jié)點(diǎn)（即根結(jié)點(diǎn)），第二層有兩個(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)，無父結(jié)點(diǎn)；若i1，則其父結(jié)點(diǎn)編號(hào)為 ?i/2? 。 圖 下圖 。 也可以增加一個(gè)指向父親的指針，如下： 圖 6。 } BTree。 ?對(duì)于用順序法表示的二叉樹，各結(jié)點(diǎn)在數(shù)組中的編號(hào)很有規(guī)律，其遍歷較容易進(jìn)行，但對(duì)于用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)表示的二叉樹，進(jìn)行遍歷就復(fù)雜一些，故本節(jié)僅討論鏈?zhǔn)酱鎯?chǔ)形式的二叉樹遍歷過程。 ? (2) 先序（ Preorder）遍歷 若遍歷的二叉樹為空，執(zhí)行空操作；否則依次執(zhí)行下列操作： 訪問根結(jié)點(diǎn)； 先序遍歷左子樹； 先序遍歷右子樹。 ?后序遍歷序列：H， I， D， E， B，F(xiàn)， G， C， A。 } } 先序遍歷 非 遞歸算法 ?基本思想 ： 先訪問根結(jié)點(diǎn)，并進(jìn)棧，再訪問左兒子，并進(jìn)棧 , …… , 直到左兒子為空； 退棧，并訪問其右兒子 , …… ； 重復(fù)以上過程，?？諡橹?。 while ((p!=null)||(top!=0) { while(p!=null) { s[top]=p。 /*取其左兒子 */ } 先序遍歷 非 遞歸算法（續(xù)） if (top!=0) { top。 printf(%d,BTdata)。 p=bt。 /*取其左兒子 */ } 中序遍歷 非 遞歸算法（續(xù)） if (top!=0) { top。 /*取其右兒子 */ } } } 后序遍歷 方法 1: 按照 先根、右子樹、左子樹的順序遍歷二叉樹，得到的結(jié)果與后序遍歷的結(jié)果相反。 所以，要設(shè)一個(gè)標(biāo)志 flag, 以記住是第 1次進(jìn)棧還是第 2次進(jìn)棧。 hight2。 if (hight1hight2) return(hight1+1)。 /*L[]記錄 S[]中元素對(duì)應(yīng)的層號(hào) int L[ ]。 while ((p!=null) || (top!=0)) { while(p!=null) { level++。 p=plchild。 level=L[top]。 二叉鏈表存儲(chǔ)的二叉樹的層次遍歷算法。 ?以二叉鏈表作為存儲(chǔ)結(jié)構(gòu)時(shí)，只能找到其左右兒子，而不能直接找到它的前趨或后繼； ?另一方面，對(duì)有 n個(gè)結(jié)點(diǎn)的二叉鏈表，有 n+1個(gè)指針域是空的，能否利用這些空指針域來存儲(chǔ)結(jié)點(diǎn)的前趨或后繼呢？ ?艾 .（ ）和查 .桑頓（ ） 提出了巧妙地利用這些空鏈的方法。 ?以 中序遍歷 為例介紹二叉樹的線索化 基本思想： 若結(jié)點(diǎn)有左兒子，則其 lchild指向其左兒子；否則，令 lchild指向其前趨結(jié)點(diǎn)； 若結(jié)點(diǎn)有右兒子，則其 rchild指向其右兒子；否則，令 rchild指向其后繼結(jié)點(diǎn)； 在每個(gè)結(jié)點(diǎn)中增加兩個(gè)標(biāo)志，即左線索標(biāo)志ltag，右線索標(biāo)志 rtag, 以區(qū)別是線索和兒子。 struct bithrnode *lchild。圖中的虛線箭頭即為新加上的線索。 （以中序遍歷），在遍歷算法的輸出語句處加入下列語句即可。 /*定義棧 S[ ],中間變量 P*/ int top=0。 /*若 P非空 ， 則進(jìn)棧 */ top++。 /*退棧至 P中 */ if( plchild== null) { plchild=pre。 /*取其右兒子 */ } } } 中序線索樹求 后繼 結(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。 return(q)。 while(qRtag==0) q=qRchild。 中序遍歷子線索二叉樹非遞歸算法 void thinorder(bithrtree *p) { if (p!=NULL) /*樹非空 */ { while(pltag==0) p=plchild。 } } 返回 在中序線索二叉樹中插入結(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。 /*成為 T的后繼 Tltag=1。 在中序線索二叉樹中插入結(jié)點(diǎn)的算法（續(xù)） P=trchild。 /*指向其前趨 T } ?插入結(jié)點(diǎn) T, 使其成為 S 的左兒子 樹 森林與二叉樹的轉(zhuǎn)換 普通樹可用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)來表示，每個(gè)結(jié)點(diǎn)包括數(shù)據(jù)域以及指向它各個(gè)兒子結(jié)點(diǎn)的指針域。 ? 按照一定的原則將普通樹用二叉樹來表示，是較好的表示方法。 }ptreeType。 }CtreeType。 struct node *son。 圖 樹轉(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)橄旅嫠镜亩鏄洹? 樹的路徑長(zhǎng)度 ：從根到每一結(jié)點(diǎn)的路徑 長(zhǎng)度之和，一般記作 pl。 ???niii lww p l1?給定 n個(gè)實(shí)數(shù)，以它們作為 n個(gè)葉子結(jié)點(diǎn)的權(quán)，可構(gòu)成多個(gè)不同的有 n個(gè)葉子結(jié)點(diǎn)的二叉樹，這些二叉樹的帶權(quán)路徑長(zhǎng)度wpl可能不同。如此重復(fù)進(jìn)行下去，直到構(gòu)成一個(gè)二叉樹為止，即得到哈夫曼樹。用頻度 {1， 2， 3， 3， 4}為權(quán)生成哈夫曼樹，并在每個(gè)葉結(jié)點(diǎn)上注明對(duì)應(yīng)的字符。 返回 可以看出：任一個(gè)字符的編碼都不是另一個(gè)字符編碼的前綴，這樣的編碼稱作 前綴編碼 。 } HuffmanTree。 求哈夫曼樹 哈夫曼編碼算法 Void Huffmancode(int w[], HuffmanTree ht[], Hcode hcd[]) /*w存放 n個(gè)字符的權(quán)， ht[]表示 huffman樹，