【文章內(nèi)容簡(jiǎn)介】 derTraverse(Tlchild)。 ??前序遍歷左子樹(shù) PreOrderTraverse(Trchild)。 ??前序遍歷右子樹(shù) } } 75 二叉樹(shù)的中序遍歷遞歸算法 若二叉樹(shù)為空，則算法結(jié)束；否則： (1)中序遍歷根結(jié)點(diǎn)的左子樹(shù)； (2)訪問(wèn)根結(jié)點(diǎn)； (3)中序遍歷根結(jié)點(diǎn)的右子樹(shù)。 void InOrderTraverse(bitree *T) { if(T) { InOrderTraverse(Tlchild)。 printf(\t%c\n,Tdata)。 InOrderTraverse(Trchild)。 } } 76 二叉樹(shù)的后序遍歷遞歸算法 若二叉樹(shù)為空，則算法結(jié)束；否則： (1)后序遍歷根結(jié)點(diǎn)的左子樹(shù)； (2)后序遍歷根結(jié)點(diǎn)的右子樹(shù)； (3)訪問(wèn)根結(jié)點(diǎn)。 void PostOrderTraverse(bitree *T) { if(T) { PostOrderTraverse(Tlchild)。 PostOrderTraverse(Trchild)。 printf(\t%c\n,Tdata)。 } } 77 (1)問(wèn)題的數(shù)學(xué)模型或算法設(shè)計(jì)方法本身就是遞歸的，采用遞歸算法來(lái)描述它們非常自然； (2)描述直觀，結(jié)構(gòu)清晰、簡(jiǎn)潔；正確性證明比非遞歸算法容易。 (1)算法的執(zhí)行時(shí)間與空間開(kāi)銷往往比非遞歸算法要大，當(dāng)問(wèn)題規(guī)模較大時(shí)尤為明顯； (2)對(duì)算法進(jìn)行優(yōu)化比較困難； (3)分析跟蹤算法的執(zhí)行過(guò)程比較麻煩； (4)描述算法的語(yǔ)言不具有遞歸功能時(shí)，算法無(wú)法描述。 謹(jǐn)慎使用遞歸，因?yàn)樗暮?jiǎn)潔可能會(huì)掩蓋它的低效率。 五、遞歸問(wèn)題的非遞歸算法的設(shè)計(jì) 78 五、遞歸問(wèn)題的非遞歸算法的設(shè)計(jì) ? 回顧遍歷的過(guò)程 (以中序?yàn)槔?) 1 先走到最左 2 往回訪問(wèn)父結(jié)點(diǎn) 3 往右訪問(wèn)右子樹(shù) 走到最左 回訪父結(jié)點(diǎn) 訪問(wèn)右子樹(shù) ... A B C D E F G 79 二叉樹(shù)的遍歷：非遞歸算法 A B C D E F G ? 當(dāng)向左 /右走到底時(shí)怎么辦？ ? 需要返回到祖先 ? 哪個(gè)祖先？ ? 路過(guò)的卻未訪問(wèn)的最近的祖先 ? 這就需要一種機(jī)制能記錄訪問(wèn)的“歷史信息” :路過(guò)卻未訪問(wèn)的結(jié)點(diǎn) ，以便能夠回溯回去 ? 這就需要一個(gè) 棧 存放來(lái)這些祖先 80 E H二叉樹(shù)的遍歷：非遞歸算法 (1)非空樹(shù)從根開(kāi)始； (2)若當(dāng)前結(jié)點(diǎn)存在 ， 則暫存 ， p下到左子樹(shù)； 否則回退 → 訪問(wèn)當(dāng)前結(jié)點(diǎn) → p下到右子樹(shù) 中序遍歷非遞歸思路： B A ^ C ^ D ^ E ^ G ^ ^ F ^ ^ H ^ T p A 棧 S BD p ^ p 遍歷序列： D p ^ p B Gp ^ G p p ^ p E p ^ p H p ^ p A C p ^ p C Fp ^ p F p ^ (3)重復(fù) (2)直到 p空且棧空 81 Stack[0..M1]保存遍歷過(guò)程中結(jié)點(diǎn)的地址； top棧頂指針，初始為 1； p遍歷過(guò)程中使用的指針變量，初始時(shí)指向根結(jié)點(diǎn)。 用自然語(yǔ)言表達(dá)的算法 p指向的結(jié)點(diǎn)非空，則將 p指的結(jié)點(diǎn)的地址進(jìn)棧，然后，將 p指向左子樹(shù)的根； p指向的結(jié)點(diǎn)為空，則從棧中退出棧頂元素送 p，訪問(wèn)該結(jié)點(diǎn)，然后，將 p指向右子樹(shù)的根； 重復(fù)上述過(guò)程，直到 p為空，并且棧也為空。 82 二叉樹(shù)的中序遍歷：非遞歸算法 int InOrderT (bitree *T) { bitree *p=T。 SqStack *S。 InitStack(S)。 //建棧 while (p||!StackEmpty(s)) //還有未訪問(wèn)的 { if (p) //一直向左走到底 ， 路過(guò)的所有的根入棧 { Push(S, p)。 p = plchild。 //遍歷左子樹(shù) } else //p為 NULL， 說(shuō)明走到了底 { Pop(S, p)。 Visit(pdata)。 //彈出一個(gè)還沒(méi)訪問(wèn)的結(jié)點(diǎn) ， 訪問(wèn)之 p = prchild。 //遍歷右子樹(shù) } } return OK。 } p指向樹(shù)根 p走到了底，再依次彈出剛才路過(guò)卻沒(méi)有訪問(wèn)的結(jié)點(diǎn)，訪問(wèn)之，然后 p向右走 83 ? 時(shí)間復(fù)雜度 – n個(gè)結(jié)點(diǎn)，每一個(gè)都要訪問(wèn)一次 – 顯然時(shí)間復(fù)雜度為 O(n)(這里 n為結(jié)點(diǎn)數(shù) ) ? 空間復(fù)雜度 – 不論是遞歸還是非遞歸算法都要用到棧 – 棧的最大深度 = 樹(shù)的深度 – 所有空間復(fù)雜度為 O(n)(這里 n為樹(shù)的深度 ) 二叉樹(shù)的遍歷：算法效率 84 二叉樹(shù)的初始化 算法的基本思想 :創(chuàng)建二叉樹(shù)的頭結(jié)點(diǎn)。 程序?qū)崿F(xiàn) ： void Initiate(bitree **root) { *root = (bitree *)malloc(sizeof(bitree))。 (*root)lchild=NULL。 (*root)rchild=NULL。 } root是指向根指針的指針 85 按前序構(gòu)造二叉鏈表 例 1：按下列次序輸入字符 (φ表示空格 ): ABCφφDEφGφφFφφφ A ^ B ^ C ^ D ^ E ^ F ^ ^ G ^ 二叉鏈表為 : 例 2： HGφFφφMφφ root H ^ G ^ M ^ ^ F ^ 86 按前序構(gòu)造二叉鏈表的算法 void CreateBT(bitree **P) { char ch。 ch=getchar()。 /*從鍵盤上輸入一個(gè)字符 */ if (ch==39。 39。) *P=NULL。 else { *P=(bitree *)malloc(sizeof(bitree))。 (*P)data=ch。 CreateBT(amp。((*P)lchild))。 CreateBT(amp。((*P)rchild))。 } } P是指向根指針的指針， *P的值發(fā)生變化后可以返回 87 前序遍歷序列： A,B,D,K,J,G,C,F,I,E,H 中序遍歷序列： D,B,G,J,K,A,F,I,E,C,H 后序遍歷序列： D,G,J,K,B,E,I,F,H,C,A 按層次遍歷序列： A,B,C,D,K,F,H,J,I,G,E 88 89 前序序列： 中序序列： 后序序列： ABIFCGDEH FIBCGADEH FIGCBHEDA 90 利用 前序序列 和 中序序列 恢復(fù)二叉樹(shù) 利用 中序序列 和 后序序列 恢復(fù)二叉樹(shù) 利用 前序序列 和 后序序列 恢復(fù)二叉樹(shù) 前序序列： A,B,D,C 后序序列： D,B,C,A 91 六、由遍歷序列恢復(fù)二叉樹(shù) 前序序列： A,B,D,E,J,C,F,I,G 中序序列： D,B,J,E,A,F,I,C,G 92 已知前序序列和中序序列，恢復(fù)二叉樹(shù) 在前序序列中尋找根； 到中序序列中分左右。 規(guī)律 已知中序序列和后序序列，恢復(fù)二叉樹(shù) 在后序序列中尋找根； 到中序序列中分左右。 93 例 :已知結(jié)點(diǎn)的前序序列和中序序列分別為： 前序序列： ABDEGHCF 中序序列： DBGEHACF 求此二叉樹(shù) 六、由遍歷序列恢復(fù)二叉樹(shù) 94 ?由已知的前序序列和中序序列構(gòu)造二叉樹(shù)的方法 A B D 前序 E G H C F D B G 中序 E H A C F A 0 1 2 3 4 5 左子樹(shù) 右子樹(shù) 左子樹(shù) 右子樹(shù) 六、由遍歷序列恢復(fù)二叉樹(shù) 95 A B D 前序 E G H C F D B G 中序 E H A C F A B 0 1 左 右 左 右 D ?由已知的前序序列和中序序列構(gòu)造二叉樹(shù)的方法 六、由遍歷序列恢復(fù)二叉樹(shù) 96 A B D 前序 E G H C F D B G 中序 E H A C F B A D E 0 1 左 左 右 右 G H ?由已知的前序序列和中序序列構(gòu)造二叉樹(shù)的方法 六、由遍歷序列恢復(fù)二叉樹(shù) 97 A B D 前序 E G H C F D B G 中序 E H A C F B A C F D E G H 0 右 右 ?由已知的前序序列和中序序列構(gòu)造二叉樹(shù)的方法 六、由遍歷序列恢復(fù)二叉樹(shù) 98 (1)由前序序列得根； (2)在中序序列中查找根 ， 并確定左子樹(shù)中結(jié)點(diǎn)個(gè)數(shù)； (3)分別確定左 、 右子樹(shù)的前序序列和中序序列； (4)分別構(gòu)造左 、 右子樹(shù) 六、由遍歷序列恢復(fù)二叉樹(shù) ?由已知的前序序列和中序序列構(gòu)造二叉樹(shù)的方法 99 已知二叉樹(shù)的 ABDFCEHG 中序序列 DBFAHECG 請(qǐng)構(gòu)造該二叉樹(shù)。 DMFBHELGCA 中序序列 DBMFAHECGL 請(qǐng)構(gòu)造該二叉樹(shù)。 自測(cè)題 100 一棵二叉樹(shù)的前序、中序和后序序列如下，其中有部分未標(biāo)出，試構(gòu)造出該二叉樹(shù)。 ? 前序序列為： _ _ C D E _ G H I _ K ? 中序序列為： C B _ _ F A _ J K I G ? 后序序列為： _ E F D B _ J I H _ A 自測(cè)題 101 試找出滿足下列條件的二叉樹(shù) 1)前序序列與后序序列相同 2)中序序列與后序序列相同 3)前序序列與中序序列相同 4)前序、中序、后序序列均相同 5)中序序列與層次遍歷序列相同 自測(cè)題 102 ? 一棵二叉樹(shù)的前序遍歷序列為 ABCDEFG，它的中序遍歷序列可能是 ( )。 ? A. CABDEFG ? B. ABCDEFG ? C. DACEFBG ? D. ADCFEGB 自測(cè)題 103 ? 一棵非空的二叉樹(shù)的前序序列和后序序列正好相反，則該二叉樹(shù)一定滿足 ( )。 ? A. 其中任意一個(gè)結(jié)點(diǎn)均無(wú)左孩子 ? B. 其中任意一個(gè)結(jié)點(diǎn)均無(wú)右孩子 ? C. 其中只有一個(gè)葉子結(jié)點(diǎn) ? D. 其中度為 2的結(jié)點(diǎn)最多為一個(gè) ? E. 空或只有一個(gè)結(jié)點(diǎn) ? F. 高度等于其結(jié)點(diǎn)數(shù) 自測(cè)題 104 注意： 一個(gè)二叉樹(shù)的遍歷序列 不能決定一棵 二叉樹(shù)，但 前序（或后序）和中序遍歷序列的組合 可以唯一確定一棵二叉樹(shù)。而前序和后序遍歷則不能。 口訣： DLR—前序遍歷，即 先根 再左再右 LDR—中序遍歷，即 先左 再根 再右 LRD—后序遍歷，即 先左再右 再根 105 例 給二叉樹(shù)中某個(gè)指定結(jié)點(diǎn)插入一個(gè)左結(jié)點(diǎn) 算法思想 : 若當(dāng)前結(jié)點(diǎn) (假設(shè)為 curr)非空，在 curr的左子樹(shù)插入元素值為 x的新結(jié)點(diǎn)，原 curr所指結(jié)點(diǎn)的左子樹(shù)成為新插入結(jié)點(diǎn)的左子樹(shù)。若插入成功返回新插入結(jié)點(diǎn)的指針，否則返回空指針。 二叉樹(shù)操作舉例 106 bitree *InsertLeftNode(bitree *curr,datatype x) { bitree *s, *t。 if(curr==NULL) return NULL。 t=currlchild。 s=(bitree *)malloc(sizeof(bitree))。 sdata=x。 slchild=t。 srchild=NULL。 currlchild=s。 return currlchild。 } 107 算法思想 : 若 curr非空，刪除 curr所指結(jié)點(diǎn)的左子樹(shù)。若刪除成功，返回刪除結(jié)點(diǎn)的雙親結(jié)點(diǎn)指針，否則返回空指針。 例 刪除二叉樹(shù)中指定結(jié)點(diǎn)的左子樹(shù) bitree *DeleteLeftTree(bitree *curr) { if(curr==NULL||currlchild==NULL) return NULL。 free(currlchild)。 currlchild=NULL。 return cu