一种由遍历序列构造二叉树的改进算法
2016-10-27王防修刘春红
王防修,刘春红
(1.武汉轻工大学 数学与计算机学院,湖北 武汉 430023;2.九州通医药集团物流有限公司,湖北 武汉 430040)
一种由遍历序列构造二叉树的改进算法
王防修1,刘春红2
(1.武汉轻工大学 数学与计算机学院,湖北 武汉 430023;2.九州通医药集团物流有限公司,湖北 武汉 430040)
针对现有构造二叉树的算法无法适用于具有相同元素的遍历序列，提出了一种解决该问题的递归算法。该种算法以现有的递归算法为基础，通过引入遍历序列的标志序列，依据标志序列中元素之间的关系，从理论上证明了三种由遍历序列构造二叉树的算法都具有递归性。根据遍历序列构造二叉树的递归原理，设计了三种不同的由遍历序列构造二叉树的递归算法。通过算例仿真表明，使用笔者设计的算法可为具有相同元素的遍历序列构造二叉树。
先序遍历；中序遍历；后序遍历；标志序列；递归算法
1 引言
作为一种典型的层次结构，二叉树[1]在解决现实生活中的一些实际问题时起着非常重要的作用。因此，用遍历序列构造二叉树一直是人们关注的热点问题[2-6]。通过对二叉树遍历序列性质的研究，出现了一序列由遍历序列构造二叉树的递归[7-8]和非递归算法[9-12]。然而，无论是递归还是非递归算法，都要求遍历序列中不能有相同元素出现，否则算法无能为力。显然，这种要求会大大限制现有算法的使用范围。事实上，很多情况下的序列都会有相同元素出现，比如常见的用二叉树表示的算术表达式就是典型的存在相同运算符号和运算对象的遍历序列。因此，笔者通过为遍历序列引入标志序列，对现有递归算法进行了改进，使得改进后的算法对遍历序列没有任何条件限制，即无论序列中有无重复元素，都能用本算法构造二叉树。
2 用遍历序列建立二叉树的数学原理
定理1如果已知一棵二叉树的先序遍历序列和中序遍历序列，则可用递归算法建立该二叉树。
证明 设X=xixi+1…xj和Y=ykyk+1…yl分别是二叉树T的先序遍历序列和中序遍历序列。考虑到序列中可能存在相同元素，故需要为序列中的每个元素赋予一个不同标志，以示与其它元素的区别，故又设A=aiai+1…aj和B=bkbk+1…bl分别是先序遍历序列X和中序遍历序列Y的元素标志序列，由于X和Y的长度相等，则有j-i+1=l-k+1，即j-i=l-k。
由二叉树的遍历序列性质可知{xi,xi+1,…,xj}={yk,yk+1,…,yl}和{ai,ai+1,…,aj}={bk,bk+1,…,bl}，即X和Y是由相同的元素组成的符号序列，而A和B也是由相同的元素组成的标志序列。根据二叉树先序遍历序列的特点，元素xi是二叉树T的根结点。由于B中存在元素bm=ai，故从中序遍历序列Y的角度看，ym是二叉树T的根结点。因此，中序遍历Y及其标志序列B可以进行如下式(1)划分：
(1)
由中序遍历序列的性质可知，由于ym是二叉树的根结点，故子序列yk…ym-1和bk…bm-1分别是T的左子树的中序遍历序列和标志序列，而ym+1…yl和bm+1…bl分别是T的右子树的中序遍历序列和标志序列。由二叉树的先序遍历序列的性质可知，一定存在位置p，使先序遍历序列X及其标志序列A可以进行如下式(2)划分：
(2)
其中xi+1…xp和ai+1…ap分别是T的左子树的先序遍历序列和标志序列，而xp+1…xj和ap+1…aj分别是T的右子树的先序遍历序列和标志序列。要得到这两个先序遍历子序列及其标志序列，必须由已知条件求出位置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的值相等，故该位置是唯一的。根据求得的位置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的右子树。因此，由先序遍历和中序遍历构造二叉树实际上是一个递归过程。
递归子结构为：如果m>k，则由xi+1…xp，ai+1…ap和yk…ym-1，bk…bm-1递归建立T的左子树。如果m 递归终止条件为：如果m=k，则T无左子树。如果m=l，则T无右子树。 定理2如果已知一棵二叉树的中序遍历序列和后序遍历序列，则可用递归算法建立该二叉树。 证明设Y=yiyi+1…yj和Z=zkzk+1…zl分别是二叉树T的中序遍历序列和后序遍历序列，用B=bibi+1…bj和C=ckck+1…cl分别表示Y和Z的元素标志序列，则由Y和Z的长度相等得j-i=l-k。由一棵二叉树的中序遍历和后序遍历之间的关系如式(7)： {yi,yi+1,…,yj}={zk,zk+1,…,zl}. (7) 设Y和Z是由相同的元素组成的不同序列。由后序遍历序列的性质可知，元素zl是二叉树T的根结点。由于B中存在元素bm=cl，故从中序遍历序列Y的角度看，ym是二叉树T的根结点。因此，中序遍历序列Y及其标志序列可以进行如下式(8)划分： (8) 由中序遍历序列的性质可知，子序列yi…ym-1和bi…bm-1分别是T的左子树的中序遍历序列和标志序列，而ym+1…yj和bm+1…bj分别是T的右子树的中序遍历序列和标志序列。根据二叉树的后序遍历序列的性质可知，后序遍历序列Z及其标志序列可以进行如下式(9)划分： (9) 其中zk…zp和ck…cp分别是T的左子树的后序遍历序列和标志序列，而zp+1…zl-1和cp+1…cl-1分别是T的右子树的后序遍历序列和标志序列。由中序遍历和后序遍历之间的关系如式(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的右子树。因此，由二叉树的先序遍历序列和中序遍历序列构造二叉树也是一个递归过程。 递归子结构为：如果m>i，则由yi…ym-1，bi…bm-1和zk…zp，ck…cp递归建立T的左子树。如果m 递归终止条件为：如果m=i，则T无左子树。如果m=j，则T无右子树。 定理3如果已知一棵二叉树的先序遍历序列和后序遍历序列，并且该二叉树没有出度为1的结点，则可用递归算法建立该二叉树。 证明设X=xixi+1…xj和Z=zkzk+1…zl分别是二叉树T的先序遍历序列和后序遍历序列，又设A=aiai+1…aj和C=ckck+1…cl分别是Y和Z的标志序列。由X和Z的长度相等得出j-i=l-k。由先序遍历序列和后序遍历序列的关系可知，元素xi=zl，它们是二叉树T的根结点。由于C中存在元素cm=al+1。因此，后序遍历序列Z可以划分为： (14) 由后序遍历序列的性质可知，子序列zk…zm和ck…cm分别是T的左子树的后序遍历序列和标志序列，而zm+1…zl-1和cm+1…cl-1分别是T的右子树的后序遍历序列和标志序列。根据二叉树的先序遍历序列的性质可知，先序遍历序列X及其标志序列可以进行如下划分： (15) 其中xi+1…xp和ai+1…ap分别是T的左子树的先序遍历序列和标志序列，而xp+1…xj和ap+1…aj分别是T的右子树的先序遍历序列和标志序列。显然可得式(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的右子树。因此，由二叉树的先序遍历序列和后序遍历序列构造二叉树也是一个递归过程。 递归子结构为：如果m>i，则xi+1…xp，ai+1…ap和zk…zm，ck…cm递归建立T的左子树。如果m 递归终止条件为：如果i=j，则T是叶子结点，即T既无无左子树又无右子树。 3.1由先序遍历序列和中序遍历序列构造二叉树 为方便算法设计，不妨设建立二叉树的递归函数为T=f(X,A,Y,B,i,j,k,l)，则其递归过程可以描述如下： (1)由先序遍历序列X=xixi+1…xj可知X中的第一个元素x是二叉树T的根结点。 (2)从标志序列B中查找到bm=ai。 (3)如果m=k，则根结点T没有左孩子；否则，二叉树的根结点T的左孩子是其左子树的根结点，若设其左孩子为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，则二叉树的根结点T没有右孩子；否则，根结点T的右孩子是其右子树的根结点。若设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)当递归过程结束时，则得到一个根结点为T的二叉树。 3.2由中序遍历序列和后序遍历序列构造二叉树 为方便算法描述，设建立二叉树的递归函数为T=g(Y,B,Z,C,i,j,k,l)，其递归过程描述如下： (1)后序遍历序列Z=zkzk+1…zl中的元素zi是二叉树T的根结点； (2)从标志序列B中找到bm=cl。 (3)如果m=i，则二叉树T没有左子树；否则，二叉树T的左子树的根结点为 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的右子树的根结点为 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的二叉树 为方便算法描述，设建立二叉树的递归函数为T=h(X,A,Z,C,i,j,k,l)，则其递归过程描述如下： (1)先序遍历序列X=xixi+1…xj中的元素xi是二叉树T的根结点。 (2)从标志序列C中找到cm=al+1。 (3)如果j=i或l=k，则二叉树T没有左子树和右子树；否则，二叉树T的左子树的根结点为 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的右子树的根结点为 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) 算例 试用上述三种算法构造如图1所示的算术表达式的二叉树。 解 从二叉树中可以看出，树中既有相同的运算对象(运算对象a和b都出现两次)，又有相同的运算符号(其中“+”出现三次，“*”出现两次)。因此，用传统算法不能建立该二叉树。 为了将二叉树中的相同元素区分开来，不妨给树中每个元素赋予一个不同的整数标志。图2给出了二叉树中每个元素对应的整数标志。 图1 表达式a*b+(a/b+(c+d)*f)的二叉树 图2 二叉树中元素的对应标志 因此，由图1和图2可以得到如表1所示的遍历序列和标志序列。 表1二叉树的遍历序列和标志序列 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分别表示二叉树的先序遍历序列及其标志序列，Y=y1……y13和B=b1……b13分别表示二叉树的中序遍历序列及其标志序列，而Z=z1……z13和C=c1……c13分别表示二叉树的后序遍历序列及其标志序列。 方法一根据算法2.1，由先序遍历序列及其标志序列X,A和中序遍历序列及其标志序列Y，B构造二叉树的过程如下： (1)由f(X,A,Y,B,1,13,1,13)得根结点为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)当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)当m=12时，由f(X,A,Y,B,10,12,9,11)可以得到x9(*)的左孩子为x10(+)，而x10(+)的左孩子为x11(c)和右孩子为x12(d)。 方法二根据算法2.2，由中序遍历序列及其标志序列Y,B和后序遍历序列及其标志序列Z，C构造二叉树的过程如下： (1)由g(Y,B,Z,C,1,13,1,13)得到根结点为z13(+)和m=4。 (2)当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)当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)当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)当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)当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)当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)。 方法三根据算法2.3，由先序遍历序列及其标志序列X,A和后序遍历序列及其标志序列Z，C构造二叉树的过程如下： (1)由h(X,A,Z,C,1,13,1,13)得到根结点为x1(+)和m=3。 (2)当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)当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)当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)当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)当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)当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)。 如果遍历序列中存在相同元素，则现有算法无法根据该遍历序列构造二叉树。笔者通过引入标志序列对现有的递归算法进行了改进，使得改进后的算法适用于任何遍历序列(无论该序列有无相同元素)。算法仿真表明，该算法对具有相同元素的序列构造二叉树行之有效。由于本算法对遍历序列没有任何限制性要求，故其适用范围得到大大延伸。虽然递归算法结构清晰，方便算法设计，但是递归算法运行效率较低，其耗费的计算时间和占用的存储空间都比非递归算法要多，故本文所提问题的非递归算法是接下来的研究方向。此外，由层次遍历序列和其它遍历序列构造二叉树的算法尚未被研究，故也是未来的研究方向。 [1]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,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]唐自立.基于遍历序列的构造树的算法[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. 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. 国家自然科学基金资助项目(61179032). 2095-7386(2016)03-0068-06 10.3969/j.issn.2095-7386.2016.03.013 TP 391 A3 由遍历序列建立二叉树的算法设计
4 算法仿真
5 结束语
