一、树（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 个
• 同样节点数量的二叉树，完全二叉树的高度最小