四、 树与二叉树

1. 树的基本概念

1. 树的定义
2. 基本术语
3. 树的性质

2. 二叉树的概念

1. 二叉树的定义及其主要特性

1. 二叉树的定义
2. 几个特殊的二叉树
3. 二叉树的性质

2. 二叉树的存储结构

1. 顺序存储结构
2. 链式存储结构

3. 二叉树的遍历和线索二叉树

1. 二叉树的遍历

1. 先序遍历
2. 中序遍历
3. 后序遍历
4. 递归算法和非递归算法的转换
5. 层次遍历
6. 由遍历序列构造二叉树
   a) 由二叉树的先序序列和中序序列可以唯一地确定一棵二叉树；
   b) 由二叉树的后序序列和中序序列也可以唯一确定一棵二叉树；
   c) 由二叉树的层次序列和中序序列也可以唯一地确定一棵二叉树；
   d) 先序序列和后序序列，无法唯一确定一棵二叉树 。

2. 线索二叉树

1. 线索二叉树的基本概念
2. 线索二叉树的构造
3. 线索二叉树的遍历

4. 树、森林

1. 树的存储结构

1. 双亲表示法
2. 孩子表示法
3. 孩子兄弟表示法

2. 树、森林与二叉树的转换

1. 树转换为二叉树
2. 森林转换为二叉树
3. 二叉树转换为树、森林

3. 树和森林的遍历

1. 树的遍历
    先根遍历。相当于二叉树的先序遍历。
    后根遍历。相应于二叉树的中序遍历。
2. 森林的遍历
    先序遍历森林
    中序遍历森林
3. 树和森林的遍历与二叉树遍历的对应关系

树 森林 二叉树
先根遍历 先序遍历 先序遍历
后根遍历 中序遍历 中序遍历

4. 树的应用——并查集

并查集是一种简单的集合表示，它支持一下3个操作：

1. Union(S, Root1, Root2): 把集合S中的子集合Root2并入子集合Root1。要求Root1和Root2互不相交，否则不执行合并。
2. Find(S,x):查找集合S中单元素x所在的子集合，并返回该子集合的名字。
3. Initial(S):将集合S中的每个元素都初始化为只有一个单元素的子集合。

5. 树与二叉树的应用

1. 二叉排序树

1. 二叉排序树的定义
2. 二叉排序树的查找
3. 二叉排序树的插入
4. 二叉排序树的构造
5. 二叉排序树的删除
6. 二叉排序树的查找效率分析

2. 平衡二叉树

1. 平衡二叉树的定义
为避免树的高度增长过快，降低二叉排序树的性能，我们规定在插入和删除二叉树结点时，要保证任意结点的左、右子树高度差的绝对值不超过1，这样的二叉树称为平衡二叉树，简称平衡树（AVL）。
2. 平衡二叉树的插入
二叉排序树保证平衡的基本思想如下：每当在二叉排序树栈中插入（删除）一个结点时，首先检查其插入路径上的结点是否因为此次操作而导致了不平衡。若导致了不平衡，则先找到插入路径上离插入结点最近的平衡因子的绝对值大于1的结点A，再对以A为根的子树，在保持二叉排序树特性的前提下，调整各结点的位置关系，使之重新达到平衡。
注意：每次调整的对象都是最小不平衡子树，即以插入路径上离插入结点最近的平衡因子绝对值大于1的结点作为根的子树。

平衡二叉树的插入过程的前半部分与二叉排序树相同，但在新结点插入后，若造成查找路径上的某个结点不再平衡，则需要做出相应调整。一般可将失去平衡后进行调整的规律归纳为下列4中情况：
 LL平衡旋转（右单旋转）。
 RR平衡旋转（左单旋转）。
 LR平衡旋转（先左后右双旋转）。
 RL平衡旋转（先右后左双旋转）。
3. 平衡二叉树的查找
 若所有非叶结点的平衡因子均为1，即平衡二叉树满足平衡的最少结点情况。对于高度为N、左右子树高度分别为N-1、N-2、所有非叶结点的平衡因子均为1的平衡二叉树，总结点数的公式为：CN = CN-1 + CN-2 + 1, C1 = 1, C2 = 2 , C3 = 2 + 1 +1 = 4.
 查找过程中，与给定值进行比较的关键字个数不超过树的深度。可以证明，含有n个结点的平衡二叉树的最大深度为O(log2n)，因此平衡二叉树的平均查找长度为O(log2n) 。

3. 哈夫曼树和哈夫曼编码

1. 哈夫曼树的定义
2. 哈夫曼树的构造
    将n个结点分别作为n棵仅含有一个结点的二叉树，构成森林F；
    构造一个新结点，从F中选取两棵根结点权值最小的树作为新结点的左、右子树，并且新结点的权值置为左、右子树上根结点权值之和。
    从F中删除刚才选出的两棵树，同时将新得到的树加入F
3. 哈夫曼编码
   前缀编码：没有一个编码是另一个编码的前缀。