王防修，劉春紅

(1.武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,湖北 武漢 430023;2.九州通醫(yī)藥集團(tuán)物流有限公司,湖北 武漢 430040)

一種由層次遍歷和其它遍歷構(gòu)造二叉樹(shù)的新算法

王防修1，劉春紅2

(1.武漢輕工大學(xué) 數(shù)學(xué)與計(jì)算機(jī)學(xué)院,湖北 武漢 430023;2.九州通醫(yī)藥集團(tuán)物流有限公司,湖北 武漢 430040)

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

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

1 引言

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

(1)由先序遍歷序列和中序遍歷序列構(gòu)建二叉樹(shù)；

(2)由中序遍歷序列和后序遍歷序列構(gòu)建二叉樹(shù)；

(3)由先序遍歷序列和后序遍歷序列構(gòu)建二叉樹(shù)。

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

(1)由層次遍歷序列和中序遍歷序列構(gòu)建二叉樹(shù)；

(2)由層次遍歷序列和先序遍歷序列構(gòu)建二叉樹(shù)。

(3)由層次遍歷序列和后序遍歷序列構(gòu)建二叉樹(shù)。

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

2 由層次遍歷和其它遍歷構(gòu)造二叉樹(shù)的數(shù)學(xué)原理

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

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

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

(1)

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

如果對(duì)層次遍歷序列W進(jìn)行如下劃分：

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

(2)

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

(3)

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

如果對(duì)層次遍歷序列W進(jìn)行如下重組：

W=wiW1W2

(4)

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

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

(5)

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

由Y1與W1的長(zhǎng)度相等 ，有

p=m+i-k

(6)

由Y2與W2的長(zhǎng)度相等 ，有

p=m+j-l

(7)

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

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

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

定理2 如果已知一棵二叉樹(shù)的層次遍歷序列和先序遍歷序列，并且該二叉樹(shù)沒(méi)有出度為1的結(jié)點(diǎn)，則可用遞歸算法建立該二叉樹(shù)。

證明 如果二叉樹(shù)存在出度為1的結(jié)點(diǎn)，則由層次遍歷序列和先序遍歷序列所對(duì)應(yīng)的二叉樹(shù)不唯一，故無(wú)法構(gòu)造該二叉樹(shù)。如果不存在出度為1的結(jié)點(diǎn)，則設(shè)W=wiwi+1…wj和X=xkxk+1…xl分別是二叉樹(shù)T的層次遍歷和先序遍歷。由二叉樹(shù)層次遍歷和先序遍歷的性質(zhì)可知wi和xk都是二叉樹(shù)T的根結(jié)點(diǎn)，故wi=xk。由二叉樹(shù)的性質(zhì)可知，在先序遍歷序列存在唯一的元素xm，使得xm=wi+2。因此，先序遍歷序列X可以進(jìn)行如下劃分：

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

(8)

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

如果對(duì)層次遍歷序列W進(jìn)行如下劃分：

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

(9)

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

(10)

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

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

由X1與W1的長(zhǎng)度相等 ，有

p=m+i-k-1

(11)

由X2與W2的長(zhǎng)度相等 ，有

p=m+j-l-1

(12)

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

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

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

定理3 如果已知一棵二叉樹(shù)的層次遍歷序列和后序遍歷序列，并且該二叉樹(shù)沒(méi)有出度為1的結(jié)點(diǎn)，則可用遞歸算法建立該二叉樹(shù)。

證明如果二叉樹(shù)存在出度為1的結(jié)點(diǎn)，則由層次遍歷序列和后序遍歷序列所對(duì)應(yīng)的二叉樹(shù)不唯一，故無(wú)法構(gòu)造該二叉樹(shù)。如果不存在出度為1的結(jié)點(diǎn)，則設(shè)W=wiwi+1…wj和Z=zkzk+1…zl分別是二叉樹(shù)T的層次遍歷和后序遍歷。由二叉樹(shù)層次遍歷和后序遍歷的性質(zhì)可知wi和zl都是二叉樹(shù)T的根結(jié)點(diǎn)，故wi=zl。由二叉樹(shù)的性質(zhì)可知，在后序遍歷序列存在唯一的元素zm，使得zm=wi+1。因此，后序遍歷序列Z可以進(jìn)行如下劃分：

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

(13)

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

如果對(duì)層次遍歷序列W進(jìn)行如下劃分：

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

(14)

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

(15)

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

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

由Z1與W1的長(zhǎng)度相等 ，有

p=m+i-k+1

(16)

由Z2與W2的長(zhǎng)度相等 ，有

p=m+j-l+1

(17)

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

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

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

3 由層次遍歷和其它遍歷建立二叉樹(shù)的算法設(shè)計(jì)

3.1 由層次遍歷序列和中序遍歷序列構(gòu)造二叉樹(shù)

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

(1)由層次遍歷序列W=wiwi+1…wj可知W中的第一個(gè)元素wi是二叉樹(shù)T的根結(jié)點(diǎn)。

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

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

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

(5)如果m=k，則根結(jié)點(diǎn)T沒(méi)有左孩子；否則，二叉樹(shù)的根結(jié)點(diǎn)T的左孩子是其左子樹(shù)的根結(jié)點(diǎn)，若設(shè)其左孩子為T(mén)l，則式(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，則二叉樹(shù)的根結(jié)點(diǎn)T沒(méi)有右孩子；否則，根結(jié)點(diǎn)T的右孩子是其右子樹(shù)的根結(jié)點(diǎn)。若設(shè)T的右孩子為T(mén)r，則有

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)當(dāng)遞歸過(guò)程結(jié)束時(shí)，則得到一個(gè)根結(jié)點(diǎn)為T(mén)的二叉樹(shù)。

3.2 由層次遍歷序列和先序遍歷序列構(gòu)造無(wú)出度為1的二叉樹(shù)

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

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

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

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

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

(5)如果m>k，則二叉樹(shù)的根結(jié)點(diǎn)T的左孩子是其左子樹(shù)的根結(jié)點(diǎn)，若設(shè)其左孩子為T(mén)l，則式(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，則二叉樹(shù)T既沒(méi)有左孩子又沒(méi)有右孩子。

(8)當(dāng)遞歸過(guò)程結(jié)束時(shí)，則得到一個(gè)根結(jié)點(diǎn)為T(mén)的二叉樹(shù)。

3.3 由層次遍歷序列和后序遍歷序列建立無(wú)出度為1的二叉樹(shù)

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

(1)后序遍歷序列Z=zkzk+1…zl中的元素zl是二叉樹(shù)T的根結(jié)點(diǎn)。

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

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

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

(5)如果m>k，則二叉樹(shù)的根結(jié)點(diǎn)T的左孩子是其左子樹(shù)的根結(jié)點(diǎn)，若設(shè)其左孩子為T(mén)l，則式(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，則二叉樹(shù)T既沒(méi)有左孩子又沒(méi)有右孩子。

(8)當(dāng)遞歸過(guò)程結(jié)束時(shí)，則得到一個(gè)根結(jié)點(diǎn)為T(mén)的二叉樹(shù)。

4 算法仿真

算例 用上述三種算法構(gòu)造如圖1所示的二叉樹(shù)。

圖1 二叉樹(shù)

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

表1 二叉樹(shù)的遍歷序列

i123456789wiacbdefghKyidchekafbGxiacdehkbfgzidhkecfgba

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

方法一 根據(jù)算法3.1，由層次遍歷序列W和中序遍歷序列Y構(gòu)造二叉樹(shù)的過(guò)程如下：

(4)當(dāng)m=8時(shí)，由f(W,Y,8,8,7,7)得w7(b)的左孩子為w8(f)和m=7，而由m=7可知w8(f)是葉子結(jié)點(diǎn)；由f(W,Y,9,9,9,9)得w7(b)的右孩子為w9(g)和m=9，而由m=9可知w9(g)是葉子結(jié)點(diǎn)。

(5)當(dāng)m=4時(shí)，由f(W,Y,5,5,3,3)得w4(e)的左孩子為w5(h)和m=3，而由m=3可知w5(h)是葉子結(jié)點(diǎn)；由f(W,Y,6,6,5,5)得w4(e)的右孩子為w6(k)和m=5，而由m=5可知w6(k)是葉子結(jié)點(diǎn)。

方法二 根據(jù)算法3.2，由層次遍歷序列W和先序遍歷序列X構(gòu)造二叉樹(shù)的過(guò)程如下：

(4)當(dāng)m=9時(shí)，由g(W,X,8,8,8,8)得x7(b)的左孩子為x8(f)和l=k=8，而由l=k可知x8(f)是葉子結(jié)點(diǎn)；由g(W,X,9,9,9,9)得x7(b)的右孩子為x9(g)和l=k=9，而由l=k可知x9(g)是葉子結(jié)點(diǎn)。

(5)當(dāng)m=6時(shí)，由f(W,X,5,5,5,5)得x4(e)的左孩子為x5(h)和l=k=5，而由l=k可知x5(h)是葉子結(jié)點(diǎn)；由f(W,X,6,6,6,6)得x4(e)的右孩子為x6(k)和l=k=6，而由l=k可知x6(k)是葉子結(jié)點(diǎn)。

方法三 根據(jù)算法3.3，由層次遍歷序列W和后序遍歷序列Z構(gòu)造二叉樹(shù)的過(guò)程如下：

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

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

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

本文設(shè)計(jì)了由層次遍歷和其它遍歷構(gòu)造二叉樹(shù)的三種遞歸算法。算法仿真表明，由層次遍歷和中序遍歷可以遞歸建立二叉樹(shù)，由層次遍歷和先序遍歷可以遞歸建立無(wú)出度為1的二叉樹(shù)，由層次遍歷和后序遍歷也可以遞歸建立無(wú)出度為1的二叉樹(shù)。同以前所有構(gòu)造二叉樹(shù)的傳統(tǒng)算法一樣，本文設(shè)計(jì)的算法要求遍歷序列中不能有相同元素出現(xiàn)。因此，由具有相同元素的遍歷序列構(gòu)造二叉樹(shù)的算法是未來(lái)研究的重點(diǎn)。此外，雖然遞歸算法結(jié)構(gòu)清晰，方便算法設(shè)計(jì)，但遞歸算法運(yùn)行效率較低，其耗費(fèi)的計(jì)算時(shí)間和占用的存儲(chǔ)空間都比非遞歸算法要多，故本文所提問(wèn)題的非遞歸算法也是接下來(lái)的研究方向。

[1] 嚴(yán)蔚敏,吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京:清華大學(xué)出版社,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] 唐自立.基于遍歷序列的構(gòu)造樹(shù)的算法[J].蘇州大學(xué)學(xué)報(bào)(自然科學(xué)版),2011,27(3):26-29.

[5] 唐自立.由先序序列和結(jié)點(diǎn)的左孩子情況構(gòu)造嚴(yán)格二叉樹(shù)的高效算法[J].南通大學(xué)學(xué)報(bào)(自然科學(xué)版)，2013,12(1):9-13.

[6] 唐自立.由后序序列和結(jié)點(diǎn)的雙親情況構(gòu)造嚴(yán)格二叉樹(shù)的非遞歸算法[J].南通職業(yè)大學(xué)學(xué)報(bào),2014,28(4):93-98.

[7] 劉璐.由遍歷序列構(gòu)造二叉樹(shù)的非遞算法實(shí)現(xiàn)[J].衡水學(xué)院學(xué)報(bào),2009,11(4):37-40.

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

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

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

[11] 朱濤.基于遍歷序列重構(gòu)二叉結(jié)構(gòu)樹(shù)的分析[J].紅河學(xué)院學(xué)報(bào),2013,11(2):27-30.

[12] 化志章.基于遍歷序列恢復(fù)二叉樹(shù)的新解法及其證明[J].江西師范大學(xué)學(xué)報(bào),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

國(guó)家自然科學(xué)基金資助項(xiàng)目(61179032)。

2095-7386(2016)04-0067-06

10.3969/j.issn.2095-7386.2016.04.013

TP391

A