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