2015计算机考研制胜攻略讲解 二叉树_跨考网
二叉树是计算机考研数据结构中的重点内容,在这两年的专业考试中也将二叉树作为重点内容来考查。二叉树这部分内容要求大家掌握二叉树的定义、性质、存储结构、遍历、线索化、森林和二叉树的转换等内容。算法的重点是二叉树的遍历及其应用,这也是二叉树这部分的重点和难点。遍历是二叉树各种操作的基础,可以在遍历过程中对结点进行各种操作。例如:求二叉树结点总数,建立二叉树,建立二叉树的存储结构等。二叉树的很多算法是在遍历算法基础上改造完成的,这就要求大家在复习时,熟练掌握二叉树遍历的递归和非递归算法。
下面,跨考考研编辑组介绍一下二叉树的几种遍历方法:
由二叉树的定义可知,一颗二叉树由根节点及左、右子树三个基本部分组成,因此,只要依次遍历这三部分,就可以遍历整个二叉树。
1.先序遍历
先序遍历的递归过程为:若二叉树为空,遍历结束。否则,
(1)访问根节点;
(2)先序遍历根节点的左子树;
(3)先序遍历根节点的右子树。
2.中序遍历
中序遍历的递归过程为:若二叉树为空,遍历结束。否则,
(1)中序遍历根节点的左子树;
(2)访问根节点;
(3)中序遍历根节点的右子树。
3.后序遍历
后序遍历的递归过程为:若二叉树为空,遍历结束。否则,
(1)后序遍历根节点的左子树;
(2)后序遍历根节点的右子树;
(3)访问根节点。
层次遍历
二叉树的层次遍历,是指从二叉树的第一层(根结点)开始,从上至下逐层遍历,在同一层中,则按从左到右的顺序对结点逐个访问。在进行层次遍历时,对一层结点访问完后,再按照它们的访问次序对各个结点的左孩子和右孩子顺序访问,这样一层一层进行,先遇到的结点先访问,这与队列的操作原则比较吻合。因此,在进行层次遍历时,可设置一个队列结构,遍历从二叉树的根结点开始,首先将根结点指针入队列,然后从对头取出一个元素,每取一个元素,执行下面两个操作:
(1)访问该元素所指结点;
(2)若该元素所指结点的左、右孩子结点非空,则将该元素所指结点的左孩子指针和右孩子指针顺序入队。
此过程不断进行,当队列为空时,二叉树的层次遍历结束。
这部分相关算法以及二叉树遍历的非递归算法在《计算机学科专业基础综合辅导讲义》中有详细讲解,大家如果对这部分内容还有疑问,可以查阅《计算机学科专业基础综合辅导讲义》,一定要把这些基础内容搞清楚。
下面大家来看二叉树遍历这部分在考试中常考题型
1.由二叉树的两个遍历序列的组合(先序序列和中序序列)、(中序序列和后序序列)、(层次序列和中序序列)构造该二叉树或求其他遍历序列是一种常见的题型。需要注意的是已知二叉树的先序序列和后序序列不能唯一确定该二叉树。
2.以遍历为基础的二叉树算法设计是考试的重点和难点。常见的试题有以下几类:
(1)基于二叉树遍历的递归算法
这类题目的特点是直接根据三种递归算法改写,修改访问语句来实现。例如:求二叉树的结点个数。
(2)基于二叉树层次遍历的算法
这类题目有求二叉树的高度,求二叉树最大宽度等。
(3)基于顺序存储的二叉树遍历算法
例如:求顺序存储的满二叉树中序遍历的非递归算法。
(4)其他二叉树遍历算法
例如:左、右子树交换等。
大家要重点掌握这些以遍历为基础的二叉树算法题目,这就要求大家多做练习,通过习题训练加深理解,掌握解题思路和技巧,提高解题能力。针对以上几种算法题,大家可通过计算机学科专业基础综合辅导讲义同步练习来准备相应的练习题并配有详细的解答,掌握此部分内容。
另外,现在大家开始计算机考研冲刺复习了,选择一本涵盖全面、与真题题型一致、题目难度和真题难度高度相近,并对这两年的考试试题进行了详细分析的全真模拟试题集,是此时冲刺的最佳帮手,可以帮助你查缺补漏,显著提高应试能力。
2022考研初复试已经接近尾声,考研学子全面进入2023届备考,跨考为23考研的考生准备了10大课包全程准备、全年复习备考计划、目标院校专业辅导、全真复试模拟练习和全程针对性指导;2023考研的小伙伴针也已经开始择校和复习了,跨考考研畅学5.0版本全新升级,无论你在校在家都可以更自如的完成你的考研复习,暑假集训营带来了院校专业初步选择,明确方向;考研备考全年规划,核心知识点入门;个性化制定备考方案,助你赢在起跑线,早出发一点离成功就更近一点!
考研院校专业选择和考研复习计划 | |||
2023备考学习 | 2023线上线下随时学习 | 34所自划线院校考研复试分数线汇总 | |
2022考研复试最全信息整理 | 全国各招生院校考研复试分数线汇总 | ||
2023全日制封闭训练 | 全国各招生院校考研调剂信息汇总 | ||
2023考研先知 | 考研考试科目有哪些? | 如何正确看待考研分数线? | |
不同院校相同专业如何选择更适合自己的 | 从就业说考研如何择专业? | ||
手把手教你如何选专业? | 高校研究生教育各学科门类排行榜 |
跨考考研课程
班型 | 定向班型 | 开班时间 | 高定班 | 标准班 | 课程介绍 | 咨询 |
秋季集训 | 冲刺班 | 9.10-12.20 | 168000 | 24800起 | 小班面授+专业课1对1+专业课定向辅导+协议加强课程(高定班)+专属规划答疑(高定班)+精细化答疑+复试资源(高定班)+复试课包(高定班)+复试指导(高定班)+复试班主任1v1服务(高定班)+复试面授密训(高定班)+复试1v1(高定班) | |
2023集训畅学 | 非定向(政英班/数政英班) | 每月20日 | 22800起(协议班) | 13800起 | 先行阶在线课程+基础阶在线课程+强化阶在线课程+真题阶在线课程+冲刺阶在线课程+专业课针对性一对一课程+班主任全程督学服务+全程规划体系+全程测试体系+全程精细化答疑+择校择专业能力定位体系+全年关键环节指导体系+初试加强课+初试专属服务+复试全科标准班服务 |