【正文】 每一層的結(jié)點數(shù)都是上一層結(jié)點數(shù)的二倍。 2) 如果 2i≤n，則其左兒子結(jié)點編號為 2i；若 2in，則無左兒子結(jié)點。 圖 二叉樹的順序存儲結(jié)構(gòu) ?這種存儲結(jié)構(gòu)適用于完全二叉樹和滿二叉樹。 5可表示成： Lchild data Rchild Lchild data Parent Rchild A ∧ B ∧ E C ∧ D ∧ ∧ G ∧ ∧ F ∧ 結(jié)點定義 ?鏈式存儲結(jié)構(gòu)的結(jié)點定義如下： typedef struct BTnode { elementtype data。 這里的 elemeenttype可以是任何相應(yīng)的數(shù)據(jù)類型如 int、 float或 char等。 ?一個非空的二叉樹由根結(jié)點及左、右子樹這三個基本部分組成，因此若能依次遍歷這三部分，便是遍歷了整個二叉樹。 ? (3) 后序（ Postorder）遍歷 若遍歷的二叉樹為空，執(zhí)行空操作；否則依次執(zhí)行下列操作： 后序遍歷左子樹； 后序遍歷右子樹； 訪問根結(jié)點。 ○ B ○C ○ D ○ E ○ F ○ G ○ A ○ H ○ I 先序遍歷遞歸算法 void preorder(btree *BT) { if (BT！ =NULL) { printf(%d,BTdata)。 先序遍歷 非 遞歸算法 define maxsize 二叉樹的結(jié)點數(shù) void Nrpreorder(btree *BT) { btree *S[maxsize],*p。 /*若 P非空 ， 則進棧 */ top++。 p=s[top]。 inorder(BTRchild)。 while ((p!=null) || (top!=0)) { while(p!=null) { s[top]=p。 p=s[top]。 根據(jù)這一事實，可以對二叉樹按以上順序遍歷，之后顛倒過來即可。該標志與指針同時進出棧。 if (BT==null) return(0)。 else return(hight2+1)。 top=0。 s[top]=p。 /*取其左兒子 */ } If (levelmax) max=level。 /*退棧 p=prchild。 求二叉樹中，每層結(jié)點的個數(shù)。 線索二叉樹 (續(xù)） （以中序遍歷為例） 若結(jié)點的左指針為空，則存放其前驅(qū)結(jié)點；若結(jié)點的右指針為空，則存放其后繼結(jié)點。 ?增加線索標志后的結(jié)點結(jié)構(gòu)為： ? 其中 ， ltag=0， Lchild指向其左兒子 ltag=1， Lchild指向其前趨 rtag=0， rchild指向其右兒子 rtag=1， rchild指向其后繼 ?注意 指針 和 線索 的區(qū)別 lchild ltag data rtag rchild 結(jié)點類型和相應(yīng)結(jié)點的指針類型定義如下： typedef struct bithrnode { int ltag。 struct bithrnode *rchild。 ○ A ○ C ○ F ○ G ○ B ○ D ○ E ○ H ○ I 線索二叉樹的構(gòu)造 基本思想： 已知一棵二叉樹，使其線索化。 if( plchild== null) { plchild=pre。 p=bt。 p=plchild。 pltag=1 } if( prerchild== null) { prerchild=p。 if (prtag==1) return(prchild)。 } } 在 中序線索樹中求 前趨 結(jié)點 ?找前趨結(jié)點相應(yīng)的原則如下： 1) 如果某結(jié)點的 Ltag=1，說明其左指針域是線索，這個線索所指的即是該結(jié)點的前趨結(jié)點； 2) 如果某結(jié)點的 Ltag=0，則其左指針指向左兒子，它的前趨是該結(jié)點的左子樹最右下方的結(jié)點 . 在中序線索二叉樹中求前驅(qū)結(jié)點的算法 tbtree *pre (bithrtree *p) { bithrtree *q。 return(q)。 /*找最左下方的結(jié)點 */ do { print(“%c” ,pdate)。 在中序線索二叉樹中插入結(jié)點的算法 Bithrtree insert(bithrtree *thrt,*s,*t) { bithrtree *p。 /*S成為 T的前趨 */ Tlchild=s。 If (trtag==0) /*若 T有右兒子，則找它右子樹的 { while (pltag==0) /*最左下方的結(jié)點 p=plchild。 ? 由于同一樹的各結(jié)點度數(shù)一般并不相同，如按結(jié)點的度數(shù)給每個結(jié)點設(shè)置不同數(shù)目的指針域，不同結(jié)點的數(shù)據(jù)結(jié)構(gòu)不同，會給算法設(shè)計和程序編制造成困難。 樹 森林與二叉樹的轉(zhuǎn)換 雙親表示法： 每個結(jié)點除了信息字段外，另設(shè)一個指向其父親的字段。 孩子表示法： 每個結(jié)點除了信息字段外，還設(shè)若干個指針，每個指針指向一個兒子。 其中 degree為樹的度。 struct node *next。 ○ B ○ C ○ D ○ E ○ F ○ G ○ A ○ H ○ I ○ J ?由于樹根沒有兄弟，所以樹轉(zhuǎn)換為二叉樹后，二叉樹的根結(jié)點的右子樹必為空。 ? pl=0+1+1+2+2+2+2=10 ? pl=0+1+1+2+2+2+3=11 結(jié)點的權(quán) ：在許多實際應(yīng)用中，常常將樹中結(jié)點賦予一個有某種意義的實數(shù)，稱為該結(jié)點的權(quán)。 wpl最小的二叉樹稱為該二叉樹的 哈夫曼樹。 圖 哈夫曼算法過程 ?給定 4個數(shù)： 7， 5， 2， 4。 圖 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é)點起每輸入一個數(shù)碼即沿二叉樹下移一層，數(shù)碼為 0時移向左分支，數(shù)碼為 1時移向右分支，待達到葉子結(jié)點時即譯出一個字符，再輸入的數(shù)碼又從根結(jié)點開始重新做起。 ?下面討論求哈夫曼編碼的算法。 Typedef struct codetype { char bits[n]。 im。 } for(i=0。 im。 /*結(jié)點，它們在 ht[]中的序號為 ht[i]. lch=s1。 } 求哈夫曼樹 哈夫曼編碼算法 (續(xù)） for (i=0。 f=ht[k].parent。 k=f。 4 2 3 1 7 5 6 8 9 例 ?解 : 前序 : 9 中序 : 9 后序 : 1 例 ?設(shè)數(shù)據(jù)集合d={1,12,5,8,3,10,7,13,9},試依次取 d中各數(shù)據(jù)，構(gòu)造一棵二叉排序樹，并給出該二叉排序樹中序遍歷序列。 ?解：根據(jù)中序遍歷二叉樹的遞歸定義，轉(zhuǎn)換成非遞歸函數(shù)時，用一個棧保存返回的結(jié)點。 p=b。 } 例6.4算法續(xù) if (top0) { p=stack[top]。 /*掃描右子樹 */ } }while (top!=0)。 圖 二叉樹例子 ① ② ③ ④ ⑤ ⑥ ⑦ ⑧ ⑨ 6. 若二叉樹中各結(jié)點值均不相同。 8. 輸入一個正整數(shù)序列{55,34,18,88,119,11,76,9,97,99,46}，試構(gòu)造一個二叉排序樹。 2. 一個二叉樹以鏈式結(jié)構(gòu)存儲，寫出在二叉樹中查找值為 x的結(jié)點的算法。 返回