二叉树
二叉树（Binary Tree）：每个节点最多有两个子节点（左子节点和右子节点）的树形结构。它是最基本的树形结构，节点间没有特定的顺序要求。
二叉树的DFS todo
前中后续遍历
- 递归
- 非递归（栈）
神级遍历 morris
二叉树全类型对比与 Java 实现
以下是常见二叉树类型的详细对比，包括定义、特点、所属类别、示例、关键性质、现实应用场景及 Java 代码示例：
一、基础分类二叉树
1. 普通二叉树（Binary Tree）
定义：每个节点最多有两个子节点的树结构。
特点：无特殊约束，结构自由。
示例
：
plaintext
1 / \ 2 3 / 4关键性质：节点数 n≥0，高度 h≥0。
应用：作为其他树结构的基础。
2. 完美二叉树（Perfect Binary Tree）
定义：所有层节点数达到最大值，叶子节点在最后一层。
特点：总节点数 n=2h+1−1（h 为高度）。
示例
：
plaintext
1 / \ 2 3 / \ / \ 4 5 6 7关键性质：每层节点数为 2h，结构对称。
应用：理论模型、并行计算。
3. 完全二叉树（Complete Binary Tree）
定义：除最后一层外满，最后一层节点左对齐。
特点：适合数组存储，父子关系通过下标计算。
示例
：
plaintext
1 / \ 2 3 / \ / 4 5 6关键性质：高度 h=⌊log2n⌋，最后一层可能不满。
应用：二叉堆、堆排序。
4. 满二叉树（Full Binary Tree）
定义：每个非叶子节点有两个子节点。
特点：叶子节点数 = 非叶子节点数 + 1。
示例
：
plaintext
1 / \ 2 3 / \ 4 5关键性质：总节点数为奇数。
应用：理论模型。
二、搜索类二叉树
5. 二叉搜索树（BST, Binary Search Tree）
定义：左子树 ≤ 根 ≤ 右子树，中序遍历有序。
特点：平均操作 O(logn)，可能退化为链表。
示例
：
plaintext
5 / \ 3 7 / \ / \ 2 4 6 8关键性质：中序遍历结果为升序。
应用：动态数据集合、查找表。
6. AVL 树（平衡二叉搜索树）
定义：BST 的子类，每个节点的左右子树高度差 ≤ 1。
特点：通过旋转维持平衡，高度始终 O(logn)。
示例
：
plaintext
5 / \ 3 7 / / \ 2 6 8关键性质：四种旋转操作（左旋、右旋、左右旋、右左旋）。
应用：数据库索引、高效查找插入删除。
7. 红黑树（Red-Black Tree）
定义：BST 的子类，通过颜色标记和规则约束维持近似平衡。
特点：最长路径 ≤ 2 倍最短路径，插入 / 删除效率优于 AVL 树。
关键规则
：
- 节点为红色或黑色。
- 根节点和叶子节点（NIL）是黑色。
- 红色节点的子节点必须是黑色。
- 从任一节点到其每个叶子的路径包含相同数目的黑色节点。
应用：Java TreeMap/TreeSet、Linux 内存管理。
8. 伸展树（Splay Tree）
- 定义：BST 的子类，访问频繁的节点靠近根节点。
- 特点：通过伸展操作（Splaying）将最近访问的节点移至根。
- 关键性质：自适应优化，局部性原理提升效率。
- 应用：缓存系统、垃圾回收算法。
9. 替罪羊树（Scapegoat Tree）
- 定义：BST 的子类，在失衡时通过重构子树恢复平衡。
- 特点：插入 / 删除后检查平衡因子，超过阈值则重构。
- 关键性质：重构操作分摊时间复杂度 O(logn)。
- 应用：需要稳定性能的场景。
三、其他特殊二叉树
10. 霍夫曼树（Huffman Tree）
- 定义：带权路径长度（WPL）最小的二叉树。
- 特点：权值越大的叶子离根越近，用于数据压缩。
- 应用：JPEG、ZIP 等压缩算法。
11. 二叉堆（Binary Heap）
- 定义：完全二叉树，满足堆性质（大根堆 / 小根堆）。
- 特点：插入 / 删除 O(logn)，适合优先队列。
- 应用：任务调度、Dijkstra 算法。
12. 线段树（Segment Tree）
- 定义：每个节点代表一个区间，用于高效处理区间查询。
- 特点：查询、更新时间复杂度 O(logn)。
- 应用：区间求和、区间最值查询。
四、Java 代码示例
1. AVL 树（平衡二叉搜索树）
java
public class AVLTree {
static class Node {
int val, height;
Node left, right;
Node(int val) {
this.val = val;
this.height = 1;
}
}
private Node root;
private int height(Node node) {
return node == null ? 0 : node.height;
}
private int getBalance(Node node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
private Node rightRotate(Node y) {
Node x = y.left;
Node T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
private Node leftRotate(Node x) {
Node y = x.right;
Node T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
public void insert(int val) {
root = insertRec(root, val);
}
private Node insertRec(Node node, int val) {
if (node == null) return new Node(val);
if (val < node.val) {
node.left = insertRec(node.left, val);
} else {
node.right = insertRec(node.right, val);
}
node.height = 1 + Math.max(height(node.left), height(node.right));
int balance = getBalance(node);
if (balance > 1 && val < node.left.val) {
return rightRotate(node);
}
if (balance < -1 && val > node.right.val) {
return leftRotate(node);
}
if (balance > 1 && val > node.left.val) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && val < node.right.val) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
}
2. 红黑树（简化版）
java
public class RedBlackTree {
private static final boolean RED = true;
private static final boolean BLACK = false;
static class Node {
int val;
Node left, right;
boolean color;
Node(int val) {
this.val = val;
this.color = RED;
}
}
private Node root;
private boolean isRed(Node node) {
return node == null ? false : node.color == RED;
}
private Node rotateLeft(Node h) {
Node x = h.right;
h.right = x.left;
x.left = h;
x.color = h.color;
h.color = RED;
return x;
}
private Node rotateRight(Node h) {
Node x = h.left;
h.left = x.right;
x.right = h;
x.color = h.color;
h.color = RED;
return x;
}
private void flipColors(Node h) {
h.color = RED;
h.left.color = BLACK;
h.right.color = BLACK;
}
public void insert(int val) {
root = insert(root, val);
root.color = BLACK;
}
private Node insert(Node h, int val) {
if (h == null) return new Node(val);
if (val < h.val) {
h.left = insert(h.left, val);
} else {
h.right = insert(h.right, val);
}
if (isRed(h.right) && !isRed(h.left)) h = rotateLeft(h);
if (isRed(h.left) && isRed(h.left.left)) h = rotateRight(h);
if (isRed(h.left) && isRed(h.right)) flipColors(h);
return h;
}
}
3. 伸展树（Splay Tree）
java
public class SplayTree {
static class Node {
int val;
Node left, right;
Node(int val) { this.val = val; }
}
private Node root;
private Node splay(Node root, int val) {
if (root == null || root.val == val) {
return root;
}
if (val < root.val) {
if (root.left == null) return root;
if (val < root.left.val) {
root.left.left = splay(root.left.left, val);
root = rotateRight(root);
} else if (val > root.left.val) {
root.left.right = splay(root.left.right, val);
if (root.left.right != null) {
root.left = rotateLeft(root.left);
}
}
return (root.left == null) ? root : rotateRight(root);
} else {
if (root.right == null) return root;
if (val > root.right.val) {
root.right.right = splay(root.right.right, val);
root = rotateLeft(root);
} else if (val < root.right.val) {
root.right.left = splay(root.right.left, val);
if (root.right.left != null) {
root.right = rotateRight(root.right);
}
}
return (root.right == null) ? root : rotateLeft(root);
}
}
private Node rotateRight(Node x) {
Node y = x.left;
x.left = y.right;
y.right = x;
return y;
}
private Node rotateLeft(Node x) {
Node y = x.right;
x.right = y.left;
y.left = x;
return y;
}
public void insert(int val) {
if (root == null) {
root = new Node(val);
return;
}
root = splay(root, val);
if (val < root.val) {
Node newNode = new Node(val);
newNode.left = root.left;
newNode.right = root;
root.left = null;
root = newNode;
} else if (val > root.val) {
Node newNode = new Node(val);
newNode.right = root.right;
newNode.left = root;
root.right = null;
root = newNode;
}
}
}
五、关键性质对比表
| 树类型 | 所属类别 | 平衡条件 | 时间复杂度 | 特点 | 应用场景 |
|---|---|---|---|---|---|
| 完美二叉树 | 基础二叉树 | 所有层节点数最大 | O(logn) | 结构对称，节点数 2h+1−1 | 理论模型、并行计算 |
| 完全二叉树 | 基础二叉树 | 最后一层左对齐 | O(logn) | 适合数组存储 | 二叉堆、堆排序 |
| 满二叉树 | 基础二叉树 | 非叶子节点有两个子节点 | O(h) | 叶子数 = 非叶子数 + 1 | 理论模型 |
| 二叉搜索树 | 搜索类 | 无强制平衡 | 平均 O(logn) | 中序遍历有序 | 动态数据集合 |
| AVL 树 | 搜索类（BST 子类） | 左右子树高度差 ≤ 1 | O(logn) | 严格平衡，旋转维护 | 数据库索引、高效查找 |
| 红黑树 | 搜索类（BST 子类） | 最长路径 ≤ 2 倍最短路径 | O(logn) | 近似平衡，插入 / 删除效率高 | Java TreeMap、Linux 内存管理 |
| 伸展树 | 搜索类（BST 子类） | 频繁访问的节点靠近根 | 均摊 O(logn) | 自适应优化 | 缓存系统、垃圾回收 |
| 替罪羊树 | 搜索类（BST 子类） | 失衡时重构子树 | O(logn) | 重构操作分摊开销 | 需要稳定性能的场景 |
| 霍夫曼树 | 特殊应用 | 带权路径长度最小 | O(nlogn) | 用于数据压缩 | JPEG、ZIP 压缩算法 |
| 二叉堆 | 特殊应用 | 完全二叉树 + 堆性质 | O(logn) | 优先队列实现 | 任务调度、Dijkstra 算法 |
| 线段树 | 特殊应用 | 每个节点代表一个区间 | O(logn) | 高效区间查询 | 区间求和、区间最值查询 |
六、总结
基础二叉树（完美、完全、满）是结构定义，用于理论模型和存储优化。
搜索类二叉树（BST 及其子类）通过有序性实现高效查找，AVL 树追求严格平衡，红黑树在效率和平衡间折中，伸展树利用局部性原理。
特殊应用二叉树（霍夫曼树、二叉堆、线段树）针对特定问题设计，如压缩、优先队列和区间查询。
选择建议
：
- 数据分布均匀且操作简单：BST
- 需要严格平衡：AVL 树
- 频繁插入删除：红黑树
- 访问具有局部性：伸展树
- 特定领域问题：选择对应专用树结构
通过理解各种二叉树的特性和适用场景，可以在实际开发中做出更优的数据结构选择。
六、总结对比表
| 树类型 | 定义与核心特点 | 关键性质 | 典型应用场景 | 时间复杂度 |
|---|---|---|---|---|
| 完美二叉树 | 所有层节点数达到最大值，叶子在最后一层 | 总节点数 2h+1−1 | 理论模型、并行算法 | 所有操作 O(h) |
| 完全二叉树 | 除最后一层外满，最后一层节点左对齐 | 适合数组存储，父子关系通过下标计算 | 二叉堆、堆排序 | 插入 / 删除 O(logn) |
| 满二叉树 | 每个非叶子节点有两个子节点 | 叶子数 = 非叶子数 + 1 | 理论模型 | 所有操作 O(h) |
| 二叉搜索树 | 左子树 ≤ 根 ≤ 右子树，中序遍历有序 | 平均操作 O(logn)，可能退化 | 动态数据集合、查找表 | 最坏 O(n) |
| 平衡二叉树 | 每个节点的左右子树高度差 ≤ 1 | 通过旋转维持平衡，高度始终 O(logn) | 数据库索引、高效查找插入删除 | 所有操作 O(logn) |
七、选择建议
- 需要严格对称结构：选择完美二叉树（如理论分析）。
- 需要高效存储和访问：选择完全二叉树（如二叉堆）。
- 需要有序性和动态操作：选择二叉搜索树（需注意避免退化）。
- 需要严格平衡：选择平衡二叉树（如 AVL 树、红黑树）。