1. 树

1.1 树的定义

树是 n（n >= 0）个结点的有限集合。

1.2 树的基本概念

1.3 树的性质

2. 二叉树

2.1 二叉树的定义

二叉树是每个结点最多有两个子树的树结构。

2.2 二叉树的性质

2.3 满二叉树与完全二叉树

  • 满二叉树：深度为 k 且有 2^k - 1 个结点的二叉树
  • 完全二叉树：深度为 k 的，有 n 个结点的二叉树，当且仅当其每一个结点都与深度为 k 的满二叉树中编号从 1 至 n 的结点一一对应

2.4 二叉树的遍历

遍历是按某种策略访问树中的每个结点，且仅访问一次的过程。

先序遍历

先序遍历顺序：根 -> 左 -> 右

中序遍历

中序遍历顺序：左 -> 根 -> 右

后序遍历

后序遍历顺序：左 -> 右 -> 根

层序遍历

按层次从上到下、每层从左到右依次访问结点。

2.5 二叉树的存储结构

顺序存储

链式存储（了解）

2.6 构造二叉树

  • 先序 + 中序 可以唯一确定一棵二叉树
  • 后序 + 中序 可以唯一确定一棵二叉树
  • 层序 + 中序 可以唯一确定一棵二叉树

2.7 线索二叉树

3. 平衡二叉树

二叉树中的任意一个结点的左右子树高度之差的绝对值不超过1。

4. 二叉排序树（二叉查找树）

4.1 二叉排序树定义

  • 左子树所有结点的关键字 < 根结点的关键字
  • 右子树所有结点的关键字 > 根结点的关键字
  • 左右子树也是一个二叉排序树

即：左 < 根 < 右

4.2 二叉排序树的性质

中序遍历得到的序列是有序序列。

4.3 二叉排序树的构造

5. 最优二叉树（哈夫曼树）

5.1 最优二叉树的定义

最优二叉树：是一类带权路径长度最短的树。

  • 路径：从树中一个结点到另一个结点之间的通路
  • 路径长度：路径上的分支数目

5.2 哈夫曼算法（构造最优二叉树）

最优二叉树构造规则：

  1. 从前往后找两个权值最小
  2. 小左大右
  3. 加入末尾
  4. 权值相同，从前往后
  5. 用时再调

5.3 哈夫曼编码

利用哈夫曼树构造的前缀编码，使带权路径长度最短，实现数据压缩。