一、树（Tree）的基本概念
- 节点、根节点、父节点、子节点、兄弟节点
- 空树：没有任何节点的树
- 一棵树可以只有 1 个节点（即只有根节点）
- 子树、左子树、右子树
---
- 节点的度（degree）：子树的个数
- 树的度：全部节点的度的最大值
- 叶子（leaf）节点：度为 0 的节点
- 非叶子节点
- 层数（level）：根节点是第 1 层，根节点的子节点是第 2 层，以此类推
- 节点的深度（depth）：从根节点开始到当前节点的唯一路径上的节点总数（节点13的深度是5；节点6的深度是3）
- 节点的高度（height）：从当前节点开始到最远叶子节点的路径上的节点总数（节点13的高度是0；节点6的高度是3）
- 树的深度：全部节点深度中的最大值
- 树的高度：全部节点高度中的最大值
- 树的深度等于树的高度
---
- 有序树：树中节点的子节点之间有顺序关系
- 无序树：树中节点的子节点之间没有顺序关系
- 森林：由 m（m >= 0）棵互不相交的树组成的集合
二、二叉树（Binary Tree）
(1) 二叉树的特点
① 每一个节点的度最大为 2（最大拥有 2 棵子树）
② 左右子树是有顺序的
③ 即使某节点只有一棵子树，也严格区分左右子树
④ 二叉树是有序树
(2) 二叉树的性质
① 非空二叉树的第 i 层最多有 2^(i-1) 个节点（i >= 1）
② 高度为 h 的二叉树上最多有 2^h - 1 个节点（h >= 1）
③ 对于任意一棵非空二叉树，如果叶子节点的个数为 n0，度为 2 的节点个数为 n2，则有：n0 = n2 + 1【对于非空二叉树，没有子树的节点的个数等于有两棵子树的节点的个数加1】
性质 ③ 的证明：
- 假设度为 1 的节点个数为 n1，那么二叉树的节点总数 n 等于 n0 + n1 + n2
- 二叉树的边数 T = n1 + n2 * 2 = n - 1 = n0 + n1 + n2 - 1【一个节点的边数等于度；除了根节点，每个节点的顶部都有一条边】
- 化简：T = n1 + n2 * 2 = n - 1 = n0 + n1 + n2 - 1
三、真二叉树（Proper Binary Tree）
特点：全部节点的度要么为0，要么为2（没有度为1的节点）
四、满二叉树（Full Binary Tree）
特点：
① 在真二叉树的基础上，所有的叶子节点都在最后一层
② 在同样高度的二叉树中，满二叉树的叶子节点数量最多，总结点数量最多
③ 满二叉树一定是真二叉树，但真二叉树不一定是满二叉树
性质：
- 若满二叉树的高度为 h（h >= 1）
-- 第 i 层的节点数量是 2^(i-1)
-- 叶子节点数量是 2^(h-1)
-- 总节点数是2^h - 1
五、完全二叉树（Complete Binary Tree）
(1) 完全二叉树特点
① 叶子节点只会出现在最后两层，且最后一层的叶子节点都靠左对齐
② 完全二叉树从根节点到倒数第二层是一棵满二叉树
③ 满二叉树一定是完全二叉树，但完全二叉树不一定是满二叉树
(2) 完全二叉树性质
- 度为 1 的节点只有左子树
- 度为 1 的节点要么是 1 个，要么是 0 个
- 同样节点数量的二叉树，完全二叉树的高度最小
