计算机#2021考研究生计算机复习备考#二叉树遍历序列的应用

类目：三人行考研网>计算机>正文

时间：2020-05-2913:40:08

相信很多备战计算机考研考生在做树和二叉树这章题的过程中
，应该会遇到过以下类型的题

设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC ，要求：画出这棵二叉树
。

这种类型的题通常会给我们二叉树的两个遍历序列
，一般是先序遍历序列和中序遍历序列，或者是后序遍历序列和中序遍历序列。可能很多同学遇到这种题会比较懵 ，直接选择通过各种试探来构造这棵二叉树 。然后
，做这种题是有规律可循的，今天​就跟随三人行考研网计算机老师一起来讨论这类题的解题思路
。

首先 ，我们知道
，先序遍历序列是根左右的形式即DLR形式，对于上面的例题而言 ，先序序列中的第一个结点A就是根结点；中序遍历序列是左根右的形式即LDR形式
，所以当我们由先序序列确定出A是根结点之后，A把中序序列分成两个子序列 ，A左面的序列就是根结点A左子树上的结点集合，A右面的序列就是根结点A右子树上的结点集合
，对于左右两子树的集合，我们又可以通过先序序列中先出现的结点确定哪个结点是子树的根 ，比如左子树结点集合为B
，F，D组成 ，而在先序序列中B先于D和F出现
，说明B是根A的左子树的根，C是根A的右子树的根 ，以此类推
，得到由先序序列：ABDFCEGH以及中序序列：BFDAGEHC确定的唯一一棵二叉树，如下图所示。简言之 ，由先序序列确定哪些结点是根或子树的根
，由中序序列确定哪些结点是左子树结点集合以及右子树结点集合 。同理，由后序序列和中序序列也可唯一确定一棵二叉树
。

以上就是三人行考研网小编整理的“2021考研计算机复习备考：二叉树遍历序列的应用
”相关内容 ，希望对大家有所帮助，预祝大家能考上理想的院校。更多计算机考研信息尽在三人行考研网计算机频道！

相关推荐：

2021考研计算机复习备考：依据先序后序生成二叉树

2021考研：计算机考研难度排行榜

2021考研：计算机专业考研方向有哪些？