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