基于遍历求二叉树的程序设计与探讨

应沈静 袁仁斌 陶骏 张海民

摘 要：阐述了非线性数据结构二叉树的基本概念，介绍了二叉树的四种遍历方法，实现了已知前序中序序求二叉树、已知后序中序序求二叉树、已知特定前序求二叉树和已知特定层次遍历求二叉树的程序，并对程序进行了详细的分析。

关键词：非线性;二叉树;遍历;前序;后序;层次

1 二叉树

有一种非线性的逻辑结构被称为二叉树，它的特点是其中的每一个结点都最多会拥有两个直接后继，而这两个直接后继拥有顺序关系，一个被称为左子树，另一个被称为右子树。而左右子树本身也是二叉树。因此由特点可以看出，二叉树是一种递归的逻辑结构，具体如图1：

二叉树T6的左子树T5和右子树T4均为二叉树，二叉树T5的左子树T1也是二叉树，二叉树T4的左子树T2和右子树T3也是二叉树。

1.1 二叉树的存储

二叉树的一个结点可能会有两个直接后继，所以二叉树的一个结点需要记录其左右子树的情况，二叉树一般采取二叉链表进行存储，一个结点有三个数据项，一个是数据域，存取结点本身的信息，另外两个是地址域，存取左右子树的存储地址，因为一棵二叉树是以其根结点作为特征值的，所以这两个地址域存取其左右子树根结点的存储地址，如果没有左右子树，这两个地址域就用空地址（NULL）表示，圖2为图1二叉树的二叉链表存储图：

二叉链表也是一种逻辑构造的存储结构，下表1所表示的是它所对应的真实物理存储结构（表中的16进制地址由操作系统按照系统情况动态分配的）：

图3 细化的二叉链表示意图

1.2 二叉树的遍历

二叉树遍历就是对二叉树按一定次序进行访问，并且每个结点仅进行一次访问。

因为二叉树不是线性的，所以二叉树访问的顺序也就会有多种，常见的二叉树遍历方式有先序遍历、中序遍历、后续遍历和层次遍历。

先序遍历的步骤为：访问根结点;访问左子树;访问右子树。在进行左子树的访问时，因为左子树也是一棵二叉树，所以对于左子树也要执行先序遍历，也就是先进行左子树的根的访问，再进行左子树的左子树的访问，最后对左子树的右子树进行访问，至子树的根对应的左右子树都为空为止。树的遍历可以通过递归实现，对应的伪代码如下：

由上可以看出，二叉树先序遍历的结果序列为：A、B、D、C、E、F;而中序遍历的步骤为：访问左子树;访问根;访问右子树。因此，图1的中序遍历结果为：D、B、A、E、C、F;后序遍历的步骤为：访问左子树;访问右子树;访问根。因此，图1的后序遍历结果为：D、B、E、F、C、A;层次遍历的步骤为：层间自上到下，层内自左到右的对每个结点进行访问。因此，图1的层次遍历为：A、B、C、D、E、F。

2 已知遍历求二叉树

已知二叉树的形状，则二叉树的遍历结果肯定是唯一的。但二叉树不是线性的，因此获知二叉树的一种遍历结果，是确定不了二叉树形状的。当仅知一棵二叉树的先序遍历结果为AB时，A是树根，而B可能是左子树，也可能是右子树，所以除了知道二叉树的一种遍历结果外，还需要有其他的先提条件才能唯一的确定一棵二叉树，有四种情况可以确定一棵二叉树。

2.1 已知前序和后序求二叉树

设一棵二叉树有n个结点，它的先序遍历结果为：a1，a2，a3……an，它的中序遍历结果为：b1，b2，b3……bn，由先序遍历可知其第一个元素a1必定是二叉树的树根，因此a1是必定会出现在中序遍历中的，因为中序遍历也需要访问树根，令bk=a1（1<=k<=n），此时bk就将中序遍历的序列分成了三个部分：树根是bk，左子树的中序遍历结果序列为b1，b2……bk1，总共k1个元素，右子树的中序遍历结果序列为bk+1，bk+2……bn，总共nk个元素。对于先序序列来讲，中序遍历左子树的元素个数与其相同，因此可以得出：a2，a3……ak是左子树的前序遍历，其余部分即ak+1，ak+2……an是右子树的前序遍历。此时已知左右子树的前序和后序，这与原问题是同一个性质的，只不过问题规模缩小了，是一个递归的问题，利用递归一直进行划分直到二叉树为空结束再返回，其对应的java源代码如下：

//二叉树结点类

public class TreeNode {

//数据域

public char data;

//左右子树

public TreeNode lchild，rchild;

//构造函数

public TreeNode（char data）

{

this.data=data;

//左右子树初始为空

this.lchild=null;

this.rchild=null;

}}

//已知前序和中序求二叉树

public TreeNode qzorder（String qstr，String zstr）

{

//字符串长度为0则返回空树

if（qstr.length（）==0||zstr.length（）==0）

return（null）;

else

{

char c=qstr.charAt（0）;

TreeNode        p=new

TreeNode（qstr.charAt（0））;

//树根位置

int x=zstr.indexOf（c）;

//递归求左右子树

p.lchild=qzorder（qstr.substring（1，（zstr.substring（0，x））.length（）+1），zstr.substring（0，x））;

p.rchild=qzorder（qstr.substring（（zstr.substring（0，x））.length（）+1），zstr.substring（x+1，zstr.length（）））;

return（p）;}}

对于图1二叉树的执行过程如图5所示：

2.2 已知中序和后序求二叉树

设一棵二叉树有n个结点，它后序遍历结果为：a1，a2，a3……an，它中序遍历结果为：b1，b2，b3……bn，由后序遍历可知其最后一个元素an必定是二叉树的树根，因而an必然出现在中序遍历中，因为中序遍历也需要进行访问树根，那么令bk=an（1<=k<=n），此时bk把中序遍历序列分成了三个部分：树根是bk，左子树中序遍历的结果序列为b1，b2……bk1，总共k1个元素，右子树中序遍历的结果序列为bk+1，bk+2……bn，总共nk个元素。对于后序序列来讲，中序遍历的左子树的元素个数与其相同，因此可以得出：a1，a3……ak1是左子树的后序遍历，其余部分即ak，ak+1……an1是右子树的后序遍歷。此时已知左右子树的中序和后序，这与原问题是同一个性质的，只不过问题规模缩小了，是一个递归的问题，利用递归一直进行划分直到二叉树为空结束再返回，其对应的java源代码如下：

//已知中序和后序求二叉树

public TreeNode zhorder（String zstr，String hstr）

{

//字符串为空返回空树

if（hstr.length（）==0||zstr.length（）==0）

return（null）;

else

{

//确定树根

char c=hstr.charAt（hstr.length（）1）;

TreeNode p=new TreeNode（c）;

int x=zstr.indexOf（c）;

//递归求左右子树

p.lchild=zhorder（zstr.substring（0，x），hstr.substring（0，x））;

p.rchild=zhorder（zstr.substring（x+1），hstr.substring（x，x+zstr.substring（x+1）.length（）））;

return（p）;

}}

对于图1二叉树的执行过程如图6所示：

如果已知后序和前序是不能求出二叉树的形状的，因为此时树根在中序的位置无法确定，例如一棵二叉树的前序是AB，后序为BA，则A是树根，B可能是左子树，也可能是右子树。

2.3 已知地址域为空的结点和前序求二叉树

仅已知前序序列是无法求得二叉树的，但是如果知道地址域为空的结点特征就能和前序序列划分出左右子树，对于图1的二叉树，每个二叉树结点的空地址域用#表示，则可表示成图7：

它通过先序遍历获得序列为：ABD###CE##F##，已知此遍历求二叉树的java代码如下：

//count为全局变量，指遍历字符串位置

private int count=0;

//创建二叉树

public TreeNode Dcreate（String str）

{//取序列结点，每次进一格

char c=str.charAt（count++）;

TreeNode p;

if（c！='#'）

{p=new TreeNode（c）;

//递归创建左右子树

p.lchild=Dcreate（str）;

p.rchild=Dcreate（str）;}

else

//为#则为空地址域

p=null;

return（p）;}

对于图1二叉树的执行过程如图8所示：

图8 前序空地址域二叉树生成过程

2.4 按层次遍历求二叉树

如果已知层次序列是无法求得二叉树的，比如二叉树的层次遍历序列为ABC，C可能位于二叉树的第二层，也可能位于二叉树的第三层，但是如果运用满二叉树的形式将二叉树进行存储，不存在的结点和结点的空地址域都用特殊字符#表示，每一个结点的顺序都与满二叉树的结点一一对应，此时根据层次遍历的序列是可以求得二叉树的，对于图1的二叉树，就可表示成图9：

图9 按照满二叉树补全的二叉树

它通过层次遍历获得的序列为：ABCD#EF####，已知此序列求二叉树的代码如下：

//str为层次遍历，i是字符位置

public TreeNode Lcreate（String str，int i）

{ char c=str.charAt（i）;

TreeNode p;

if（c！='#'）

{ p=new TreeNode（c）;

//创建左右子树

p.lchild=Lcreate（str，2*i+1）;

p.rchild=Lcreate（str，2*i+2）;}

else

//为#时返回空

p=null;

return（p）;}

當前二叉树的层次遍历序列按满二叉树的形式存储在字符串中时，根的位置必然是0，因为java语言中字符串是从0号位置开始的。如果当前结点位置为i，若其左子树存在，左子树的根的位置必然是2*i+1，这运用数学归纳法就可以证明，假设k为当前结点的序号，第一，当k=0时，其左子树的根的位置为1，这显然成立;第二，假设k=i时，其左子树的根的序号为2*i+1;第三，当k=i+1时，其左子树的根的左边是i号结点的右子树，由假设可知i号结点的左子树是2*i+1，则i号的右子树必然是2*i+2，则i+1号的左子树为2*i+2+1=2*（i+1）+1，成立。同理可证i号结点的右子树根的序号为2*i+2。当str等于“ABCD#EF####”，图10就表示图1的二叉树其执行过程：

3 结论

本文先介绍了二叉树的基本概念，二叉树是数据结构中一种重要的非线性结构，其有递归的特性，组成其的子树和其本身特性相同。介绍了二叉树的四种遍历方式，前序为先根再左再右，中序为先左再根再右，后序为先左再右再根，层次指自上到下自左到右访问二叉树，设计了四种由遍历求二叉树的程序，分别是：已知前序和中序求二叉树，已知中序和后序求二叉树，已知特定的前序求二叉树，已知特定的层次求二叉树，并详细分析了程序的实现和验证。

这四种程序的时间复杂度都是O（N），下一步的工作是利用哈希表改良这些程序以降低这些程序的时间复杂度。

参考文献：

[1]朱战立.数据结构Java语言描述[M].北京：清华大学出版社，2005.

[2]赵丹丹.二叉树的遍历及还原[J].科技创新导报，2010（7）：225.

[3]黄霞.二叉树的先序遍历和中序遍历的非递归算法[J].电脑开发与应用，2010，23（1）：5354，59.

[4]朱战立.数据结构[M].西安：西安电子科技大学出版社，2003.

[5]胡元义，黑新宏，罗作民，雷西玲，费蓉.数据结构教程[M].北京：电子工业出版社，2018.

[6]郑逢斌.计算机导论[M].北京：科学出版社，2011.

[7]郝桂芳.由二叉树的遍历序列返回二叉树[J].山西矿业学院学报，1997，15（4）：372375.

[8]杨军.题解二叉树的构造[J].学周刊·上旬刊，2016，（3）：165.

[9]康牧，陈向奎.怎样由遍历序列确定二叉树[J].洛阳师范学院学报，2003，22（2）：5658.

基金项目：安徽省教育厅高校优秀青年人才支持计划项目（项目编号：gxyq2020107）。安徽省教育厅质量工程教学研究一般项目：面向计算机类专业新生的项目设计与实践（项目编号：2020jyxm0829）。安徽省教育厅高校学科拔尖人才学术资助项目（项目编号：2020jxbjZD2020104）。安徽省科技厅重点研究与开发计划项目：基于北斗的ADSB OUT系统国产化研制及关键技术研究（项目编号：201904a05020093）。芜湖市科技项目：基于北斗的ADSB网络系统研制（项目编号：2019yf49）

作者简介：应沈静（2000— ），女，汉族，浙江丽水人，本科，主要研究方向为网络安全;袁仁斌（2000— ），女，汉族，安徽滁州人，本科，主要研究方向为大数据技术;陶骏（1978— ），男，汉族，安徽芜湖人，硕士，副教授，高级工程师，主要研究方向为网络安全;张海民（1983— ），男，汉族，安徽安庆人，硕士，讲师，主要研究方向为网络安全。