- 分享至
-
加入QQ群享真题
546357334
21计算机考研群 -
关注公众号得干货
启航计算机考研
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确定的唯一一棵二叉树,如下图所示。简言之,由先序序列确定哪些结点是根或子树的根,由中序序列确定哪些结点是左子树结点集合以及右子树结点集合。同理,由后序序列和中序序列也可唯一确定一棵二叉树。
【考研党必备学习资料包】:考研真题+免费择校择专业+免费考研复习规划,更有考研课程优惠券等你来加购~名额有限立即领取【领取链接】
【启航教育考研辅导课程推荐】:面授课集训营(冲刺密训,十一特训),专业课一对一辅导,考研网课全程班包含公共课以及专业课,这些课程中都会配有内部讲义以及辅导书和资料,同时会有教研教辅双师模式对大家进行教学以及督学,并配有24小时答疑和模拟测试等,具体详情可直接咨询在线客服老师。