满二叉树#

如果二叉树中除了叶子结点，每个结点的度都为 2，则此二叉树称为满二叉树。

完全二叉树#

如果二叉树中除了最后一层，其他各层都被完全填充，并且最后一层的节点都靠左对齐，则此二叉树称为完全二叉树。 因此，完全二叉树特别适合用数组来存储，因为它的节点可以按照层序遍历的顺序存储在数组中，且没有空洞。 完全二叉树的性质：

1. 完全二叉树的深度为 $d$，则完全二叉树的节点数在 $2^{d-1}$ 到 $2^d - 1$ 之间。
2. 完全二叉树的节点数为 $n$，则完全二叉树的深度为 $\lceil \log_2(n + 1) \rceil$
3. 完全二叉树的节点数为 $n$，则完全二叉树的叶子节点数为 $\left\lceil \frac{n}{2} \right\rceil$
4. 完全二叉树的节点数为 $n$，则完全二叉树的非叶子节点数为 $\left\lfloor \frac{n}{2} \right\rfloor$

二叉搜索树#

二叉搜索树（Binary Search Tree，BST）是一种特殊的二叉树，其中每个节点的值都满足以下条件：

1. 左子树中所有节点的值都小于该节点的值。
2. 右子树中所有节点的值都大于该节点的值。

二叉搜索树的性质：

1. 二叉搜索树的中序遍历结果是一个有序的序列。
2. 二叉搜索树的平均时间复杂度为 $O(\log n)$，最坏时间复杂度为 $O(n)$，取决于树的平衡程度。

顺序存储#

顺序存储通常使用数组表示二叉树，常见于完全二叉树（如堆）。

若根节点下标从0开始，则有：

1. 下标为 i 的节点，其左孩子下标为 2i + 1
2. 下标为 i 的节点，其右孩子下标为 2i + 2
3. 下标为 i 的节点，其父节点下标为 (i - 1) >> 1

如果根节点下标从1开始，则对应公式为：左孩子 2i，右孩子 2i + 1，父节点 i // 2。

优点：

1. 按下标可 $O(1)$ 访问父子节点。
2. 实现简单，缓存局部性好。

缺点：

1. 对非完全二叉树会出现大量空位，浪费空间。
2. 插入、删除中间节点不灵活。

链式存储#

链式存储通过节点对象保存数据和左右指针，最常见定义是：val、left、right。

优点：

1. 适合任意形态的二叉树，不会因为空位浪费大量空间。
2. 插入、删除节点更灵活。

缺点：

1. 每个节点有额外指针开销。
2. 访问父节点不方便（若需要可增加 parent 指针）。

TIP

工程中若树结构经常变化，通常优先使用链式存储。

前序遍历#

访问顺序：根 -> 左 -> 右。

常见用途：

1. 复制一棵树。
2. 序列化树结构（可配合空节点标记）。

实现思路：

1. 递归：先访问根，再递归左子树和右子树。
2. 迭代：用栈，先压右子节点，再压左子节点。

中序遍历#

访问顺序：左 -> 根 -> 右。

核心性质：

1. 对二叉搜索树，中序结果是升序序列。

实现思路：

1. 递归：左子树完成后访问根，再访问右子树。
2. 迭代：一路向左入栈，弹出访问后转向右子树。

后序遍历#

访问顺序：左 -> 右 -> 根。

常见用途：

1. 删除树（先删子节点再删父节点）。
2. 计算树高、子树汇总信息。

实现思路：

1. 递归：左右子树都处理完成后再访问根。
2. 迭代：可使用双栈，或“访问标记法”单栈实现。

层序遍历#

访问顺序：按层从上到下、从左到右。

实现思路：

1. 使用队列。
2. 根节点入队。
3. 每次出队一个节点并访问，再将其左右孩子入队。

常见用途：

1. 求树的最大宽度。
2. 按层打印、锯齿形遍历、最短层数问题。