【文章內(nèi)容簡介】 中所經(jīng)過的結(jié)點路線也是相同的 ， 僅僅只是訪問的時機不同而已 。 ?如左下圖所示的二叉樹 ， 其三種遍歷的巡訪路線和訪問時機可示意如右下圖所示 。 二叉樹的遍歷舉例 巡訪路線 △ △ 前序序列： △ + △ a △ * △ b △ c △ / △ d △ e * *中序序列： a * + * b * * * c * * d * / * e ⊕ ⊕ 后序序列： a ⊕ b ⊕ c ⊕ * ⊕ + ⊕ d ⊕ e ⊕ / 二叉 樹的遍歷 遍歷二叉樹的遞歸算法 遍歷二叉村的非遞歸算法 遍歷序列與二叉樹的復(fù)原 基于遍歷的幾種二叉樹運算的 實現(xiàn)和應(yīng)用舉例 遍歷二叉樹的非遞歸算法 ?遞歸算法簡潔精練 、 可讀性好 、 易理解 ， 但其執(zhí)行效率較低；另外 ， 并非所有程序設(shè)計語言都提供遞歸的功能設(shè)施 。 所以 ，我們有必要討論遍歷二叉樹的 非遞歸算法 。 ?我們注意觀察前面給出的三種次序的巡訪路線 ， 它是從根結(jié)點開始沿左子樹深入直到最左下端時 ， 返回進(jìn)入剛剛遇到結(jié)點的右子樹； ?在右子樹中 ， 也是先深入到它的最左下結(jié)點時返回剛遇到結(jié)點的右子樹 ， …… ， 如此深入和返回 ， 直到從根結(jié)點的右子樹返回到根結(jié)點時止 。 ?在這一過程中 ， 返回結(jié)點的順序恰與深入結(jié)點的順序相反 ，先深入的后返回 ， 正好符合棧的特點 。 ?所以我們可以用棧來保存遍歷過程中的結(jié)點信息來實現(xiàn)遍歷二叉樹的 非遞歸算法 ， 并且假定?？臻g足夠大不會發(fā)生棧上溢以簡化算法 。 ?前序遍歷二叉樹的 非遞歸算法思想 是：從二叉樹的根結(jié)點開始 ， 沿左子樹一直深入到最左下結(jié)點時止 ，在深入的過程中訪問所遇到的結(jié)點 ， 并把所遇到結(jié)點的非空右孩子進(jìn)棧；當(dāng)左子樹結(jié)點全部處理完之后 ， 從棧頂退出當(dāng)前最近訪問過結(jié)點的右孩子 ， 再按上述過程遍歷該結(jié)點的右子樹；如此重復(fù) ， 直到?？諘r為止 。 ?在下面的算法中 ， 二叉樹以 二叉鏈表存儲 ， 用一維數(shù)組 stack[MAXSIZE]作為棧來保存結(jié)點的右孩子信息 ， top為棧頂指針 ， p始終指向巡訪過程中當(dāng)前要處理的結(jié)點 。 前序遍歷的非遞歸算法描述 define MAXSIZE 100 void nrpreorder(bitree bt) {bitree stack[MAXSIZE],p。 int top=0。 p=bt。 do {while(p!=NULL) {printf(“%d\t”,pdata)。 if(prchild!=NULL) /*如果右子樹不空 */ stack[++top]=prchild。 /*右孩子進(jìn)棧 */ p=plchild。} if(top0) p=stack[top]。 }while(top0)。 /*當(dāng)棧不空時繼續(xù)遍歷 */ } ?中序遍歷二叉樹的非遞歸算法 ， 其基本思想與前序遍歷類同 ， 只是沿左子樹向下搜索的過程中先將所遇結(jié)點進(jìn)棧 ， 待遍歷完左子樹返回時從棧頂退出結(jié)點并訪問 ， 然后再遍歷右子樹 。 中序遍歷的非遞歸算法描述 define MAXSIZE 100 void nrinorder(bitree bt) {bitree stack[MAXSIZE],p。 int top=0。 p=bt。 do {while(p!=NULL) { stack[++top]=p。 /*所遇結(jié)點進(jìn)棧 */ p=plchild。} /*繼續(xù)搜索 p的左子樹 */ if(top0) {p=stack[top]。 /*出棧一個結(jié)點 */ printf(“%d\t”,pdata)。 /*訪問結(jié)點 */ p=prchild。} /*繼續(xù)搜索右子樹 */ }while(top0)。 } ?后序遍歷二叉樹的非遞歸算法要比前序和中序遍歷稍復(fù)雜些 。 ?在后序遍歷中 ， 當(dāng)搜索指針指向一個結(jié)點時不能馬上訪問 ， 需要先遍歷左子樹 ， 所以結(jié)點需要進(jìn)棧保存； ?當(dāng)遍歷完左子樹返回再次搜索到該結(jié)點時還不能進(jìn)行訪問 ， 還需要遍歷其右子樹 ， 所以結(jié)點需要再次進(jìn)棧保存；即一個結(jié)點在兩次進(jìn)棧兩次出棧之后才能訪問 。 后序遍歷二叉樹的非遞歸算法續(xù) ?為了區(qū)別某一結(jié)點指針的兩次出棧 ， 需設(shè)置一標(biāo)志flag同結(jié)點同時進(jìn)出棧 ， flag定義如下： ?棧中數(shù)據(jù)類型可定義為指向結(jié)點的指針和 flag組成的結(jié)構(gòu)體類型： typedef struct stackelem {bitree link。 int flag。 }stackelemtype。 后序遍歷的非遞歸算法描述 define MAXSIZE 100 void nrpostorder(bitree bt) {stackelemtype stack[MAXSIZE]。 /*定義棧 */ bitree p。 int top=0,sign。 p=bt。 /*巡訪指針指向二叉樹的根結(jié)點 */ do {while(p!=NULL) {stack[++top].link=p。 /*結(jié)點第一次入棧 */ stack[top].flag=0。 /*置標(biāo)志為 0*/ p=plchild。 /*遍歷左子樹準(zhǔn)備 */ } 后序遍歷的非遞歸算法描述續(xù) if(top0) {sign=stack[top].flag。 /*標(biāo)志出棧存于 sign*/ p=stack[top].link。 if(sign==0) /*flag為 0， 是第一次出棧 */ { stack[++top].link=p。 stack[top].flag=1。 /*置標(biāo)志為 1*/ p=prchild。} else /*flag為 1， 是第二次出棧 */ { printf(“%d\t”,pdata)。 p=NULL。} } }while(top0)。 } ?所謂 層次遍歷 （ levelorder traversal）是指從二叉樹的根結(jié)點開始從上到下逐層遍歷該二叉樹 ， 在同一層次中從左到右依次訪問各個結(jié)點 。 例如對右圖的二叉樹 ， 按層次遍歷得到的結(jié)點序列為 ABCDEFG。 ?由層次遍歷的定義可知 ， 層次遍歷 是從根結(jié)點開始訪問 ， 然后訪問它的左孩子和右孩子 ， 接下來是它左孩子的左孩子和右孩子 ， 右孩子的左孩子和右孩子 ， …… 。 即在訪問完某個結(jié)點后 ， 一般不能馬上訪問它的左孩子和右孩子 （ 除根結(jié)點等特殊情況外 ） ，需要把它的左右孩子信息保存起來 。 二叉樹的層次遍歷（續(xù)） ?這種方式正好與隊列的操作特點吻合 ， 所以可利用一個隊列結(jié)構(gòu)來實現(xiàn)層次遍歷 ， 其做法是： (1) 首先將根結(jié)點入隊列； (2) 當(dāng)隊列不空 ， 從隊列中取出隊頭結(jié)點訪問它 ， 并在其左右孩子非空時 ， 把它的左孩子和右孩子結(jié)點依次入隊列； (3) 反復(fù)執(zhí)行 (2)， 直到隊列為空時止 。 ? 在下面的層次遍歷算法中 ， 二叉樹以二叉鏈表存儲 ， 用一維數(shù)組 queue[MAXSIZE]實現(xiàn)循環(huán)隊列 ， 變量 front和 rear為分別表示隊頭指針和隊尾指針的指示器變量 ， 并假定隊列有足夠空間不會發(fā)生上溢 。 二叉樹的層次遍歷算法描述 define MAXSIZE 100 void levelorder(bitree bt) {bitree queue[MAXSIZE]。 int front,rear。 if(bt==NULL) return。 front=0。 rear=0。 queue[++rear]=bt。 /*根結(jié)點入隊列 */ while(front!=rear) {front=(front+1)%MAXSIZE。 printf(“%d\t”,queue[front]data)。 二叉樹的層次遍歷算法描述續(xù) if(queue[front]lchild!=NULL) {rear=(rear+1)%MAXSIZE。 /*修改隊尾指針 */ queue[rear]=queue[front]lchild。} if(queue[front]rchild!=NULL) {rear=(rear+1)%MAXSIZE。 queue[rear]=queue[front]rchild。} } } 二叉 樹的遍歷 遍歷二叉樹的遞歸算法 遍歷二叉村的非遞歸算法 遍歷序列與二叉樹的復(fù)原 基于遍歷的幾種二叉樹運算的 實現(xiàn)和應(yīng)用舉例 二叉樹的復(fù)原 ?由前面的討論可知 ， 任意一棵二叉樹中結(jié)點的前序 、 中序 、 后序和層次遍歷次序都是惟一的 。 ?反過來講 ， 由一種遍歷次序能否惟一確定一棵二叉樹呢 ？ 回答是否定的 。 ?然而 ， 我們可以由兩種遍歷次序惟一確定一棵二叉樹 ， 這就是二叉樹的 復(fù)原問題 。 ? 二叉樹的前序遍歷是先訪問根結(jié)點 ， 再按前序遍歷方式遍歷根結(jié)點的左子樹和右子樹 ， 即由前序序列可以確定二叉樹的根結(jié)點 。 ?另一方面 ， 中序遍歷是先中序遍歷左子樹 ， 然后訪問根結(jié)點 ， 最后中序遍歷右子樹；根結(jié)點在中序序列中必然將結(jié)點分割成為兩個子序列 ， 根結(jié)點前的子序列是其左子樹的中序序列 ， 而根結(jié)點后的子序列是其右子樹的中序序列 。 利用前序序列和中序序列恢復(fù)二叉樹續(xù) ?現(xiàn)在可以根據(jù)這兩個子序列在前序序列中找到對應(yīng)的左子序列和右子序列 ， 兩個子序列在前序中的第一個結(jié)點分別是根結(jié)點的左孩子和右孩子結(jié)點 ，即左子樹和右子樹的根結(jié)點；此時左右子樹的根結(jié)點又分別把左右子序列各劃分成兩個子序列 。 ?如此一直做下去 ， 由前序序列確定各級子樹的根結(jié)點 ， 由中序序列確定隸屬于各級子樹的左右子樹中的結(jié)點 ， 當(dāng)取盡前序序列中的所有結(jié)點時 ， 各級子樹中的左右孩子都惟一確定了 ， 二叉樹也就恢復(fù)了；而且這種恢復(fù)是惟一的 。 利用前序、中序序列恢復(fù)二叉樹舉例 ?已知一棵二叉樹的前序序列為 ABDCEFG， 中序序列為 DBAFEGC， 其二叉樹的恢復(fù)過程是： ?先由前序序列知 A為根結(jié)點 ， 由中序序列知 DB為左子樹而 FEGC為右子樹 ， 如下圖 (a)； ?其次由前序序列確定左右子樹的根結(jié)點為 B和 C， 由中序序列知 D為 B的左孩子 B無右孩子 ， FEG為 C的左子樹 C無右子樹 ， 如上圖 (b)； 利用前序、中序序列恢復(fù)二叉樹舉例續(xù) ?現(xiàn)在由前序序列確定 C的左子樹的根結(jié)點為 E， 由中序序列知 F為 E的左孩子而 G為 E的右孩子 ， 這樣就得到了最終恢復(fù)的二叉樹 ， 如下圖 (c)。 ?同利用前序序列和中序序列恢復(fù)二叉樹的道理一樣 ， 利用后序序列和中序序列也可以惟一確定一棵二叉樹 。 ?在恢復(fù)二叉樹的過程中 ， 后序序列的作用如同前面的前序序列一樣是確定各級子樹的根結(jié)點；無非是前序序列中第一個結(jié)點為根結(jié)點而后序序列中最后一個結(jié)點為根結(jié)點 。 ?中序序列的作用仍然是確定隸屬于各級子樹的左右子樹中的結(jié)點 ， 當(dāng)各級子樹中的左右孩子都惟一確定時 ， 二叉樹就完全恢復(fù)了 。 利用后序、中序序列恢復(fù)二叉樹舉例 ?對于后序序列 DBFGECA和中序序列 BDAFEGC， 可以