一種由層次遍歷和其它遍歷構造二叉樹的新算法

王防修，劉春紅

(1.武漢輕工大學 數學與計算機學院,湖北 武漢 430023;2.九州通醫藥集團物流有限公司,湖北 武漢 430040)

一種由層次遍歷和其它遍歷構造二叉樹的新算法

王防修1，劉春紅2

(1.武漢輕工大學 數學與計算機學院,湖北 武漢 430023;2.九州通醫藥集團物流有限公司,湖北 武漢 430040)

在由遍歷序列構造二叉樹問題的研究中，針對目前還沒有用層次遍歷和其它遍歷一起構造二叉樹的問題，提出了一種由層次遍歷和其它遍歷一起構造二叉樹的新算法?？紤]到層次遍歷中左子樹和右子樹的層次遍歷不具有遞歸屬性，設計了從層次遍歷中分離出左右子樹層次遍歷的方法，并且通過組合得到具有遞歸屬性的層次遍歷。通過對層次遍歷和中序遍歷的遞歸屬性的研究，設計了由層次遍歷和中序遍歷構造二叉樹的遞歸算法；通過對層次遍歷和先序遍歷的遞歸屬性的研究，設計了由層次遍歷和中序遍歷構造沒有出度為1的二叉樹的遞歸算法；通過對層次遍歷和后序遍歷的遞歸屬性的研究，設計了由層次遍歷和后序遍歷構造沒有出度為1的二叉樹的遞歸算法。仿真結果表明，用設計的算法構造二叉樹是有效的，可為二叉樹的構造提供新算法。

層次遍歷；先序遍歷；中序遍歷；后序遍歷；遞歸算法

1 引言

自然界很多事物本質上是樹狀結構，如果想用計算機模擬具有樹狀結構的事物，則必須首先解決樹狀結構在計算機中的表示問題。由于樹和二叉樹之間能夠相互轉化，故只需解決二叉樹在計算機內存中的表示即可。因此，用各種算法構造二叉樹一直是人們研究的熱點問題[2-6]。近年來，通過對二叉樹自身特點的研究，出現了很多由遍歷序列構造二叉樹的遞歸算法[7,8]和非遞歸算法[9-12]。雖然這些算法各有不同，但都可以歸結為以下三種情形：

(1)由先序遍歷序列和中序遍歷序列構建二叉樹；

(2)由中序遍歷序列和后序遍歷序列構建二叉樹；

(3)由先序遍歷序列和后序遍歷序列構建二叉樹。

然后，除了上述三種情況之外，構造二叉樹值得研究的還有下述三種情形：

(1)由層次遍歷序列和中序遍歷序列構建二叉樹；

(2)由層次遍歷序列和先序遍歷序列構建二叉樹。

(3)由層次遍歷序列和后序遍歷序列構建二叉樹。

對于這三種構造二叉樹的情形，目前尚未見之于文獻。因此，如果能夠設計這三種構造二叉樹的新算法，則無疑對二叉樹的構造具有重要意義。此外，由層次遍歷序列和其它遍歷序列構建二叉樹可能還需要額外的附加條件。針對這些問題， 筆者對這三種構造二叉樹的算法進行了理論上的證明，并且分別設計了三種不同的構造二叉樹的遞歸算法。仿真結果表明，這三種新算法都可以用來構造二叉樹。

2 由層次遍歷和其它遍歷構造二叉樹的數學原理

定理1 如果已知一棵二叉樹的層次遍歷序列和中序遍歷序列，則可用遞歸算法建立該二叉樹。

證明設W=wiwi+1…wj和Y=ykyk+1…yl分別表示二叉樹T的層次遍歷序列和中序遍歷序列，則由層次遍歷序列的性質可知二叉樹T的根結點是wi。由二叉樹的性質可知，在中序遍歷序列存在唯一的元素ym，使得ym=wi。因此，中序遍歷序列Y可以進行如下劃分：

Y=(yk…ym-1)ym(ym+1…yl)

(1)

根據二叉樹中序遍歷序列的性質可知，Y1=yk…ym-1是T的左子樹的中序遍歷，而Y2=ym+1…yl是T的右子樹的中序遍歷。

如果對層次遍歷序列W進行如下劃分：

W1={wq|wq∈Y1,q=i+1,…,j}

(2)

W2={wq|wq∈Y2,q=i+1,…,j}

(3)

則由二叉樹的層次遍歷的性質可知，W1是二叉樹T的左子樹的層次遍歷，而W2是二叉樹T的右子樹的層次遍歷。

如果對層次遍歷序列W進行如下重組：

W=wiW1W2

(4)

則存在p∈{i+1,…,j}，使得W進行如下劃分：

W=wi(wi+1…wp)(wp+1…wj)

(5)

其中W1=wi+1…wp是T的左子樹的層次遍歷，而W2=wp+1…wjT的右子樹的層次遍歷。

由Y1與W1的長度相等 ，有

p=m+i-k

(6)

由Y2與W2的長度相等 ，有

p=m+j-l

(7)

由于W和Y的長度相等，故有j-i=l-k，從而式(6)和式(7)表示的p值相等。

遞歸子結構：如果m>k，則二叉樹T的左孩子由左子樹的層次遍歷W1=wi+1…wp和中序遍歷Y1=yk…ym-1確定；如果m

遞歸終止條件：如果m=k，則二叉樹T無左孩子；如果m=l，則二叉樹T無右孩子。

定理2 如果已知一棵二叉樹的層次遍歷序列和先序遍歷序列，并且該二叉樹沒有出度為1的結點，則可用遞歸算法建立該二叉樹。

證明 如果二叉樹存在出度為1的結點，則由層次遍歷序列和先序遍歷序列所對應的二叉樹不唯一，故無法構造該二叉樹。如果不存在出度為1的結點，則設W=wiwi+1…wj和X=xkxk+1…xl分別是二叉樹T的層次遍歷和先序遍歷。由二叉樹層次遍歷和先序遍歷的性質可知wi和xk都是二叉樹T的根結點，故wi=xk。由二叉樹的性質可知，在先序遍歷序列存在唯一的元素xm，使得xm=wi+2。因此，先序遍歷序列X可以進行如下劃分：

X=xk(xk+1…xm-1)(xm…xl)

(8)

根據二叉樹先序遍歷序列的性質可知，X1=xk+1…xm-1是T的左子樹的先序遍歷，而X2=xm…xl是T的右子樹的先序遍歷。

如果對層次遍歷序列W進行如下劃分：

W1={wq|wq∈X1,q=i+1,…,j}

(9)

W2={wq|wq∈X2,q=i+1,…,j}

(10)

則由二叉樹的層次遍歷的性質可知，W1是二叉樹T的左子樹的層次遍歷，而W2是二叉樹T的右子樹的層次遍歷。

如果令W=wiW1W2，則?p∈{i+1,…,j}，使得W1=wi+1…wp和W2=wp+1…wj。

由X1與W1的長度相等 ，有

p=m+i-k-1

(11)

由X2與W2的長度相等 ，有

p=m+j-l-1

(12)

由j-i=l-k可知式(11)和式(12)的值相等。

遞歸子結構：如果m>k，則二叉樹T的左孩子由左子樹的層次遍歷W1=wi+1…wp和先序遍歷X1=xk+1…xm-1確定；如果m

遞歸終止條件：如果l=k，則二叉樹T既無左孩子又無右孩子。

定理3 如果已知一棵二叉樹的層次遍歷序列和后序遍歷序列，并且該二叉樹沒有出度為1的結點，則可用遞歸算法建立該二叉樹。

證明如果二叉樹存在出度為1的結點，則由層次遍歷序列和后序遍歷序列所對應的二叉樹不唯一，故無法構造該二叉樹。如果不存在出度為1的結點，則設W=wiwi+1…wj和Z=zkzk+1…zl分別是二叉樹T的層次遍歷和后序遍歷。由二叉樹層次遍歷和后序遍歷的性質可知wi和zl都是二叉樹T的根結點，故wi=zl。由二叉樹的性質可知，在后序遍歷序列存在唯一的元素zm，使得zm=wi+1。因此，后序遍歷序列Z可以進行如下劃分：

Z=(zk…zm)(zm+1…zl-1)zl

(13)

根據二叉樹后序遍歷序列的性質可知，Z1=zk…zm是T的左子樹的后序遍歷，而Z2=zm+1…zl-1是T的右子樹的后序遍歷。

如果對層次遍歷序列W進行如下劃分：

W1={wq|wq∈Z1,q=i+1,…,j}

(14)

W2={wq|wq∈Z2,q=i+1,…,j}

(15)

則由二叉樹的層次遍歷的性質可知，W1是二叉樹T的左子樹的層次遍歷，而W2是二叉樹T的右子樹的層次遍歷。

如果令W=wiW1W2，則?p∈{i+1,…,j}，使得W1=wi+1…wp和W2=wp+1…wj。

由Z1與W1的長度相等 ，有

p=m+i-k+1

(16)

由Z2與W2的長度相等 ，有

p=m+j-l+1

(17)

由j-i=l-k可知式(16)和式(17)的值相等。

遞歸子結構：如果m>k，則二叉樹T的左孩子由左子樹的層次遍歷W1=wi+1…wp和后序遍歷Z1=zk…zm確定；如果m

遞歸終止條件：如果l=k，則二叉樹T既無左孩子又無右孩子。

3 由層次遍歷和其它遍歷建立二叉樹的算法設計

3.1 由層次遍歷序列和中序遍歷序列構造二叉樹

為方便算法設計，不妨設建立二叉樹的遞歸函數為T=f(W,Y,i,j,k,l)，則其遞歸過程可以描述如下：

(1)由層次遍歷序列W=wiwi+1…wj可知W中的第一個元素wi是二叉樹T的根結點。

(2)從中序遍歷序列Y中查找元素ym，使得ym=wi。根據式(1)得到左子樹的中序遍歷Y1和右子樹的中序遍歷Y2。

(3)根據式(2)從層次遍歷W中分離出左子樹的層次遍歷W1，根據式(3)從層次遍歷W中分離出右子樹的層次遍歷W2。

(4)根據式(5)重新組裝W=wiW1W2。

(5)如果m=k，則根結點T沒有左孩子；否則，二叉樹的根結點T的左孩子是其左子樹的根結點，若設其左孩子為Tl，則式(6)或式(7)分別有

Tl=f(W,Y,i+1,m+i-k,k,m-1)

(18)

或

Tl=f(W,Y,i+1,m+j-l,k,m-1)

(19)

(6)如果m=l，則二叉樹的根結點T沒有右孩子；否則，根結點T的右孩子是其右子樹的根結點。若設T的右孩子為Tr，則有

Tr=f(X,Y,m+i-k+1,j,m+1,l)

(20)

或

Tr=f(X,Y,m+j-l+1,j,m+1,l)

(21)

(7)當遞歸過程結束時，則得到一個根結點為T的二叉樹。

3.2 由層次遍歷序列和先序遍歷序列構造無出度為1的二叉樹

為方便算法描述，設建立二叉樹的遞歸函數為T=g(W,X,i,j,k,l)，其遞歸過程描述如下：

(1)先序遍歷序列X=xkxk+1…xl中的元素xk是二叉樹T的根結點；

(2)從先序遍歷序列X中查找元素xm，使得xm=wi+2。根據式(8)得到左子樹的先序遍歷X1和右子樹的先序遍歷X2

(3)根據式(9)從層次遍歷W中分離出左子樹的層次遍歷W1，根據式(10)從層次遍歷W中分離出右子樹的層次遍歷W2。

(4)由W=wiW1W2重新組裝層次遍歷。

(5)如果m>k，則二叉樹的根結點T的左孩子是其左子樹的根結點，若設其左孩子為Tl，則式(11)或式(12)分別有

Tl=g(W,X,i+1,m+i-k-1,k+1,m-1)

(22)

或

Tl=g(W,X,i+1,m+j-l-1,k+1,m-1)

(23)

(6)如果m

Tr=g(W,X,m+i-k,j,m,l)

(24)

或

Tr=g(W,X,m+j-l,j,m,l)

(25)

(7)如果l=k，則二叉樹T既沒有左孩子又沒有右孩子。

(8)當遞歸過程結束時，則得到一個根結點為T的二叉樹。

3.3 由層次遍歷序列和后序遍歷序列建立無出度為1的二叉樹

為方便算法描述，設建立二叉樹的遞歸函數為T=h(W,Z,i,j,k,l)，則其遞歸過程描述如下：

(1)后序遍歷序列Z=zkzk+1…zl中的元素zl是二叉樹T的根結點。

(2)從后序遍歷序列Z中查找元素zm，使得zm=wi+1。根據式(13)得到左子樹的后序遍歷Z1和右子樹的后序遍歷Z2。

(3)根據式(14)從層次遍歷W中分離出左子樹的層次遍歷W1，根據式(15)從層次遍歷W中分離出右子樹的層次遍歷W2。

(4)由W=wiW1W2重新組裝層次遍歷。

(5)如果m>k，則二叉樹的根結點T的左孩子是其左子樹的根結點，若設其左孩子為Tl，則式(16)或式(17)分別有

Tl=h(W,Z,i+1,m+i-k+1,k,m)

(26)

或

Tl=h(W,Z,i+1,m+j-l+1,k,m)

(27)

(6)如果m

Tr=h(W,Z,m+i-k+2,j,m+1,l-1)

(28)

或

Tr=h(W,Z,m+j-l+2,j,m+1,l-1)

(29)

(7)如果l=k，則二叉樹T既沒有左孩子又沒有右孩子。

(8)當遞歸過程結束時，則得到一個根結點為T的二叉樹。

4 算法仿真

算例 用上述三種算法構造如圖1所示的二叉樹。

圖1 二叉樹

解 由圖1可以得到如表1所示的遍歷序列。

表1 二叉樹的遍歷序列

i123456789wiacbdefghKyidchekafbGxiacdehkbfgzidhkecfgba

表1中，W=w1w2…w9表示二叉樹的層次遍歷序列，Y=y1y2…y9表示二叉樹的中序遍歷序列，X=x1x2…x9表示二叉樹的先序遍歷序列，而Z=z1z2…z9表示二叉樹的后序遍歷序列。

方法一 根據算法3.1，由層次遍歷序列W和中序遍歷序列Y構造二叉樹的過程如下：

(4)當m=8時，由f(W,Y,8,8,7,7)得w7(b)的左孩子為w8(f)和m=7，而由m=7可知w8(f)是葉子結點；由f(W,Y,9,9,9,9)得w7(b)的右孩子為w9(g)和m=9，而由m=9可知w9(g)是葉子結點。

(5)當m=4時，由f(W,Y,5,5,3,3)得w4(e)的左孩子為w5(h)和m=3，而由m=3可知w5(h)是葉子結點；由f(W,Y,6,6,5,5)得w4(e)的右孩子為w6(k)和m=5，而由m=5可知w6(k)是葉子結點。

方法二 根據算法3.2，由層次遍歷序列W和先序遍歷序列X構造二叉樹的過程如下：

(4)當m=9時，由g(W,X,8,8,8,8)得x7(b)的左孩子為x8(f)和l=k=8，而由l=k可知x8(f)是葉子結點；由g(W,X,9,9,9,9)得x7(b)的右孩子為x9(g)和l=k=9，而由l=k可知x9(g)是葉子結點。

(5)當m=6時，由f(W,X,5,5,5,5)得x4(e)的左孩子為x5(h)和l=k=5，而由l=k可知x5(h)是葉子結點；由f(W,X,6,6,6,6)得x4(e)的右孩子為x6(k)和l=k=6，而由l=k可知x6(k)是葉子結點。

方法三 根據算法3.3，由層次遍歷序列W和后序遍歷序列Z構造二叉樹的過程如下：

(4)當m=6時，由f(W,X,8,8,6,6)得z8(b)的左孩子為z6(f)和l=k=6，而由l=k可知z6(f)是葉子結點；由f(W,X,9,9,7,7)得z8(b)的右孩子為z7(g)和l=k=7，而由l=k可知z7(g)是葉子結點。

(5)當m=2時，由g(W,Z,5,5,2,2)得z4(e)的左孩子為z2(h)和l=k=2，而由l=k可知z2(h)是葉子結點；由h(W,Z,6,6,3,3)得z4(e)的右孩子為z3(k)和l=k=3，而由l=k可知z3(k)是葉子結點。

5 結束語

本文設計了由層次遍歷和其它遍歷構造二叉樹的三種遞歸算法。算法仿真表明，由層次遍歷和中序遍歷可以遞歸建立二叉樹，由層次遍歷和先序遍歷可以遞歸建立無出度為1的二叉樹，由層次遍歷和后序遍歷也可以遞歸建立無出度為1的二叉樹。同以前所有構造二叉樹的傳統算法一樣，本文設計的算法要求遍歷序列中不能有相同元素出現。因此，由具有相同元素的遍歷序列構造二叉樹的算法是未來研究的重點。此外，雖然遞歸算法結構清晰，方便算法設計，但遞歸算法運行效率較低，其耗費的計算時間和占用的存儲空間都比非遞歸算法要多，故本文所提問題的非遞歸算法也是接下來的研究方向。

[1] 嚴蔚敏,吳偉民.數據結構[M].北京:清華大學出版社,1992.

[2] Xiang L M,Lawi A,Ushijima K.On constructing a binary tree from its traversals[J].Research Reports on Information Science and Electrical Engineering of Kyushu University,2000, 5(1):13-18.

[3] Mikinen E.Constructing a binary tree efficiently from its traversals[J]. International Journal of Computer Mathematics, 2000,75(2):143-147.

[4] 唐自立.基于遍歷序列的構造樹的算法[J].蘇州大學學報(自然科學版),2011,27(3):26-29.

[5] 唐自立.由先序序列和結點的左孩子情況構造嚴格二叉樹的高效算法[J].南通大學學報(自然科學版)，2013,12(1):9-13.

[6] 唐自立.由后序序列和結點的雙親情況構造嚴格二叉樹的非遞歸算法[J].南通職業大學學報,2014,28(4):93-98.

[7] 劉璐.由遍歷序列構造二叉樹的非遞算法實現[J].衡水學院學報,2009,11(4):37-40.

[8] 王防修,周 康.基于二叉排序樹的二叉樹建立[J].武漢工業學院學報,2013,32(3):53-57.

[9] 李麗姝.利用遍歷序列還原二叉樹算法的研究與實現[J].電大理工, 2010,242(1) :53-54.

[10] 趙剛,李昆.由遍歷序列確定二叉樹.[J]南昌航空大學學報,2010,24(1):55-59.

[11] 朱濤.基于遍歷序列重構二叉結構樹的分析[J].紅河學院學報,2013,11(2):27-30.

[12] 化志章.基于遍歷序列恢復二叉樹的新解法及其證明[J].江西師范大學學報,2013,37(3):268-272.

A new algorithm which constructs the binary tree by using the level traversal and the other traversal

WANG Fang-xiu1,LIU Chun-hong2

(1. School of Mathematics and Computer Science,Wuhan Polytechnic University, Wuhan 430023,China;2.Jointown Pharmaceutical Group Logistics Co., Ltd. Wuhan 430040,China)

In the study which uses traversal sequences to construct the binary tree, in view of The fact that it is not used to construct the binary tree by using the level traversal and the other traversal, a new algorithm is put forward to construct the binary tree by using the level traversal and the other traversal. Considering that there is not recursive attribute in the level traversal of the left sub tree and the right sub tree, a method is designed to isolate the left subtree level traversal and the right subtree level traversal from the level traversal, and recursive property is gained through the combination with the two sub level traversals. By the recursive property of the level traversal and the inorder traversal, a recursive algorithm is designed to construct the binary tree by using the level traversal and inorder traversal. Through the research of the recursive attribute between the level traversal and the preorder traversal,a recursive algorithm is designed to construct the binary tree. By the research of the recursive attribute between the level traversal and the postorder traversal, a recursive algorithm is designed to construct the binary tree. The simulation results show that the algorithm is effective for constructing the binary tree and can provide a new algorithm for the construction of the binary tree.

Level traversal; preorder traversal; inorder traversal; postorder traversal; recursive algorithm

2016-05-26

王防修(1973-),男,副教授，E-mail:wfx323@126.com

國家自然科學基金資助項目(61179032)。

2095-7386(2016)04-0067-06

10.3969/j.issn.2095-7386.2016.04.013

TP391

A