二叉树的遍历探究与应用
开篇：润墨网以专业的文秘视角，为您筛选了一篇二叉树的遍历探究与应用范文，如需获取更多写作素材，在线客服老师一对一协助。欢迎您的阅读与分享！
摘要：通过对同一棵二叉树的前序遍历、中序遍历、后序遍历及层次遍历得到四个不同序列的分析，概括出二叉树的前序遍历、中序遍历、后序遍历及层次遍历序列间的关系，确定对应的二叉树。
关键词：二叉树；二叉树的遍历；层次遍历
中图分类号：TP311文献标识码：A文章编号：1009-3044(2008)23-1014-02
The Research and Application of Traversing Binary Tree
SHENG Kui
(Bozhou Vocational and Technical College, Bozhou 236800, China)
Abstract: This paper summarizes the relation of the four different array though the analysis of getting four arrayfrom the same binary tree using four different algorithm: preorder traversal,inorder traversal,postorder traversal and level traversal,to determine the corresponding binary tree.
Key words: binary tree; binary tree traversal;level traversal
二叉树是数据结构非常重要的一种非线性数据结构，是树型结构的一种特殊形式，广泛应用于计算机科学和信息科学。在对二叉树的操作中，遍历是一种重要的操作，在现在生活中有许多数据关系，可推广为二叉树遍历的形式，如在二叉树查找二叉树中的某些结点，或者是通过对二叉树中所有结点逐一处理而达到某些运算的目的。但许多教材中都指出二叉树的遍历是二叉树其它操作的基础，但由于篇幅方面的限制，没有对二叉树的遍历作更深刻的介绍，因而学生学习这部分内容时感到十分困难，本文针对这一问题进行讨论。
1 二叉树的遍历概念
二叉树的遍历是指按照一定的规则访问二叉树各个接结点，使每个结点都访问且只能被访问一次的过程。二叉树遍历的实质是将非线性结构的数据线性化的过程，根据访问的规则（先左后右的顺序）不同，可以分为四种先序遍历、中序遍历、后序遍历及层次遍历。
先序遍历（Preorder Traversal亦称(先根遍历)）二叉树的操作定义为：若二叉树为空，则退出，否则，①访问根结点；②先序遍历左子树；③先序遍历右子树。
中序遍历（Inorder Traversal亦称(中根遍历)）二叉树的操作定义为：若二叉树为空，则退出，否则，①中序遍历左子树；②访问根结点；③中序遍历右子树。
后序遍历（Postorder Traversal亦称(后根遍历)）二叉树的操作定义为：若二叉树为空，则退出，否则，①后序遍历左子树；②后序遍历右子树；③访问根结点。
层次遍历（Level Traversal）二叉树的操作定义为：若二叉树为空，则退出，否则，按照树的结构，从根开始自上而下，自左而右进行访问每一个结点，从而实现对每个结点的访问。
由这四种操作可以得到同一课树的四个不同的遍历序列，下面我们将进一步研究四种遍历有什么联系？
2 四种遍历序列的联系
性质一：已知中序遍历序列和后序遍历序列能唯一地确定一棵二叉树。
证明：①如果后序遍历序列和中序遍历序列都是空，则该二叉树是空树，而空二叉树是唯一的；
②如果后序遍历序列和中序遍历序列中都只有一个结点，那么该二叉树是只有一个结点二叉树，而只有一个结点的二叉树也是唯一的;
③其它情况，设小于n(n≥2)）个结点的二叉树可由后序遍历序列和中序遍历序列唯一确定。 则对于有n个结点的二叉树，后序遍历序列中的最后一个结点必然是该二叉树的根结点.然后在中序遍历序列中找到根结点，故根结点可以唯一确定，在中序遍历序列中根结点后面的结点序列就是根结点右子树的中序遍历序列，在后序遍历序列中根结点前面的属于中序遍历序列中根结点后面的那些结点组成的序列就是根结点右子树的后序遍历序列。 因为根结点的右子树至少比原二叉树少一个结点，所以根据归纳假设可知根结点的右子树是唯一的；原中序序列中根结点前面的结点序列就是根结点左子树的中序序列，原后序序列中去掉右子树后序序列后剩下的结点序列就是根结点左子树的后序序列，根结点的左子树至少比原二叉树少一个结点，根据归纳假设可知根结点的左子树也是唯一的。
所以对于有 n 个结点的二叉树也可由后序遍历序列和中序遍历序列唯一确定。
由①、②、③可知对于任意个结点的二叉树都可由后遍历序列和中序遍历序列唯一确定。
性质二：已知先序遍历序列和中序遍历序列，可以唯一确定一棵二叉树。
证明原理同1，下面我们用一个例子来说明此性质。
如：先序遍历序列 ABCDEFG 中序序列CBEDAFG,问是否能确定一棵二叉树?
分析：由先序遍历序列ABCDEFG可知A为根结点，由中序序列CBEDAFG可知CBED和FG分别为该二叉树的左子树和右子树结点。
性质三：已知先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。
下面我们用一个反例来证明，已知：先序序列ABCK 后序序列BKCA，问是否能确定一棵二叉树。
分析：由先序遍历和后序遍历只能确定根的结点A，而无法确定A的左子树和右子树，故，先序遍历序列和后序遍历序列不能唯一确定一棵二叉树。
性质四：已知一棵二叉树的层次遍历序列和中序遍历序列能唯一确定一棵二叉树。
证明： ①当n=0时，一棵空二叉树的中序序列和层次序列都为空，可以唯一确定该二叉树。命题成立。
②假设当0≤n≤k时命题成立(k≥0),下面证明当n=k+1时命题也成立。
设一棵二叉树的中序序列和层次序列分别为b1，b2，b3…bk+1，和d1，d2…dk+1，根据二叉树的层次序列的定义，d1为根结点，d1在b1，b2，b3……bk+1中出现一次，设bi=d1(1≤i≤k+1)。根据二叉树的中序序列的定义，i=1,则左子树的中序序列为空，左子树的层次序列也为空，若2≤I;≤k+1, 则 b1，b2，b3……bi-1为左子树的中序序列，将b1，b2，b3……bi-1中的所有结点按其在d1，d2……dk+1中相对次序排列成dp1，dp2……dpi-1 (2＝p1
由①②可知已知一棵二叉树的层次遍历序列和中序遍历序列能唯一确定一棵二叉树。
推论1：已知一棵二叉树的层次遍历序列和先序遍历序列不能唯一确定一棵二叉树。
推论2：已知一棵二叉树的层次遍历序列和后序遍历序列不能唯一确定一棵二叉树。
几个重要结论：
①前序序列和中序序列相同的二叉树是：空二叉树或没有左子树的二叉树(右单支树)。
②中序序列和后序序列相同的二叉树是：空二叉树或没有右子树的二叉树(左单支树)。
③前序序列和后序序列相同的二叉树是：空二叉树或只有根结点的二叉树。
④前序、中序、后序序列均相同的二叉树：空树或只有根结点的二叉树。
3 利用二叉树的四种遍历序列的联系来解决问题
1) 已知一个非空二叉树，其按中根和后根遍历的结果分别为中根：CGBAHEDJFI，后根：GBCHEJIFDA.试将这样的二叉树构造出来，若已知先根和后根的遍历根，能否构造出这样的二叉树?为什么? [哈工大研究生试题]
解：有二叉树的后根遍历定义可知，后根遍历序列的最后一个结点为根结点，而此根结点可将对应的中根序列分割为左子树和右子树两部分，然后继续对每一子树重复上述的划分过程直到树叶结点为止，最终可将完整的二叉树构造出来。此二叉树的构造过程如下图：
如果已知先根和下根的遍历结果，由性质3可知，由这两种遍历序列仅可知道根结点的信息无法区别左右子树，所以也就无法确定一棵二叉树。
2) 假设一棵二叉树的层次序列为ABCDEFGHIJ，中序序列为DBGEHJACIF。请推出这样二叉树。（武汉大学研究生试题）
解：层次序列的第一个结点为根结点，而此根结点将对应的中序序列分割为左子树和右子树两部分，然后继续从左至右扫描层次序列的第二个结点即为子树的根，再将其对应的中序子树序列分割为左右子树两部分，反复上述操作可构造出对应的二叉树。此二叉树的构造过程如下图：
利用上述方法解题相似题目还有：
1) 证明，由一棵二叉树的前序序列和中序序列可唯一确定这棵二叉树。设一棵二叉树的前序序列为ABDGECFH，中序序列为：DGBEAFHC 。试画出该二叉树。（浙江大学研究生试题）
2) 一棵树的先序和后序序列分别如下，画出该树。先序序列：ABCDEFGHIJKLM ，后序序列：CDBEFGJKLMIHA（华南理工大学研究生试题）
3) 二叉树已知其中序扫描序列和后序扫描序列如何确定这一棵二叉树，并举例说明。（山东大学研究生试题）
4) 试证明：仅仅已知一棵二叉树的后序遍历序列和先序遍历序列，不能唯一地确定这棵二叉树。（大连海事大学研究生试题）
5) 由二叉树的前序遍历和后序遍历结果能否唯一确定一棵二叉树？解释你的论断。（西安电子科技大学研究生试题）
4 结束语
二叉树的遍历在数据结构中有着重要作用，像求二叉树的深度，二叉树的左右子树，统计叶子个数及波兰式问题，都可以从二叉树的遍历去着手分析，所以说遍历二叉树的问题是非常重要，对我们研究有关问题起着很大帮助。
参考文献：
[1] 齐景嘉.数据结构(含实训)[M].南京:东南大学出版社,2006.
[2] 王昆仑,李红.数据结构[M].北京:中国铁道出版社,2007.
[3] 康牧,陈向奎.怎样由遍历序定二叉树[J].洛阳师范学院学报,2003,22(2):56-58.
[4] 唐自立.基于遍历序列的唯一确定树或二叉树的方法[J].小型微型计算机系统,2001,22(8):985-988.