基于遍歷序列重構(gòu)二叉結(jié)構(gòu)樹的分析

朱 濤

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

引言

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

1 二叉樹的遍歷

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

先序遍歷算法描述為：

若二叉樹為空，則空操作；否則

（1）訪問根結(jié)點；

（2）先序遍歷左子樹；

（3）先序遍歷右子樹.

中序遍歷算法描述為：

若二叉樹為空，則空操作；否則

（1）中序遍歷左子樹；

（2）訪問根結(jié)點；

（3）中序遍歷右子樹.

圖1 二叉樹

后序遍歷算法描述為：

若二叉樹為空，則空操作；否則

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

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

（3）訪問根節(jié)點.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

（1）若二叉樹為空，返回空；

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

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

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

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

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

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

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

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

（1）若二叉樹為空，返回空；

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

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

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

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

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

4 結(jié)束語

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

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

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

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

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

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

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