您所在的位置：四川中公考研 > 备考资料 > 考研专硕 > 2020计算机职业考研数据结构知识点：二叉树

2020计算机职业考研数据结构知识点：二叉树

发布日期：2019-06-12 20:38:57 来源：四川中公考研

2020考研择校择职业指导群

点击关注“四川中公考研”新浪微博，与博主互动获取考研上名校技巧

点击关注“四川中公考研”微信公众号，第一时间获取新考研资讯

职业课协议班、周末面授班、半年集训、暑期集训营

本文是四川中公考研网小编整理的关于“2020计算机职业考研数据结构知识点：二叉树"的相关资讯信息，供大家参考。
　 1. 二叉树的概念、性质
　　(1)掌握树和二叉树的定义。
　　(2)理解二叉树与普通双分支树的区别。二叉树是一种特殊的树，这种特殊不仅仅在于其分支多为2以及其它特征，一个重要的特殊之处是在于：二叉树是有序的。即二叉树的左右孩子是不可交换的，如果交换了就成了另外一棵二叉树，这样交换之后的二叉树与原二叉树是不相同的两棵二叉树。但是，对于普通的双分支树而言，不具有这种性质。
　　(3)满二叉树和完二叉树的概念。
　　(4)重点掌握二叉树的五个性质及证明方法，并把这种方法推广到K叉树。普通二叉树的五个性质：第i层的多结点数，深度为k的二叉树的多结点数，n0=n2+1的性质，n个结点的完二叉树的深度，顺序存储二叉树时孩子结点与父结点之间的换算关系。
　　2. 掌握二叉树的顺序存储结构和二叉链表、三叉链表存储结构的各自优缺点及适用场合，以及二叉树的顺序存储结构和二叉链表存储结构的相互转换的算法。
　　3. 熟练掌握二叉树的先序，中序和后序遍历算法以及按层次遍历二叉树的先序、中序和后序三种遍历算法，划分的依据是视其每个算法中对根结点数据的访问顺序而定。不仅要熟练掌握这三种遍历的递归算法，理解其执行的实际步骤，并且应该熟练掌握三种遍历的非递归算法。
　　4.遍历是基础，重点掌握在三种基本遍历算法的基础上实现二叉树的其它算法。如求二叉树叶子结点总数，求二叉树结点总数，求度为1或度为2的结点总数，复制二叉树，建立二叉树，交换左右子树，查找值为n的某个指定结点，删除值为n的某个指定结点等等。
　　5. 线索二叉树的引出，是为避免如二叉树遍历时的递归求解。递归虽然形式上比较好理解，但是消耗了大量的内存资源，如果递归层次一多，势必带来资源耗尽的危险。二叉树线索化的实质是建立结点在相应序列中与其前驱和后继之间的直接联系。对于线索二叉树，应该掌握：线索化的实质，三种线索化的算法，线索化后二叉树的遍历算法，基本线索二叉树的其它算法问题(如：查找某一类线索二叉树中指定结点的前驱或后继结点)。
　　6. 二叉排序树的中序遍历结果是一个递增的有序序列。二叉排序树的形态取决于元素的输入顺序，二叉排序树在差情况下形成单支树。熟练掌握其建立、查找、插入和删除算法，以及判断某棵二叉树是否二叉排序树这一问题的递归与非递归算法。
　　7. 平衡二叉树是二叉排序树的优化，平衡二叉树对左右子树的深度有了限定：深度之差的绝对值不得大于1。掌握平衡二叉树的四种调整算法。
　　8. 树与森林的遍历，只有两种遍历算法：先根与后根(对于森林而言称作：先序与中序遍历)。二者的先根与后根遍历与二叉树中的遍历算法是有对应关系的：先根遍历对应二叉树的先序遍历，而后根遍历对应二叉树的中序遍历。二叉树使用二叉链表分别存放它的左右孩子，树利用二叉链表存储孩子及兄弟(称孩子兄弟链表)，而森林也是利用二叉链表存储孩子及兄弟。掌握树、森林和二叉树间的相互转换。
　　9. 简单掌握等价类的生成算法。
　　10.哈夫曼树为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是小的，一般来说，哈夫曼树的形态不是的。理解哈夫曼编码的基本原理，掌握基于哈夫曼树生成哈夫曼编码的方法。
更多考研常识相关内容尽在四川中公考研专硕栏目，中公考研为广大学子推出乐学面授课、VIP一对一等系列备考课程，针对每一个科目要点进行深入的指导分析，欢迎各位考生了解咨询。同时，中公考研一直为大家推出考研直播课堂，足不出户就可以边听课边学习，为大家的考研梦想助力！

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

【责任编辑：白红梅】

上一篇： 2020计算机职业考研数据结构知识点：栈、队列和数组

下一篇： 2020计算机职业考研数据结构知识点：图

预约报名流程

考研指导图书

热点推荐

中公考研课堂

公共课
|专业课

课程系列	班次名称	价格	免费试听
考研政治网络课堂	2022考研政治+英语提升课程	咨询	免费试听
考研政治网络课堂	考研政治主观题答题技巧班	咨询	免费试听
考研英语网络课堂	2022考研政英数提升课程	咨询	免费试听
考研英语网络课堂	2022考研英语备考指导课	咨询	免费试听
考研数学网络课堂	2022考研数学备考指导课	咨询	免费试听
	2022考研数学（二）	咨询	免费试听
	2022考研数学（三）	咨询	免费试听
22专业课精品班	2022考研英语核心词汇精讲	咨询	免费试听
	9天突破英语核心1000词	咨询	免费试听
	2022考研管综备考指导课	咨询	免费试听

课程系列	班次名称	价格	免费试听
经济学精品班	2021考研经济学	咨询	免费试听
教育学精品班	经济学（初级）考研入门课	咨询	免费试听
教育学精品班	经济学（中级）考研入门课	咨询	免费试听
法学精品班	法律硕士（非法学）考研入门课	咨询	免费试听
法学精品班	2022考研法律硕士	咨询	免费试听
管理学精品班	管理学考研入门课	咨询	免费试听
管理学精品班	考研管理学全科精讲	咨询	免费试听