一、树的基本概念
1. 定义
树是 n（n >= 0）个结点的有限集合。
- n = 0 时：称为空树。
- n > 0 时，满足：
- 有且仅有一个根结点（root）
- 其余结点可分为 m（m>0）个互不相交的有限集合，每个集合本身也是一棵树，称为根的子树
2. 结点的分类
- 结点：树中的一个独立单元，包含一个数据元素，及若干指向其子树的分支。
- 度（结点的）：子树的个数。
- 树的度：结点中最大的度。
- 叶子节点（终端节点）：度为 0 的节点。
- 分支节点（内部节点或非终端节点）：度不为 0。
3. 节点之间的关系
- 双亲和孩子：结点的子树称为该结点的孩子，该结点也称为孩子的双亲。
- 兄弟：同一个双亲的孩子之间互称兄弟；双亲在同一层的孩子称为堂兄弟。
- 祖先和子孙：结点的祖先是从根到该结点所经分支上的所有结点，以某结点为根的子树中的任一结点称为该结点的子孙。
4. 度量树
- 树的深度：树中的结点的最大层次。
- 树的高度：两者之间数值相同。
5. 有序树和无序树
如果将树中的结点的各子树看成从左至右是有次序的，不能互换的，则称该树为有序的，否则称为无序树。
6. 森林
森林是 m ( m >= 0 ) 棵互不相交的树的集合。
7. 线性结构和树结构的区别
| 线性结构 | 树结构 |
|---|---|
| 第一个数据元素：无前驱 | 根结点：无双亲，唯一 |
| 最后一个数据元素：无后继 | 叶结点：无孩子，可以多个 |
| 中间元素：一个前驱，一个后继 | 中间结点：一个双亲多个孩子 |
二、树的存储结构
1. 顺序存储
适用于完全二叉树等结构规则的树，常用数组实现。
2. 链式存储
通用方式：每个节点包含数据域和指向子节点的指针域。
三、二叉树
1. 定义
是 n（n≥0）个结点的有限集合，或为空树（n=0）；或由一个根结点和两棵互不相交的子树组成，分别称为左子树和右子树，且二者有严格顺序。
2. 特点
- 每个结点最多有两个子树，所有二叉树中不存在度大于 2 的结点；
- 左、右子树有顺序，不可互换；
- 即使某结点仅有一个子树，也必须明确是左子树还是右子树。
3. 二叉树的五种基本形态
- 空二叉树
- 只有一个根结点
- 根结点只有左子树
- 根结点只有右子树
- 根结点既有左子树又有右子树
4. 特殊二叉树
- 斜树：所有的结点都只有左子树的二叉树叫左斜二叉树，所有结点都只有右子树的二叉树叫右斜树，这两种情况统称斜树。
- 满二叉树：在一棵二叉树中，如果所有的分支结点都存在左子树和右子树，并且所有的叶子都在同一层，这样的二叉树称为满二叉树。（深度为 k 且结点数为 (2^k) - 1 的二叉树，在同等深度的二叉树中，满二叉树的结点个数最多，叶子数最多）
- 完全二叉树：对 n 个结点按层序从 1 到 n 编号，若每个结点的位置与相同深度的满二叉树中编号相同的结点位置一致，则为完全二叉树。
- 完全二叉树的特点：除最后一层外，其它层全满，最后一层的结点靠左排列
- 满二叉树一定是完全二叉树，完全二叉树不一定是满二叉树
- 按层序编号就是设想每一个结点都有左右子树，都编号，如下图，就是 5 没有左子树，但是还是会给他的左子树编 10，尽管他为空，右子树编 11
- 叶子结点只能出现在最下两层
- 最下层的叶子一定集中在左边连续的位置
- 倒数第二层若有叶子结点，一定在右边连续的位置
- 如果结点度为 1，则该结点只有左孩子
- 同样结点数的二叉树，完全二叉树的深度最小
5. 二叉树的性质
- 在二叉树的第 i 层最多有 2^(i-1) 个结点（i>=1）
- 深度为 k 的二叉树最多有 (2^k)-1 个结点
- 对于任何一棵二叉树，如果其终端结点数为 m，度为 2 的结点数为 n，则 m = n + 1
- 具有 n 个结点的完全二叉树的深度为 ⌊log₂n⌋+1（对数是以 2 为底，⌊x⌋表示不大于 x 的最大整数）
- 如果对一棵有 n 个结点的完全二叉树（其深度为 ⌊log₂n⌋+1）的结点按层序编号（从第 1 层到第 ⌊log₂n⌋+1 层，每层从左到右），对任一结点 i（1≤i≤n）有:
- 如果 i = 1，则结点 i 是二叉树的根，无双亲；
- 如果 i > 1，则其双亲是结点 ⌊i / 2⌋
- 如果 2i > n，则结点 i 无左孩子（结点 i 为叶子结点）；否则其左孩子是结点 2i
- 如果 2i+1>n，则结点 i 无右孩子；否则其右孩子是结点 2i+1。
四、二叉树的遍历
从根结点出发，按照某种次序依次访问二叉树中的所有结点，使得每个结点被访问一次且仅被访问一次。
1. 前序遍历
规则：若二叉树为空，则空操作返回，否则先访问根结点，然后前序遍历左子树，再前序遍历右子树。如下图，遍历的顺序为 ABDGHCEIF。
2. 中序遍历
规则：若二叉树为空，则空操作返回，否则从根结点开始（注意并不是先访问根结点），中序遍历根结点的左子树，然后访问根结点，最后中序遍历右子树。如下图，遍历的顺序为 GDHBAEICF。
3. 后序遍历
规则：若二叉树为空，则空操作返回，否则先后序遍历左子树，再后序遍历右子树，最后访问根结点。
4. 层序遍历
规则：从上到下、从左到右依次访问每一层的结点。
