第5章 树和二叉树

本章学习了树和二叉树这种具有层次关系的非线性数据结构。主要内容如下：

(1) 二叉树的定义和术语，二叉树的性质，特殊的二叉树。

(2) 二叉树的存储结构，顺序存储和二叉链表，顺序存储更加适用于完全二叉树，二叉链表使用指针指向左孩子和右孩子，是二叉树常用的存储结构。

(3) 二叉树的的前序、中序、后序遍历算法。线索化二叉树。通过遍历得到二叉树结点的线性序列，实现非线性结构的线性化。线索二叉树则是在首次遍历二叉树时，利用空指针存储结点的前驱和后继结点，以加快查找结点前驱和后继的速度。

(4) 树和森林的定义，树的存储，树、森林与二叉树的转换。树的存储结构主要有三种：双亲表示法、孩子表示法和孩子兄弟表示法。通过孩子兄弟表示法可以在树和森林与二叉树之间转换。

(5) 树的应用——哈夫曼树及哈夫曼编码。只要构造了哈夫曼树，按分支情况在左路径上写代码0，在右路径上写代码1，然后从上到下叶结点相应路径上的代码序列就是该叶结点的最优前缀码，即哈夫曼编码。

本章的学习要求如下：

• 了解树和森林的概念，包括树的定义、树的术语。
• 掌握二叉树的概念、性质及二叉树的表示。
• 熟练掌握二叉树的遍历算法，并且能灵活运用遍历算法实现二叉树的其他操作。
• 掌握线索化二叉树的特性及寻找某结点的前驱和后继的方法。
• 掌握树的存储、树和森林与二叉树的转换方法。
• 掌握哈夫曼树的实现方法、构造哈夫曼编码的方法及带权路径长度的计算。

本章练习：

教材P123页第5章习题

全部选择题

应用题：（2）（3）（4）

算法设计题：（1）（6）（7）（8）

本章学习建议完成时间：本章学习建议完成时间：11月23日