4.1 考点归纳与考点分析

4.1 考点归纳与考点分析

　　二叉树是数据结构的一个考查重点，主要考查二叉树的性质和基本应用。在学习过程中，我们要注意把握各种二叉树的基本性质、应用场合。本章中的考点情况如表4-1所示。

表4-1 树与二叉树的考点情况

　　（1）树的概念、表示方法与性质；二叉树的概念和性质，包括特殊的二叉树（如满二叉树、完全二叉树等）。理解并熟练运用树的基本术语、性质来求解各种相关问题；二叉树问题中主要是和数量相关的计算题，既需要运用基本性质进行推导，也要借助图形等方式直观表示。
　　（2）二叉树的顺序存储结构和链式存储结构。理解两种结构的相同点和不同点，彼此的优缺点，还需要有意识地建立起二叉树形态和其逻辑结构的对应关系，这是求解二叉树算法问题的关键。这部分存在一些定量关系式，是历年考试的常考知识点，包括：完全二叉树中结点编号、叶结点和非叶结点的判断等。
　　（3）二叉树的三种基本遍历方法（前序遍历、中序遍历、后序遍历）、由二叉树的遍历序列恢复二叉树。遍历是求解各种二叉树问题的基础，需要掌握递归和非递归两种遍历方法。在此基础上还要掌握算法中所蕴涵的一些思想，从而提高算法的应用深度。遍历算法框架中的visit函数不仅仅是访问结点，在具体应用中需要根据情况对其进行扩充，从而实现更广泛的应用。回溯法是先序遍历“状态树”的过程，属于更高级的遍历法运用，是历年考试的难点，但又是拉开分值的关键，需要深入理解。
　　（4）二叉树线索化过程，能够建立一棵线索二叉树，并能求出其在各种形式（先序、中序、后序）下的前驱和后继。其中，中序线索二叉树用途最广，是出题的重点。
　　（5）树和森林的遍历，树、森林与二叉树的关系。树和森林的孩子兄弟表示法与其对应的二叉树等价，要熟练掌握树、森林与二叉树的转换，理解树、森林的遍历与其对应二叉树遍历之间的关系。与二叉树相同，树和森林也是递归定义的，所以二叉树算法中的某些策略，在树和森林中也适用。
　　（6）哈夫曼树的定义与构造方法。要能够根据权值，构建对应的哈夫曼树；能够根据不同的实际情况，编制出适用的哈夫曼编码。