朱 濤

（陜西理工學(xué)院數(shù)學(xué)與計(jì)算機(jī)科學(xué)學(xué)院，陜西漢中 723000）

引言

二叉樹(shù)在計(jì)算機(jī)科學(xué)中有著重要的應(yīng)用，有好多問(wèn)題都是借助二叉樹(shù)這種結(jié)構(gòu)來(lái)描述.給定了二叉樹(shù)，依據(jù)相應(yīng)的遍歷算法，能夠方便的遍歷它的所有結(jié)點(diǎn)，并得到相應(yīng)的遍歷序列.但在有些應(yīng)用中，需要由二叉樹(shù)的遍歷序列反過(guò)來(lái)刻畫(huà)它們所表示的二叉樹(shù)，對(duì)于這樣的問(wèn)題，找出遍歷序列間的關(guān)系及相應(yīng)的重構(gòu)方法對(duì)研究相關(guān)的問(wèn)題是十分必要的.由于二叉樹(shù)的基本結(jié)構(gòu)是由根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)三部分構(gòu)成，因此對(duì)二叉樹(shù)的遍歷實(shí)際上是對(duì)這三部分的遍歷.對(duì)二叉樹(shù)遍歷以后，會(huì)得到一個(gè)線性的遍歷序列，在這個(gè)線性遍歷序列中，每個(gè)結(jié)點(diǎn)（除第一個(gè)和最后一個(gè)）有且僅有一個(gè)直接前驅(qū)和直接后繼，而某一結(jié)點(diǎn)的直接前驅(qū)和直接后繼又未必是該結(jié)點(diǎn)的左子樹(shù)或者右子樹(shù)，因此當(dāng)以該序列來(lái)重新構(gòu)造二叉結(jié)構(gòu)樹(shù)時(shí)，就難以實(shí)現(xiàn).徐志烽[1]給出了一種通過(guò)先序序列和中序序列構(gòu)建二叉樹(shù)的算法，但文獻(xiàn)[1]中沒(méi)有給出嚴(yán)密的理論證明，左正康等[2]給出了后序遍歷二叉樹(shù)非遞歸算法的推導(dǎo)及形式化證明.但是以上研究都很少?gòu)谋闅v序列重構(gòu)二叉樹(shù)的角度給出嚴(yán)格的理論分析和證明.本文將對(duì)由遍歷序列重新構(gòu)造二叉結(jié)構(gòu)樹(shù)進(jìn)行嚴(yán)格的理論分析及證明，并給出通過(guò)兩種遍歷序列如何唯一確定二叉結(jié)構(gòu)樹(shù)的實(shí)現(xiàn)算法.

1 二叉樹(shù)的遍歷

對(duì)二叉樹(shù)的遍歷運(yùn)算是將二叉樹(shù)中結(jié)點(diǎn)按一定規(guī)律線性化的過(guò)程，從這個(gè)意義上說(shuō)，遍歷二叉樹(shù)就是將非線性化的結(jié)構(gòu)變成線性化的訪問(wèn)序列.由二叉樹(shù)的遞歸定義[3]，二叉樹(shù)的基本結(jié)構(gòu)是由根結(jié)點(diǎn)、左子樹(shù)、右子樹(shù)三個(gè)基本單元組成，因此只要依次遍歷了這三部分，就遍歷了整個(gè)二叉樹(shù).在文獻(xiàn)[3]中，限制結(jié)點(diǎn)的先左后右原則后，得到了三種二叉樹(shù)遍歷算法，分別稱之為先（根）序遍歷，記為DLR（D表示二叉樹(shù)的根節(jié)點(diǎn)，L表示二叉樹(shù)的左孩子，R表示二叉樹(shù)的右孩子，文后各符號(hào)含義相同），中(根)序遍歷，記為L(zhǎng)DR，后根序遍歷，記為L(zhǎng)RD.文獻(xiàn)[3]中還給出了下述三種不同二叉樹(shù)遍歷的遞歸算法.

先序遍歷算法描述為：

若二叉樹(shù)為空，則空操作；否則

（1）訪問(wèn)根結(jié)點(diǎn)；

（2）先序遍歷左子樹(shù)；

（3）先序遍歷右子樹(shù).

中序遍歷算法描述為：

若二叉樹(shù)為空，則空操作；否則

（1）中序遍歷左子樹(shù)；

（2）訪問(wèn)根結(jié)點(diǎn)；

（3）中序遍歷右子樹(shù).

圖1 二叉樹(shù)

后序遍歷算法描述為：

若二叉樹(shù)為空，則空操作；否則

（1）后續(xù)遍歷左子樹(shù)；

（2）后續(xù)遍歷右子樹(shù)；

（3）訪問(wèn)根節(jié)點(diǎn).

這三種遍歷算法的不同之處僅在于其對(duì)于訪問(wèn)根結(jié)點(diǎn)、左子樹(shù)和右子樹(shù)的先后關(guān)系不同，依據(jù)這三種算法，可分別獲得不同的遍歷序列，如先序遍歷序列、中序遍歷序列和后序遍歷序列.對(duì)于圖1所示的二叉樹(shù)，可分別得到不同的遍歷序列.先根序遍歷圖1所示二叉樹(shù)后的先序序列為：ABCDEFGH；中根序遍歷圖1所示二叉樹(shù)后的中序序列為：CBEDAGHF；后根序遍歷圖1所示二叉樹(shù)后的后序序列為：CEDBHGFA.

2 遍歷序列重構(gòu)二叉樹(shù)的條件分析

對(duì)于一棵非空二叉樹(shù)，它的先序遍歷序列、中序遍歷序列或后序遍歷序列有可能相同，但三種遍歷序列不可能都相同.另外，每棵二叉樹(shù)的先序遍歷序列、中序遍歷序列和后序遍歷序列都是唯一的.那么對(duì)于一個(gè)給定的二叉樹(shù)，要得到它的遍歷序列很容易得到，反過(guò)來(lái)，由遍歷序列能否確定一棵二叉樹(shù)嗎？是否唯一？顯然，由一種遍歷序列不能唯一確定一棵二叉樹(shù).本文將對(duì)三種遍歷序列的組合唯一確定二叉樹(shù)進(jìn)行討論.

定理1:給定一棵二叉樹(shù)的先序序列和中序序列，可唯一確定一棵二叉樹(shù).

證明 設(shè)二叉樹(shù)結(jié)點(diǎn)的個(gè)數(shù)為n(n≥0).

當(dāng)n=0時(shí)，一棵空二叉樹(shù)的中序序列和先序序列都為空，可以唯一確定該二叉樹(shù)，命題成立.

定理2:給定一棵二叉樹(shù)的中序序列和后序序列，可唯一確定一棵二叉樹(shù).

證明:設(shè)二叉樹(shù)結(jié)點(diǎn)的個(gè)數(shù)為n(n≥0).

當(dāng)n=0時(shí)，一棵空二叉樹(shù)的中序序列和后序序列都為空，可以唯一確定該二叉樹(shù)，命題成立.

定理3:給定一棵二叉樹(shù)的先序序列和后序序列，可確定一棵二叉樹(shù)，但不唯一.證明:由于先序序列中第一個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)，后續(xù)序列中最后面一個(gè)結(jié)點(diǎn)是根結(jié)點(diǎn)，這樣，在先序序列中除第一個(gè)節(jié)點(diǎn)外以及在后續(xù)序列中除最后一個(gè)結(jié)點(diǎn)外，剩余的序列無(wú)法區(qū)分左子樹(shù)和右子樹(shù)，所以依據(jù)剩余的序列來(lái)構(gòu)造二叉樹(shù)，就會(huì)得到不同的二叉樹(shù)，所以確定的二叉樹(shù)不唯一.

3 遍歷序列重構(gòu)二叉樹(shù)的算法及實(shí)現(xiàn)

根據(jù)上文分析，有兩種序列組合可以唯一確定一棵二叉樹(shù)，這兩種序列組合分別為先序序列和中序序列以及中序序列和后序序列.張國(guó)[4]分析了遞歸算法和非遞歸算法差別，朱振元等[5]給出了一種遞歸算法轉(zhuǎn)化為非遞歸算法的可能.下邊對(duì)這兩種組合序列重構(gòu)二叉樹(shù)描述了算法步驟，并對(duì)其遞歸實(shí)現(xiàn)算法進(jìn)行了敘述.

3.1 先序序列和中序序列重構(gòu)二叉樹(shù)的遞歸算法及實(shí)現(xiàn)

由先序序列和中序序列重構(gòu)二叉樹(shù)的算法描述為：

（1）若二叉樹(shù)為空，返回空；

（2）若不空，由先序序列得到二叉樹(shù)的根結(jié)點(diǎn);

（3）由上述（2）的根結(jié)點(diǎn)把中序序列分為左子樹(shù)的中序序列和右子樹(shù)的中序序列兩個(gè)部分；

（4）根據(jù)上述左子樹(shù)的中序序列個(gè)數(shù)找到對(duì)應(yīng)的左子樹(shù)先序序列和右子樹(shù)的先序序列；

（5）按上述（2）、（3）、（4）同樣的方法依次類推，直到所得左、右子樹(shù)只含一個(gè)結(jié)點(diǎn)為止.

該算法的遞歸實(shí)現(xiàn)描述如下：

輸入?yún)?shù)是二叉樹(shù)的先序序列preorder和中序序列inorder，長(zhǎng)度n，返回二叉樹(shù)根結(jié)點(diǎn)指針，bitree是結(jié)點(diǎn)類型名.

3.2 中序序列和后序序列重構(gòu)二叉樹(shù)的遞歸算法及實(shí)現(xiàn)

由先序序列和中序序列重構(gòu)二叉樹(shù)的算法描述為：

（1）若二叉樹(shù)為空，返回空；

（2）若不空，由后序序列得到二叉樹(shù)的根結(jié)點(diǎn)；

（3）由上述（2）的根結(jié)點(diǎn)把中序序列分為左子樹(shù)的中序序列和右子樹(shù)的中序序列兩個(gè)部分；

（4）根據(jù)上述左子樹(shù)的中序序列個(gè)數(shù)找到對(duì)應(yīng)的左子樹(shù)后序序列和右子樹(shù)的后序序列；

（5）按上述（2）、（3）、（4）同樣的方法依次類推，直到所得左、右子樹(shù)只含一個(gè)結(jié)點(diǎn)為止.

該算法的遞歸實(shí)現(xiàn)描述如下：

4 結(jié)束語(yǔ)

二叉樹(shù)是一種樹(shù)型結(jié)構(gòu)，屬于典型的非線性結(jié)構(gòu)，也是一種簡(jiǎn)單有效地組織數(shù)據(jù)的方式.對(duì)二叉樹(shù)的遍歷是對(duì)二叉樹(shù)各種操作的基礎(chǔ)，也是對(duì)二叉樹(shù)進(jìn)行的一種常規(guī)運(yùn)算.文中主要分析了基于遍歷序列重構(gòu)二叉樹(shù)條件，提出了兩種遍歷序列相結(jié)合重構(gòu)二叉樹(shù)的遞歸算法，并給出了相應(yīng)算法的實(shí)現(xiàn)。對(duì)于給定一棵二叉樹(shù)的先序序列和后序序列，在什么情況下可以確定一棵二叉樹(shù)及是否唯一的問(wèn)題，文中只是給出了簡(jiǎn)單的理論分析，沒(méi)有詳細(xì)敘述。本文的下一步工作，將是對(duì)這種情況進(jìn)一步給出形式證明，并分情形給予分析。

[1]徐志烽.通過(guò)先序序列和中序序列建二叉樹(shù)[J].中山大學(xué)研究生學(xué)刊:自然科學(xué)(醫(yī)學(xué)版),2004(4):119—125.

[2]左正康,游珍,薛錦云.后序遍歷二叉樹(shù)非遞歸算法的推導(dǎo)及形式化證明[J].計(jì)算機(jī)工程與科學(xué),2010,32(3):119—123.

[3]嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,1992:125—131.

[4]張國(guó).基于遞歸算法的非遞歸實(shí)現(xiàn)研究[J].長(zhǎng)江大學(xué)學(xué)報(bào):自然科學(xué)版,2009,6(3):223-225.

[5]朱振元,朱承.遞歸算法的非遞歸化實(shí)現(xiàn)[J].小型微型計(jì)算機(jī)系統(tǒng), 2003,(3).

[6]朱濤.基于遍歷二叉樹(shù)的方法判斷完全二叉樹(shù)[J].紅河學(xué)院學(xué)報(bào):2005,6(3):47-48.