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