一種由遍歷序列構(gòu)造二叉樹的改進算法

王防修,劉春紅

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

?

一種由遍歷序列構(gòu)造二叉樹的改進算法

王防修1,劉春紅2

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

針對現(xiàn)有構(gòu)造二叉樹的算法無法適用于具有相同元素的遍歷序列，提出了一種解決該問題的遞歸算法。該種算法以現(xiàn)有的遞歸算法為基礎(chǔ)，通過引入遍歷序列的標(biāo)志序列，依據(jù)標(biāo)志序列中元素之間的關(guān)系，從理論上證明了三種由遍歷序列構(gòu)造二叉樹的算法都具有遞歸性。根據(jù)遍歷序列構(gòu)造二叉樹的遞歸原理，設(shè)計了三種不同的由遍歷序列構(gòu)造二叉樹的遞歸算法。通過算例仿真表明，使用筆者設(shè)計的算法可為具有相同元素的遍歷序列構(gòu)造二叉樹。

先序遍歷；中序遍歷；后序遍歷；標(biāo)志序列；遞歸算法

1　引言

作為一種典型的層次結(jié)構(gòu)，二叉樹[1]在解決現(xiàn)實生活中的一些實際問題時起著非常重要的作用。因此，用遍歷序列構(gòu)造二叉樹一直是人們關(guān)注的熱點問題[2-6]。通過對二叉樹遍歷序列性質(zhì)的研究，出現(xiàn)了一序列由遍歷序列構(gòu)造二叉樹的遞歸[7-8]和非遞歸算法[9-12]。然而，無論是遞歸還是非遞歸算法，都要求遍歷序列中不能有相同元素出現(xiàn)，否則算法無能為力。顯然，這種要求會大大限制現(xiàn)有算法的使用范圍。事實上，很多情況下的序列都會有相同元素出現(xiàn)，比如常見的用二叉樹表示的算術(shù)表達(dá)式就是典型的存在相同運算符號和運算對象的遍歷序列。因此，筆者通過為遍歷序列引入標(biāo)志序列，對現(xiàn)有遞歸算法進行了改進，使得改進后的算法對遍歷序列沒有任何條件限制，即無論序列中有無重復(fù)元素，都能用本算法構(gòu)造二叉樹。

2　用遍歷序列建立二叉樹的數(shù)學(xué)原理

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

證明 設(shè)X=xixi+1…xj和Y=ykyk+1…yl分別是二叉樹T的先序遍歷序列和中序遍歷序列。考慮到序列中可能存在相同元素，故需要為序列中的每個元素賦予一個不同標(biāo)志，以示與其它元素的區(qū)別，故又設(shè)A=aiai+1…aj和B=bkbk+1…bl分別是先序遍歷序列X和中序遍歷序列Y的元素標(biāo)志序列，由于X和Y的長度相等，則有j-i+1=l-k+1，即j-i=l-k。

由二叉樹的遍歷序列性質(zhì)可知{xi,xi+1,…,xj}={yk,yk+1,…,yl}和{ai,ai+1,…,aj}={bk,bk+1,…,bl}，即X和Y是由相同的元素組成的符號序列，而A和B也是由相同的元素組成的標(biāo)志序列。根據(jù)二叉樹先序遍歷序列的特點，元素xi是二叉樹T的根結(jié)點。由于B中存在元素bm=ai，故從中序遍歷序列Y的角度看，ym是二叉樹T的根結(jié)點。因此，中序遍歷Y及其標(biāo)志序列B可以進行如下式(1)劃分：

(1)

由中序遍歷序列的性質(zhì)可知，由于ym是二叉樹的根結(jié)點，故子序列yk…ym-1和bk…bm-1分別是T的左子樹的中序遍歷序列和標(biāo)志序列，而ym+1…yl和bm+1…bl分別是T的右子樹的中序遍歷序列和標(biāo)志序列。由二叉樹的先序遍歷序列的性質(zhì)可知，一定存在位置p，使先序遍歷序列X及其標(biāo)志序列A可以進行如下式(2)劃分：

(2)

其中xi+1…xp和ai+1…ap分別是T的左子樹的先序遍歷序列和標(biāo)志序列，而xp+1…xj和ap+1…aj分別是T的右子樹的先序遍歷序列和標(biāo)志序列。要得到這兩個先序遍歷子序列及其標(biāo)志序列，必須由已知條件求出位置p。由于先序遍歷子序列和中序遍歷子序列的長度相等，則有：

{xi+1,…,xp}={yk,…,ym-1}.

(3)

{xp+1,…,xj}={ym+1,…,yl}.

(4)

由式(3)，式(4)可知子序列的長度相等，故有：

p-(i+1)+1=m-1-k+1.

(5)

j-(p+1)+1=l-(m+1)+1.

(6)

由式(5)，式(6)分別得位置p=m+i-k和位置p=m+j-l。

由于j-i=l-k，由式(5)和式(6)可得兩個位置p的值相等，故該位置是唯一的。根據(jù)求得的位置p，可以得到兩個子序列xi+1…xp和xp+1…xj。因此，xi+1…xp和yk…ym-1分別表示二叉樹T的左子樹的先序遍歷子序列和中序遍歷子序列，而xp+1…xj和ym+1…yl分別表示二叉樹T的右子樹的先序遍歷子序列和中序遍歷子序列。同理，由xi+1…xp，ai+1…ap和yk…ym-1，bk…bm-1可求出T的左子樹，而由xp+1…xj，ap+1…aj和ym+1…yl，bm+1…bl可以求出T的右子樹。因此，由先序遍歷和中序遍歷構(gòu)造二叉樹實際上是一個遞歸過程。

遞歸子結(jié)構(gòu)為：如果m>k，則由xi+1…xp，ai+1…ap和yk…ym-1，bk…bm-1遞歸建立T的左子樹。如果m

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

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

證明設(shè)Y=yiyi+1…yj和Z=zkzk+1…zl分別是二叉樹T的中序遍歷序列和后序遍歷序列，用B=bibi+1…bj和C=ckck+1…cl分別表示Y和Z的元素標(biāo)志序列，則由Y和Z的長度相等得j-i=l-k。由一棵二叉樹的中序遍歷和后序遍歷之間的關(guān)系如式(7)：

{yi,yi+1,…,yj}={zk,zk+1,…,zl}.

(7)

設(shè)Y和Z是由相同的元素組成的不同序列。由后序遍歷序列的性質(zhì)可知，元素zl是二叉樹T的根結(jié)點。由于B中存在元素bm=cl，故從中序遍歷序列Y的角度看，ym是二叉樹T的根結(jié)點。因此，中序遍歷序列Y及其標(biāo)志序列可以進行如下式(8)劃分：

(8)

由中序遍歷序列的性質(zhì)可知，子序列yi…ym-1和bi…bm-1分別是T的左子樹的中序遍歷序列和標(biāo)志序列，而ym+1…yj和bm+1…bj分別是T的右子樹的中序遍歷序列和標(biāo)志序列。根據(jù)二叉樹的后序遍歷序列的性質(zhì)可知，后序遍歷序列Z及其標(biāo)志序列可以進行如下式(9)劃分：

(9)

其中zk…zp和ck…cp分別是T的左子樹的后序遍歷序列和標(biāo)志序列，而zp+1…zl-1和cp+1…cl-1分別是T的右子樹的后序遍歷序列和標(biāo)志序列。由中序遍歷和后序遍歷之間的關(guān)系如式(10)和式(11)：

{zk,…,zp}={yi,…,ym-1},

(10)

{zp+1,…,zl-1}={ym+1,…,yj}.

(11)

由于子序列的長度相等，則有：

p-k+1=m-1-i+1.

(12)

(l-1)-(p+1)+1=j-(m+1)+1.

(13)

由式(12)和式(13)分別得p=k+m-i-1，和p=l+m-j-1。

由于j-i=l-k，可以得到這兩個p的值是相等的。同理，由中序遍歷子序列yi…ym-1，bi…bm-1和后序遍歷子序列zk…zp，ck…cp可以得到二叉樹T的左子樹。由中序遍歷子序列ym+1…yj，bm+1…bj和后序遍歷子序列zp+1…zl-1，cp+1…cl-1可以得到二叉樹T的右子樹。因此，由二叉樹的先序遍歷序列和中序遍歷序列構(gòu)造二叉樹也是一個遞歸過程。

遞歸子結(jié)構(gòu)為：如果m>i，則由yi…ym-1，bi…bm-1和zk…zp，ck…cp遞歸建立T的左子樹。如果m

遞歸終止條件為：如果m=i，則T無左子樹。如果m=j，則T無右子樹。

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

證明設(shè)X=xixi+1…xj和Z=zkzk+1…zl分別是二叉樹T的先序遍歷序列和后序遍歷序列，又設(shè)A=aiai+1…aj和C=ckck+1…cl分別是Y和Z的標(biāo)志序列。由X和Z的長度相等得出j-i=l-k。由先序遍歷序列和后序遍歷序列的關(guān)系可知，元素xi=zl，它們是二叉樹T的根結(jié)點。由于C中存在元素cm=al+1。因此，后序遍歷序列Z可以劃分為：

(14)

由后序遍歷序列的性質(zhì)可知，子序列zk…zm和ck…cm分別是T的左子樹的后序遍歷序列和標(biāo)志序列，而zm+1…zl-1和cm+1…cl-1分別是T的右子樹的后序遍歷序列和標(biāo)志序列。根據(jù)二叉樹的先序遍歷序列的性質(zhì)可知，先序遍歷序列X及其標(biāo)志序列可以進行如下劃分：

(15)

其中xi+1…xp和ai+1…ap分別是T的左子樹的先序遍歷序列和標(biāo)志序列，而xp+1…xj和ap+1…aj分別是T的右子樹的先序遍歷序列和標(biāo)志序列。顯然可得式(16)和式(17)：

{zk,…,zm}={xi+1,…,xp}.

(16)

{zm+1,…,zl-1}={xp+1,…,xj}.

(17)

由于子序列的長度相等，則有：

p-i-1=m-k.

(18)

(l-1)-(m+1)=j-(p+1).

(19)

由式(18)和式(19)分別得p=i+m-k+1和p=j+m-l+1。

由于j-i=l-k，可得這兩個p的值是相等的。因此，由先序遍歷子序列xi+1…xp，ai+1…ap和后序遍歷子序列zk…zm，ck…cm可以得到二叉樹T的左子樹。由先序遍歷子序列xp+1…xj，ap+1…aj和后序遍歷子序列zm+1…zl-1，cm+1…cl-1可以得到二叉樹T的右子樹。因此，由二叉樹的先序遍歷序列和后序遍歷序列構(gòu)造二叉樹也是一個遞歸過程。

遞歸子結(jié)構(gòu)為：如果m>i，則xi+1…xp，ai+1…ap和zk…zm，ck…cm遞歸建立T的左子樹。如果m

遞歸終止條件為：如果i=j，則T是葉子結(jié)點，即T既無無左子樹又無右子樹。

3　由遍歷序列建立二叉樹的算法設(shè)計

3.1由先序遍歷序列和中序遍歷序列構(gòu)造二叉樹

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

(1)由先序遍歷序列X=xixi+1…xj可知X中的第一個元素x是二叉樹T的根結(jié)點。

(2)從標(biāo)志序列B中查找到bm=ai。

(3)如果m=k，則根結(jié)點T沒有左孩子；否則，二叉樹的根結(jié)點T的左孩子是其左子樹的根結(jié)點，若設(shè)其左孩子為Tl，則有

Tl=f(X,A,Y,B,i+1,m+i-k,k,m-1).

(20)

或者

Tl=f(X,A,Y,B,i+1,m+j-l,k,m-1).

(21)

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

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

(22)

或者

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

(23)

(5)當(dāng)遞歸過程結(jié)束時，則得到一個根結(jié)點為T的二叉樹。

3.2由中序遍歷序列和后序遍歷序列構(gòu)造二叉樹

為方便算法描述，設(shè)建立二叉樹的遞歸函數(shù)為T=g(Y,B,Z,C,i,j,k,l)，其遞歸過程描述如下：

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

(2)從標(biāo)志序列B中找到bm=cl。

(3)如果m=i，則二叉樹T沒有左子樹；否則，二叉樹T的左子樹的根結(jié)點為

g(Y,B,Z,C,i,m-1,k,m+k-i-1).

(24)

或者

g(Y,B,Z,C,i,m-1,k,l+m-j-1).

(25)

(4)如果m=j，則二叉樹T沒有右子樹；否則，二叉樹T的右子樹的根結(jié)點為

g(Y,B,Z,C,m+1,j,k+m-i,l-1).

(26)

或者

g(Y,B,Z,C,m+1,j,l+m-j,l-1).

(27)

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

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

(1)先序遍歷序列X=xixi+1…xj中的元素xi是二叉樹T的根結(jié)點。

(2)從標(biāo)志序列C中找到cm=al+1。

(3)如果j=i或l=k，則二叉樹T沒有左子樹和右子樹；否則，二叉樹T的左子樹的根結(jié)點為

h(X,A,Z,C,i+1,i+m-k+1,k,m).

(28)

或者

h(X,A,Z,C,i+1,j+m-l+1,k,m).

(29)

二叉樹T的右子樹的根結(jié)點為

h(X,A,Z,C,i+m-k+2,j,m+1,l-1).

(30)

或者

h(X,A,Z,C,j+m-l+2,j,m+1,l-1).

(31)

4　算法仿真

算例 試用上述三種算法構(gòu)造如圖1所示的算術(shù)表達(dá)式的二叉樹。

解 從二叉樹中可以看出，樹中既有相同的運算對象(運算對象a和b都出現(xiàn)兩次)，又有相同的運算符號(其中“+”出現(xiàn)三次，“*”出現(xiàn)兩次)。因此，用傳統(tǒng)算法不能建立該二叉樹。

為了將二叉樹中的相同元素區(qū)分開來，不妨給樹中每個元素賦予一個不同的整數(shù)標(biāo)志。圖2給出了二叉樹中每個元素對應(yīng)的整數(shù)標(biāo)志。

圖1　表達(dá)式a*b+(a/b+(c+d)*f)的二叉樹

圖2　二叉樹中元素的對應(yīng)標(biāo)志

因此，由圖1和圖2可以得到如表1所示的遍歷序列和標(biāo)志序列。

表1二叉樹的遍歷序列和標(biāo)志序列

ixiaiyibizic1+3a1a12*5*5b123a1b12*54b12+3a65+2a6b86/4/4/47a6b8c108b8+2d119*9c10+1310+13+13f711c10d11*912d11*9+213f7f7+3

在表1中，X=x1……x13和A=a1……a13分別表示二叉樹的先序遍歷序列及其標(biāo)志序列，Y=y1……y13和B=b1……b13分別表示二叉樹的中序遍歷序列及其標(biāo)志序列，而Z=z1……z13和C=c1……c13分別表示二叉樹的后序遍歷序列及其標(biāo)志序列。

方法一根據(jù)算法2.1，由先序遍歷序列及其標(biāo)志序列X,A和中序遍歷序列及其標(biāo)志序列Y，B構(gòu)造二叉樹的過程如下：

(1)由f(X,A,Y,B,1,13,1,13)得根結(jié)點為x1(+)和m=4。

(2)由于m=4，故由f(X,A,Y,B,2,4,1,3)可以得到x1(+)的左孩子為x2(*)和m=2，而由m=2可以得到x2(*)的左孩子x3(a)和右孩子x4(b)。同樣，由于m=4，由f(X,A,Y,B,5,13,5,13)可以得到x1(+)的右孩子為x5(+)和m=8。

(3)當(dāng)m=8時，由f(X,A,Y,B,6,8,5,7)可以得到x5(+)的左孩子為x6(/)，以及x6(/)的左孩子x7(a)和右孩子x8(b)。由f(X,A,Y,B,9,13,9,13)可以得到x5(+)的右孩子x9(*)和m=12，而x9(*)的右孩子為x13(f)。

(4)當(dāng)m=12時，由f(X,A,Y,B,10,12,9,11)可以得到x9(*)的左孩子為x10(+)，而x10(+)的左孩子為x11(c)和右孩子為x12(d)。

方法二根據(jù)算法2.2，由中序遍歷序列及其標(biāo)志序列Y,B和后序遍歷序列及其標(biāo)志序列Z，C構(gòu)造二叉樹的過程如下：

(1)由g(Y,B,Z,C,1,13,1,13)得到根結(jié)點為z13(+)和m=4。

(2)當(dāng)m=4時，由g(Y,B,Z,C,1,3,1,3)得到z13(+)的左孩子為z3(*)和m=4，由g(Y,B,Z,C,5,13,4,12)得到z13(+)的右孩子為z12(+)和m=8。

(3)當(dāng)m=2時，由g(Y,B,Z,C,1,1,1,1)得到z3(*)的左孩子z1(a)，而由g(Y,B,Z,C,3,3,2,2)得到z3(*)的右孩子z2(b)。

(4)當(dāng)m=8時，由g(Y,B,Z,C,5,7,4,6)得到x12(+)的左孩子z6(/)和m=6，而由g(Y,B,Z,C,9,13,7,11)得到z12(+)的右孩子z11(*)和m=12。

(5)當(dāng)m=6時，由g(Y,B,Z,C,5,5,4,4)得到z6(/)的左孩子z4(a)，而由g(Y,B,Z,C,7,7,5,5)得到z6(/)的右孩子z5(b)。

(6)當(dāng)m=12時，由g(Y,B,Z,C,9,11,7,9)得到z11(*)的左孩子z9(+)和m=10，而由g(Y,B,Z,C,13,13,10,10)得到z11(*)的右孩子z10(f)。

(7)當(dāng)m=10時，由g(Y,B,Z,C,9,9,7,7)得到z9(+)的左孩子z7(c)，由g(Y,B,Z,C,11,11,8,8)得到z9(+)的右孩子z8(d)。

方法三根據(jù)算法2.3，由先序遍歷序列及其標(biāo)志序列X,A和后序遍歷序列及其標(biāo)志序列Z，C構(gòu)造二叉樹的過程如下：

(1)由h(X,A,Z,C,1,13,1,13)得到根結(jié)點為x1(+)和m=3。

(2)當(dāng)m=3時，由h(X,A,Z,C,2,4,1,3)得到x1(+)的左孩子為x2(*)和m=1，由h(X,A,Z,C,5,13,4,12)得到x1(+)的右孩子為x5(+)和m=6。

(3)當(dāng)m=1時，由h(X,A,Z,C,3,3,1,1)得到x2(*)的左孩子x3(a)，而由h(X,A,Z,C,4,4,2,2)得到x2(*)的右孩子x4(b)。

(4)當(dāng)m=6時，由h(X,A,Z,C,6,8,4,6)得到x5(+)的左孩子x6(/)和m=4，而由h(X,A,Z,C,9,13,7,11)得到x5(+)的右孩子x9(*)和m=9。

(5)當(dāng)m=4時，由h(X,A,Z,C,7,7,4,4)得到x6(/)的左孩子x7(a)，而由h(X,A,Z,C,8,8,5,5)得到x6(/)的右孩子x8(b)。

(6)當(dāng)m=9時，由h(X,A,Z,C,10,12,7,9)得到x9(*)的左孩子x10(+)和m=7，而由h(X,A,Z,C,13,13,10,10)得到x9(*)的右孩子x13(f)。

(7)當(dāng)m=7時，由h(X,A,Z,C,11,11,9,9)得到x10(+)的左孩子x11(c)，由h(X,A,Z,C,12,12,8,8)得到x10(+)的右孩子x12(d)。

5　結(jié)束語

如果遍歷序列中存在相同元素，則現(xiàn)有算法無法根據(jù)該遍歷序列構(gòu)造二叉樹。筆者通過引入標(biāo)志序列對現(xiàn)有的遞歸算法進行了改進，使得改進后的算法適用于任何遍歷序列(無論該序列有無相同元素)。算法仿真表明，該算法對具有相同元素的序列構(gòu)造二叉樹行之有效。由于本算法對遍歷序列沒有任何限制性要求，故其適用范圍得到大大延伸。雖然遞歸算法結(jié)構(gòu)清晰，方便算法設(shè)計，但是遞歸算法運行效率較低，其耗費的計算時間和占用的存儲空間都比非遞歸算法要多，故本文所提問題的非遞歸算法是接下來的研究方向。此外，由層次遍歷序列和其它遍歷序列構(gòu)造二叉樹的算法尚未被研究，故也是未來的研究方向。

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

[2]Xiang L,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, 2007,75(2):143-147.

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

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

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

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

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

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

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

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

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

An improved algorithm for constructing two binary trees by traversing sequences

WANGFang-xiu1,LIUChun-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 view of the present algorithm can not be applied to construct the binary tree by using the traversal sequence which has the same elements, this paper presents a recursive algorithm to solve the problem. Based on the existing recursive algorithm, this algorithm introduces the symbol sequence of the traversal sequence.According to the relationship among the elements in the symbol sequence, the three algorithms are proved theoretically to be recursive for using the traversal sequences to construct the binary tree. Based on the recursive principle of constructing the two binary tree by the travel sequences, three different recursive algorithms are designed to construct the binary tree. Simulation results show that the algorithm can be used to construct the two binary tree by using the traversal sequences in which there are the same elements.

preorder traversal; inorder traversal; postorder traversal; flag sequence; recursive algorithm

2016-04-08.

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

國家自然科學(xué)基金資助項目(61179032).

2095-7386(2016)03-0068-06

10.3969/j.issn.2095-7386.2016.03.013

TP 391

A