基于遍历序列重构二叉结构树的分析

朱 涛

（陕西理工学院数学与计算机科学学院，陕西汉中 723000）

引言

二叉树在计算机科学中有着重要的应用，有好多问题都是借助二叉树这种结构来描述.给定了二叉树，依据相应的遍历算法，能够方便的遍历它的所有结点，并得到相应的遍历序列.但在有些应用中，需要由二叉树的遍历序列反过来刻画它们所表示的二叉树，对于这样的问题，找出遍历序列间的关系及相应的重构方法对研究相关的问题是十分必要的.由于二叉树的基本结构是由根结点、左子树和右子树三部分构成，因此对二叉树的遍历实际上是对这三部分的遍历.对二叉树遍历以后，会得到一个线性的遍历序列，在这个线性遍历序列中，每个结点（除第一个和最后一个）有且仅有一个直接前驱和直接后继，而某一结点的直接前驱和直接后继又未必是该结点的左子树或者右子树，因此当以该序列来重新构造二叉结构树时，就难以实现.徐志烽[1]给出了一种通过先序序列和中序序列构建二叉树的算法，但文献[1]中没有给出严密的理论证明，左正康等[2]给出了后序遍历二叉树非递归算法的推导及形式化证明.但是以上研究都很少从遍历序列重构二叉树的角度给出严格的理论分析和证明.本文将对由遍历序列重新构造二叉结构树进行严格的理论分析及证明，并给出通过两种遍历序列如何唯一确定二叉结构树的实现算法.

1 二叉树的遍历

对二叉树的遍历运算是将二叉树中结点按一定规律线性化的过程，从这个意义上说，遍历二叉树就是将非线性化的结构变成线性化的访问序列.由二叉树的递归定义[3]，二叉树的基本结构是由根结点、左子树、右子树三个基本单元组成，因此只要依次遍历了这三部分，就遍历了整个二叉树.在文献[3]中，限制结点的先左后右原则后，得到了三种二叉树遍历算法，分别称之为先（根）序遍历，记为DLR（D表示二叉树的根节点，L表示二叉树的左孩子，R表示二叉树的右孩子，文后各符号含义相同），中(根)序遍历，记为LDR，后根序遍历，记为LRD.文献[3]中还给出了下述三种不同二叉树遍历的递归算法.

先序遍历算法描述为：

若二叉树为空，则空操作；否则

（1）访问根结点；

（2）先序遍历左子树；

（3）先序遍历右子树.

中序遍历算法描述为：

若二叉树为空，则空操作；否则

（1）中序遍历左子树；

（2）访问根结点；

（3）中序遍历右子树.

图1 二叉树

后序遍历算法描述为：

若二叉树为空，则空操作；否则

（1）后续遍历左子树；

（2）后续遍历右子树；

（3）访问根节点.

这三种遍历算法的不同之处仅在于其对于访问根结点、左子树和右子树的先后关系不同，依据这三种算法，可分别获得不同的遍历序列，如先序遍历序列、中序遍历序列和后序遍历序列.对于图1所示的二叉树，可分别得到不同的遍历序列.先根序遍历图1所示二叉树后的先序序列为：ABCDEFGH；中根序遍历图1所示二叉树后的中序序列为：CBEDAGHF；后根序遍历图1所示二叉树后的后序序列为：CEDBHGFA.

2 遍历序列重构二叉树的条件分析

对于一棵非空二叉树，它的先序遍历序列、中序遍历序列或后序遍历序列有可能相同，但三种遍历序列不可能都相同.另外，每棵二叉树的先序遍历序列、中序遍历序列和后序遍历序列都是唯一的.那么对于一个给定的二叉树，要得到它的遍历序列很容易得到，反过来，由遍历序列能否确定一棵二叉树吗？是否唯一？显然，由一种遍历序列不能唯一确定一棵二叉树.本文将对三种遍历序列的组合唯一确定二叉树进行讨论.

定理1:给定一棵二叉树的先序序列和中序序列，可唯一确定一棵二叉树.

证明 设二叉树结点的个数为n(n≥0).

当n=0时，一棵空二叉树的中序序列和先序序列都为空，可以唯一确定该二叉树，命题成立.

定理2:给定一棵二叉树的中序序列和后序序列，可唯一确定一棵二叉树.

证明:设二叉树结点的个数为n(n≥0).

当n=0时，一棵空二叉树的中序序列和后序序列都为空，可以唯一确定该二叉树，命题成立.

定理3:给定一棵二叉树的先序序列和后序序列，可确定一棵二叉树，但不唯一.证明:由于先序序列中第一个结点是根结点，后续序列中最后面一个结点是根结点，这样，在先序序列中除第一个节点外以及在后续序列中除最后一个结点外，剩余的序列无法区分左子树和右子树，所以依据剩余的序列来构造二叉树，就会得到不同的二叉树，所以确定的二叉树不唯一.

3 遍历序列重构二叉树的算法及实现

根据上文分析，有两种序列组合可以唯一确定一棵二叉树，这两种序列组合分别为先序序列和中序序列以及中序序列和后序序列.张国[4]分析了递归算法和非递归算法差别，朱振元等[5]给出了一种递归算法转化为非递归算法的可能.下边对这两种组合序列重构二叉树描述了算法步骤，并对其递归实现算法进行了叙述.

3.1 先序序列和中序序列重构二叉树的递归算法及实现

由先序序列和中序序列重构二叉树的算法描述为：

（1）若二叉树为空，返回空；

（2）若不空，由先序序列得到二叉树的根结点;

（3）由上述（2）的根结点把中序序列分为左子树的中序序列和右子树的中序序列两个部分；

（4）根据上述左子树的中序序列个数找到对应的左子树先序序列和右子树的先序序列；

（5）按上述（2）、（3）、（4）同样的方法依次类推，直到所得左、右子树只含一个结点为止.

该算法的递归实现描述如下：

输入参数是二叉树的先序序列preorder和中序序列inorder，长度n，返回二叉树根结点指针，bitree是结点类型名.

3.2 中序序列和后序序列重构二叉树的递归算法及实现

由先序序列和中序序列重构二叉树的算法描述为：

（1）若二叉树为空，返回空；

（2）若不空，由后序序列得到二叉树的根结点；

（3）由上述（2）的根结点把中序序列分为左子树的中序序列和右子树的中序序列两个部分；

（4）根据上述左子树的中序序列个数找到对应的左子树后序序列和右子树的后序序列；

（5）按上述（2）、（3）、（4）同样的方法依次类推，直到所得左、右子树只含一个结点为止.

该算法的递归实现描述如下：

4 结束语

二叉树是一种树型结构，属于典型的非线性结构，也是一种简单有效地组织数据的方式.对二叉树的遍历是对二叉树各种操作的基础，也是对二叉树进行的一种常规运算.文中主要分析了基于遍历序列重构二叉树条件，提出了两种遍历序列相结合重构二叉树的递归算法，并给出了相应算法的实现。对于给定一棵二叉树的先序序列和后序序列，在什么情况下可以确定一棵二叉树及是否唯一的问题，文中只是给出了简单的理论分析，没有详细叙述。本文的下一步工作，将是对这种情况进一步给出形式证明，并分情形给予分析。

[1]徐志烽.通过先序序列和中序序列建二叉树[J].中山大学研究生学刊:自然科学(医学版),2004(4):119—125.

[2]左正康,游珍,薛锦云.后序遍历二叉树非递归算法的推导及形式化证明[J].计算机工程与科学,2010,32(3):119—123.

[3]严蔚敏,吴伟民.数据结构[M].北京:清华大学出版社,1992:125—131.

[4]张国.基于递归算法的非递归实现研究[J].长江大学学报:自然科学版,2009,6(3):223-225.

[5]朱振元,朱承.递归算法的非递归化实现[J].小型微型计算机系统, 2003,(3).

[6]朱涛.基于遍历二叉树的方法判断完全二叉树[J].红河学院学报:2005,6(3):47-48.