2021考研计算机复习：二叉树遍历序列的应用
  发布时间：2020/2/10 15:14:42   浏览次数：   来源：河南文都考研

2021计算机考研复习：二叉树遍历序列的应用。

设一棵二叉树的先序序列：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计算机考研复习资料，持续更新中。