【正文】 ) 對(duì) 應(yīng) 的 二 叉 樹圖 68 森林和對(duì)應(yīng)的二叉樹 １ ． 樹與二叉樹的對(duì)應(yīng)關(guān)系 樹與二叉樹均可用二叉鏈表作為存儲(chǔ)結(jié)構(gòu)，因此給定一棵樹，用二叉鏈表存儲(chǔ)，可唯一對(duì)應(yīng)一棵二叉樹，反之亦然。 (1) 前序遍歷森林 若森林非空，則： 訪問森林中第一棵樹的根結(jié)點(diǎn)； 前序遍歷第一棵樹中根結(jié)點(diǎn)的各子樹所構(gòu)成的森林 前序遍歷去掉第一棵樹外其它樹構(gòu)成的森林。 當(dāng)用二叉鏈表作為樹和森林的存儲(chǔ)結(jié)構(gòu)時(shí)，樹和森林的前序遍歷和后序遍歷可用二叉樹的前序遍歷和中序遍歷算法來實(shí)現(xiàn)。 (1) 前序遍歷森林 若森林非空，則： 訪問森林中第一棵樹的根結(jié)點(diǎn)； 前序遍歷第一棵樹中根結(jié)點(diǎn)的各子樹所構(gòu)成的森林 前序遍歷去掉第一棵樹外其它樹構(gòu)成的森林。i++) preorder(roott[i])。 //訪問根結(jié)點(diǎn) for(i=0。（ 將介紹二叉樹） ② 后序遍歷樹恰好等價(jià)于中序遍歷該樹所對(duì)應(yīng)的二叉樹。對(duì)圖 66 (a)中的樹進(jìn)行按層次遍歷得到樹的廣度優(yōu)先遍歷序列為： ABCDEFG。 (2) 后序遍歷的遞歸定義： 若樹 T非空，則： 按照從左到右的順序依次后序遍歷根 T的各子樹 Tl， T2， … ， Tk； 訪問根結(jié)點(diǎn) R。深度優(yōu)先遍歷通常有兩種方式： 前序 遍歷和 后序 遍歷。也就是把非線性結(jié)構(gòu)的樹結(jié)點(diǎn)變成線性序列的一種方式 。 //根結(jié)點(diǎn)右線索化 rootrtag=1。 //最后處理，加入指向根結(jié)點(diǎn)的線索 prertag=1。pre)。 //pre是前驅(qū)結(jié)點(diǎn)，供加線索用 thread(amp。 rootltag=0。 rootrchild=root。 if(b==NULL)。 //值 ’ r’表示根結(jié)點(diǎn) rootltag=1。 root=(BTree *)malloc(sizeof(BTree))。(*current)rchild,pre)。 } *pre=*current。 } if((*pre)rchild==NULL) { (*pre)rchild=*current。 //左子樹線索化 if((*current)lchild==NULL){ (*current)lchild=*pre。 建立中序線索二叉樹的算法 ： void thread(BTree **current,BTree **pre) { if(*current!=NULL) { thread(amp。 //右指針域 }BTree。 //右標(biāo)志域 struct node *lchild。 //數(shù)據(jù)域 int ltag。 按中序遍歷得到的線索二叉樹稱為 中序線索二叉樹 ； 按先序遍歷得到的線索二叉樹稱為 先序線索二叉樹 ； 按后序遍歷得到的線索二叉樹稱為 后序線索二叉樹 ； （ 2）整體結(jié)構(gòu) 增設(shè)一個(gè)頭結(jié)點(diǎn)，令其 lchild指向二叉樹的根結(jié)點(diǎn)， ltag=0、rtag=1； 并將該結(jié)點(diǎn)作為遍歷訪問的第一個(gè)結(jié)點(diǎn)的前驅(qū)和最后一個(gè)結(jié)點(diǎn)的后繼； 最后用頭指針指示該頭結(jié)點(diǎn)。加線索的過程稱為線索化，由此得到的二叉樹稱作 線索二叉樹 。 線索二叉樹就是利用 n+1個(gè) 空鏈域 來存放結(jié)點(diǎn)的 前驅(qū)和后繼 結(jié)點(diǎn)的信息。 線索二叉樹 ⒈ 問題的提出 ：通過遍歷二叉樹可得到結(jié)點(diǎn)的一個(gè)線性序列，在線性序列中，很容易求得某個(gè)結(jié)點(diǎn)的直接前驅(qū)和后繼。(*T)lchild)； //構(gòu)造左子樹 CreateBinTree(amp。 //讀入空格，將相應(yīng)指針置空 else //讀入非空格 { *T=(BTree *)malloc(sizeof(BTree))。 T是指向根指針的指針，故修改 *T就修改了實(shí)參 (根指針 )本身 char ch。 (2) 構(gòu)造算法（舉例說明） 【 例 64】建立圖 613 (a)所示二叉樹，其輸入的先序序列是：ABD∮G∮∮CE∮∮F∮∮ 。前面介紹過用棧建立二叉樹，此處介紹一種基于先序遍歷的二叉樹構(gòu)造方式，即以二叉樹的先序序列為輸入構(gòu)造二叉鏈表。 3． 二叉鏈表的構(gòu)造 (1) 基本思想 利用遍歷可以實(shí)現(xiàn)對(duì)結(jié)點(diǎn)的一些操作，如求結(jié)點(diǎn)的雙親，求結(jié)點(diǎn)的孩子等。 所含輔助空間為遍歷過程中占的最大容量，即樹的深度。如果在算法中隱去和遞歸無關(guān)的語句 printf()， 則三種遍歷算法是完全相同的。 通過上述三種不同的遍歷方式得到三種不同的線性序列，它們的共同的特點(diǎn)是有且僅有一個(gè)開始結(jié)點(diǎn)和一個(gè)終端結(jié)點(diǎn)，其余各結(jié)點(diǎn)都有且僅有一個(gè)前驅(qū)結(jié)點(diǎn)和一個(gè)后繼結(jié)點(diǎn)。 //輸出當(dāng)前結(jié)點(diǎn)值 } } （ 2）中序遍歷的遞歸算法如下（假定結(jié)點(diǎn)的元素值為字符型）： void inorder(BiTree bt) { InitStack(s)； Push(s,bt)； while(!StackEmpty(s)) { while(GetTop(s)){ Push(s,GetTop(s)lchild)； p=POP(s)； if(!StackEmpty(s)) { visit(GetTop(s)data)； p=Pop(s)； Push(s, prchild)。 //遞歸后序遍歷左子結(jié)點(diǎn) postorder(rootrchild)。 //輸出當(dāng)前結(jié)點(diǎn)值 inorder(rootrchild)。 //結(jié)束 } 2．遍歷算法 void inorder(BTree *root) //中序遍歷 { if(root!=NULL) //如果不是空結(jié)點(diǎn) { inorder(rootlchild)。 //遞歸前序遍歷左子結(jié)點(diǎn) preorder(rootrchild)。 preorder(BTree *root) //前序遍歷 { if(root!= NULL) //如果不是空結(jié)點(diǎn) { printf(“%c\n”,rootdata)。 //定義左子結(jié)點(diǎn)指針 struct node *rchild。 typedef struct node //定義鏈表結(jié)構(gòu) { ElemType data。 Preorder (btrchild) 。 Postorder (btrchild) 。 visit (btdata)； Inorder (btrchild) 。若規(guī)定 先左后右 ，則只有前三種情況，分別規(guī)定為： DLR——先（根）序遍歷， LDR——中（根）序遍歷， LRD——后（根）序遍歷。 一次遍歷后，使樹中結(jié)點(diǎn)的 非線性 排列，按訪問的先后順序變?yōu)槟撤N 線性排列 。而二叉樹是非線性的，因而需要尋找一種規(guī)律，使二叉樹上的結(jié)點(diǎn)能排列在一個(gè)線性隊(duì)列上，從而便于遍歷。 遍歷二叉樹 ：指按一定的規(guī)律對(duì)二叉樹的每個(gè)結(jié)點(diǎn)，訪問且僅訪問一次的處理過程。 } } (2) 查找給定的結(jié)點(diǎn) find (root， x) (3) 找左孩子結(jié)點(diǎn) lchild(p)或右孩子結(jié)點(diǎn) rchild(p) (4) 輸出二叉樹 disptree(root) 在二叉樹的一些應(yīng)用中，常常要求在樹中查找具有某種特征的結(jié)點(diǎn)，或者對(duì)樹中全部結(jié)點(diǎn)逐一進(jìn)行某種處理。 } } } j++。 case 2： stack[top]rchild=p。 else { switch(k) { case 1： stack[top]lchild=p。plchild=prchild=NULL。plchild=prchild=NULL。 //為右結(jié)點(diǎn) default： p=(BTree *)malloc(sizeof(BTree))。 case ’,’： k=2。 //為左結(jié)點(diǎn) case ’)’： top。 stack[top]=p。 ch=str[j]。 char ch。 算法描述如下： void creatree(BTree **b, char *str) { BTree *stack[MAXSIZE], p=NULL。T) 功能：創(chuàng)建二叉樹 T 2．二叉樹部分運(yùn)算的算法描述 (1) 創(chuàng)建二叉樹 creatree(amp。 （ 6） Traverse(T) 功能：遍歷或訪問二叉樹 T。 （ 4） Lchild(T,x) 功能：求結(jié)點(diǎn)的左孩子。 （ 2） Root(T) 功能：求二叉樹的根。 二叉樹的基本運(yùn)算及實(shí)現(xiàn) 1．二叉樹的基本運(yùn)算 （ 1） Inittree (amp。 三叉鏈表的結(jié)點(diǎn)結(jié)構(gòu) 性質(zhì) 6 含有 n個(gè)結(jié)點(diǎn)的二叉鏈表中，有 n+1個(gè)空鏈域 。 lchild data parent rchild D 二叉樹 C E B A A C B D E ∧ ∧ ∧ ∧ ∧ ∧ ∧ 三叉鏈表 3．帶雙親指針的二叉鏈表 由于經(jīng)常要在二叉樹中尋找某結(jié)點(diǎn)的雙親時(shí)，可在每個(gè)結(jié)點(diǎn)上再加一個(gè)指向其雙親的指針 parent， 形成一個(gè)帶雙親指針的二叉鏈表。 ● 具有 n個(gè)結(jié)點(diǎn)的二叉鏈表中，共有 2n個(gè)指針域。 二叉鏈表的結(jié)點(diǎn)結(jié)構(gòu) lchild data rchild D 二叉樹 C E B A A C B D E ∧ ∧ ∧ ∧ ∧ ∧ 二叉鏈表 說明： ● 一個(gè)二叉鏈表由根指針 root唯一確定。 } BTree,*tree。 struct node *lchild。若某結(jié)點(diǎn)沒有左孩子或右孩子，其相應(yīng)的鏈域?yàn)榭罩羔槨Ｒ虼丝梢园衙總€(gè)結(jié)點(diǎn)分成三個(gè)域：一個(gè)域存放結(jié)點(diǎn)本身的信息，另外兩個(gè)是指針域，分別存放左、右孩子的地址。 ⒉ 鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu) （ 二叉鏈表） 設(shè)計(jì)不同的結(jié)點(diǎn)結(jié)構(gòu)，可以構(gòu)成不同的鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)。 D 二叉樹 C G F E B A 1 2 3 4 5 6 7 8 9 10 1112 A B C D E 0 0 0 0 F G 0 0 0 0 一般二叉樹也按完全二叉樹形式存儲(chǔ)，無結(jié)點(diǎn)處用 0表示。 完全二叉樹 D C G F E B A bt [3] 的雙親為 ? 3/2 ? =1， 即在 bt[1]中； 其左孩子在 bt[2i]=bt[6]中； 其右孩子在 bt[2i+1]=bt[7]中。 二叉樹的存儲(chǔ)結(jié)構(gòu) 同線性表一樣，二叉樹的存儲(chǔ)結(jié)構(gòu)也有順序和鏈表兩種結(jié)構(gòu)。 ⑵ 2i＞ n時(shí)，結(jié)點(diǎn) i無左孩子，為葉結(jié)點(diǎn)；否則，結(jié)點(diǎn) i的左孩子為結(jié)點(diǎn) 2i。 性質(zhì) 2 深度為 k的二叉樹至多有 2k1個(gè)結(jié)點(diǎn) (k≥1) 。 （ 2）完全二叉樹結(jié)點(diǎn)數(shù) n滿足 2k11＜ n≤2 k1 （ 3） 滿二叉樹一定是完全二叉樹，反之不成立。 1 2 3 7 6 5 4 K=3 n=231=7 滿二叉樹 (2) 完全二叉樹 (Complete BinaryTree) 深度為 k， 結(jié)點(diǎn)數(shù)為 n的二叉樹，當(dāng)且僅當(dāng)每個(gè)結(jié)點(diǎn)的編號(hào)都與相同深度的滿二叉樹中從 1到 n的結(jié)點(diǎn)一一對(duì)應(yīng)時(shí)，稱為完全二叉樹。 特點(diǎn)：（ 1）每一層上結(jié)點(diǎn)數(shù)都達(dá)到最大 （ 2）度為 1的結(jié)點(diǎn) n1=0， 樹葉都在最下一層上。 二叉樹有 5種基本形態(tài)： ( a ) ( b ) ( c ) ( d ) ( e )圖 69 二叉樹的五種基本形態(tài) (a) 空二叉樹 (b) 只有根結(jié)點(diǎn)的二叉樹 (c) 右子