2021计算机考研复习：二叉树遍历序列的应用
文都考研网整理
中
在考研复习的过程中，每天要坐十几个小时学习。宅在家的你，要好好复习哦。或许很多同学还没有购买教材，文都考研小编带大家一起学习。今天我们来看一下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计算机考研复习资料，持续更新中。没有教材？无心看书？那就看视频吧。点击下方相关推荐，文都网校为大家提供了课程。
相关推荐