题解二叉树的构造
来源:用户上传
作者:
摘要：文中介绍了两种方法求解问题：根据二叉树的先序遍历序列及中序遍历序列绘出二叉树。方法一为课本中的常见方法，即根据二叉树遍历的定义求解;方法二为作者提出的新方案，即根据二叉排序树的定义求解。
关键词：数据结构 二叉树遍历 二叉
排序树
DOI：
10.16657/j.cnki.issn1673-9132.2016.07.173
学习过数据结构的读者们都知道，在二叉树的遍历章节中，有一种比较典型的题型是：给出一棵二叉树的先序遍历序列及中序遍历序列，据此构造出这棵二叉树。这个问题一般都是根据二叉树的前序遍历和中序遍历定义及二叉树的性质求解的。笔者在学习过程中发现另一种解决方案，即利用二叉排序树的定义来求解。下面笔者将两种方案一一介绍如下。
一、利用二叉树遍历定义求解
一般书中的常见解法为：由二叉树的遍历定义得知，二叉树的前序遍历是先访问二叉树的根结点，然后遍历左子树，最后再遍历右子树，也就是根-左-右的顺序。这样，在遍历结点的前序序列中，第一个结点一定是根;而用中序遍历时，是先遍历左子树，再访问根结点，最后遍历右子树，是左-根-右的顺序，由此知道，根结点将中序遍历序列分割成两个部分：在根结点前是左子树的中序遍历序列，在根结点之后则是右子树的中序遍历序列。反之，根据左子树的中序遍历序列中结点的个数，又可将前序序列除根以外分成左子树的前序序列和右子树的前序序列两部分。依次类推，我们就得到了整棵二叉树。
如下例：
例1：已知二叉树结点的前序序列为：ABCDEFG，中序序列为：CBDAFEG，试绘出这棵二叉树。
解1：首先由前序序列得知二叉树的根为A，则由中序遍历序列得出其左子树的中序遍历序列为（CBD），右子树的中序遍历序列为（FEG）。反过来，又由前序序列得知其左子树的前序序列必为（BCD），右子树的前序序列为（EFG）。由左子树的前序序列（BCD）得出左子树的根结点为B，又由左子树的中序序列（CBD）得出以B为根的左子树的左边叶子结点为C，右边叶子结点为D。同理，可构造得出右子树。
构造过程图示如下：
[A] [B
C
D] [F
E
G] [A][B] [C][D] [F
E
G] [A][B] [C][D] [E] [E][G]
图1 图2 图3
二、利用二叉排序树的定义求解问题
二叉排序树是一种特殊的二叉树，它的每一个结点数据中都有一个关键值，并且对于每个结点，如果其左子树非空，则左子树的所有结点的关键值都小于该结点的关键值，如果其右子树非空，则右子树的所有结点的关键值都大于该结点的关键值。根据其定义可知，对二叉排序树进行中序遍历， 将得到一个按结点关键值递增有序的线性序列。若从一棵空树出发，构造一棵二叉排序树，则每次插入的新结点都是二叉排序树上新的叶子结点，我们可以假设为：从一棵空树出发，构造一棵二叉排序树，每次插入的新结点序列即为这棵二叉排序树的前序序列。由此我们得出文中问题的第二种解决方案：
1.将给出的中序序列中每个结点按升序依次赋一关键值;
2.根据第一步中所赋之值得到前序序列的关键值序列;
3.以前序序列所得到的关键字序列构造一棵二叉排序树;
4.将构造出的二叉排序中的关键字用原结点值换回。
下面我就以第二种解决方案来解上文中的例1。
解2：将题中中序序列（ CBDAFEG）中每个结点按升序依次赋一关键值，如结点 C对应关键值为1，结点 B对应关键值为2，结点 D对应的关键值为3，结点 A对应的关键值为4，结点 F对应关键值为5，结点 E对应关键值为6，结点 G对应关键值为7。
然后按前序序列（ABCDEFG）的关键字序列（4，2，1，3，6，5，7）构造一棵二叉排序树，构造过程如下：
最后将所构造成的二叉排序树中的各关键值用原结点值换回， 所得出二叉树如下所示：
[A][B] [C][D] [E] [E][G]
问题即得解。
比较这两种问题的解决方法，各有优劣。用第一种方法，不需掌握二叉排序树的相关知识，但如果此二叉树结构较复杂，结点较多时，使用此种方案，易造成思路混乱，速度较慢的后果，而使用第二种解法较简便快捷。
参考文献：
[1]严尉敏，吴伟民.数据结构（C语言版）[M].北京：清华大学出版社，1997.
[2]蔡子经，施伯乐.数据结构教程[M].上海：复旦大学出版社，1994.
[3]刘清，王琼.数据结构[M].北京：电子工业出版社，2001.
[4]赵刚，李昆.由遍历序列确定二叉树的算法[J].南昌航空大学学报：自然科学版，2010（1）.
（责编 赵建荣）
转载注明来源:https://www.xzbu.com/1/view-11445557.htm
