"数据结构第6章复习重点"
本章主要介绍了树与森林、二叉树的定义、性质、操作和相关算法的实现。特别是二叉树的遍历算法，它们与许多以此为基础的递归算法都必须认真学习。
一、树与森林的定义
树是由结点组成的集合，每个结点都有零个或多个子女结点。森林是零个或多个树的集合。树可以用数组或链表存储，链表存储需要结点的指针来表示结点之间的关系。
二、二叉树的定义
二叉树是一种特殊的树，每个结点最多有两个子女结点，即左子女和右子女。二叉树可以用数组或链表存储，数组存储需要按层次顺序存储结点，链表存储需要结点的指针来表示结点之间的关系。
三、二叉树的遍历算法
二叉树的遍历算法有前序遍历、中序遍历和后序遍历三种。前序遍历是先访问根结点，然后访问左子树和右子树。中序遍历是先访问左子树，然后访问根结点，最后访问右子树。后序遍历是先访问左子树和右子树，然后访问根结点。
四、线索化二叉树
线索化二叉树是指在二叉树中添加了前驱和后继线索的二叉树。线索化二叉树可以简化二叉树的遍历算法。
五、堆的定义
堆是一种特殊的二叉树，满足堆的性质是每个结点的值都大于或等于其子女结点的值。堆可以用来实现优先级队列。
六、霍夫曼树
霍夫曼树是一种特殊的二叉树，要求在外结点上带有权值，在构造霍夫曼树时必须注意一个新结点的左子女上所带的权值小于右子女上所带的权值。霍夫曼树可以用来实现霍夫曼编码。
七、树与森林的转换
树与森林可以相互转换，树可以转换为森林，森林也可以转换为树。
八、树的遍历方法
树的遍历方法有前序遍历、中序遍历、后序遍历和层次遍历四种。前序遍历是先访问根结点，然后访问左子树和右子树。中序遍历是先访问左子树，然后访问根结点，最后访问右子树。后序遍历是先访问左子树和右子树，然后访问根结点。层次遍历是按层次顺序访问结点。
九、树的应用
树有广泛的应用，如二叉搜索树、堆、霍夫曼树等。树可以用来实现优先级队列、排序算法等。
本章主要介绍了树与森林、二叉树的定义、性质、操作和相关算法的实现。掌握这些知识点对于数据结构的学习非常重要。
