爱启航考研 计算机
启航官网 > 计算机 > 计算机备考 > 经验指导 > 文章
分享至

2021计算机考研科目章节重点:二叉树遍历序列

关键字: 计算机考研科目 时间:2019.12.09

下面是爱启航考研计算机老师总结的“2021计算机考研科目章节重点:二叉树遍历序列”的内容。

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

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

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

【考研党必备学习资料包】:考研真题+免费择校择专业+免费考研复习规划,更有考研课程优惠券等你来加购~名额有限立即领取【领取链接】

【启航教育考研辅导课程推荐】:面授课集训营(冲刺密训十一特训),专业课一对一辅导考研网课全程班包含公共课以及专业课,这些课程中都会配有内部讲义以及辅导书和资料,同时会有教研教辅双师模式对大家进行教学以及督学,并配有24小时答疑和模拟测试等,具体详情可直接咨询在线客服老师。


来源:启航考研 责任编辑:yulaoshi
热门活动