您所在的位置：四川中公考研 > 备考资料 > 考研专硕 > 考研计算机|数据结构-遍历二叉树的应用

考研计算机|数据结构-遍历二叉树的应用

发布日期：2021-07-31 22:31:51 来源：四川中公考研

2022考研智能择校择专业匹配系统入口 2022考研全年备考资料包免费下载入口

一、由遍历序列构造二叉树

考研中最常考的知识点有：前中得后，中后得前。

【注意】前序和中序是无法得到唯一的中序的。

1.由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树。

在先序遍历序列中，第一个结点一定是二叉树的根结点，而在中序遍历中，根结点必然将中序序列分割成两个子序列，前一个子序列就是根结点的左子树的中序序列，后一个子序列是根结点的右子树的中序序列。根据这两个子序列，在先序序列中找到对应的左子序列和右子序列。在先序序列中，左子序列的第一个结点是左子树的根结点，右子序列的第一个结点是右子树的根结点。如此递归地进行下去，便能唯一地确定这棵二叉树。

2.由二叉树的后序序列和中序序列也可以唯一地确定一棵二叉树。

后序序列的最后一个结点就如同先序序列的第一个结点，可以将中序序列分割成两个子序列，然后采用类似的方法递归地进行划分，就可以得到一棵二叉树。

3.由二叉树的层序序列和中序序列也可以唯一地确定一棵二叉树。

二、试题实战

1. 设一棵二叉树的先序序列：ABDFCEGH，中序序列：BFDAGEHC，要求：画出这棵二叉树。

【答案解析】

1.根据先序遍历序列确定二叉树的根以及子树的根，根据中序遍历序列确定左右子树上的结点，二叉树如下：

2022考研计算机

考研实用工具推荐
1、2022考研院校专业匹配查询系统
2、近4年全国各在招院校专业复试分数线查询
3、历年调剂信息查询
4、历年各院校专业目录查询
5、历年各院校报录比查询
6、历年各院校参考书目录查询

免责声明：本站所提供的内容均来源于网友提供或网络搜集，由本站编辑整理，仅供个人研究、交流学习使用，不涉及商业盈利目的。如涉及版权问题，请联系本站管理员予以更改或删除。

【责任编辑：樊孝阳】

上一篇：应用心理不考实验统计和测量院校之福建医科大学健康学院

下一篇：考研计算机：操作系统-基于时间片的轮转调度算法

10秒智能择校

查看历年试题

热点推荐

备考福利站

公共课
|专业课

课程系列	班次名称	价格	免费开通
考研政治网络课堂	2026政治考研备考指导课	39	免费开通
考研政治网络课堂	考研政治五年试题精讲	199	免费开通
考研英语网络课堂	2026考研英语备考指导课	39	免费开通
考研英语网络课堂	考研英语（一、二）五年试题精讲	199	免费开通
考研数学网络课堂	2026考研数学备考指导课	39	免费开通
	考研数学五年试题精讲	199	免费开通
	考研数学常用公式整理	39	免费开通
23专业课精品课	311教育学考研入门课	11	免费开通
	333教育综合考研入门课	11	免费开通
	法律硕士（非法学）考研入门课	11	更多课程

课程系列	班次名称	价格	免费开通
经济学精品班	金融学考研入门课	咨询	免费开通
教育学精品班	经济学（初级）考研入门课	19	免费开通
教育学精品班	经济学（中级）考研入门课	19	免费开通
法学精品班	法律硕士（非法学）考研入门课	19	免费开通
法学精品班	13大热门专业课备考抢学包	19	免费开通
管理学精品班	管理学考研入门课	19	免费开通
管理学精品班	社会工作考研入门课	19	免费开通