2021计算机考研知识点：二叉树遍历序列的应用
时间：2020-02-28 来源：文都网校 浏览：2021考研专业课复习需要注重基础，计算机是近年来的热门考研专业，相信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考研专业课复
- 2021计算机考研
- 文都网校计算机考研
- 责任编辑：qyj
