2019计算机考研|数据结构重点知识:二叉树

考研网

下面，新东方在线为了助力计算机考研学子在备考上能够顺畅，特意分享了计算机考研中的数据结构重点知识:二叉树，供考生参考。
    　　2019计算机考研|数据结构重点知识:二叉树
    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.哈夫曼树为了解决特定问题引出的特殊二叉树结构，它的前提是给二叉树的每条边赋予了权值，这样形成的二叉树按权相加之和是最小的，一般来说，哈夫曼树的形态不是唯一的。理解哈夫曼编码的基本原理，掌握基于哈夫曼树生成哈夫曼编码的方法。