二叉树理论基础
二叉树理论基础详解
概述
二叉树是数据结构中最基础也是最重要的非线性数据结构之一。它不仅在算法设计中广泛应用，更是许多高级数据结构的基础。掌握二叉树的各种类型和特性，对于理解更复杂的树形结构和图算法至关重要。
二叉树的基本概念
二叉树（Binary Tree） 是一种树形数据结构，其中每个节点最多有两个子节点，通常称为左子节点和右子节点。
基本术语
- 根节点（Root）: 树的顶层节点，没有父节点
- 叶子节点（Leaf）: 没有子节点的节点
- 内部节点（Internal Node）: 至少有一个子节点的节点
- 度（Degree）: 节点的子节点数量
- 深度（Depth）: 从根到该节点的路径长度
- 高度（Height）: 从该节点到最远叶子节点的路径长度
二叉树的种类
根据不同的结构和性质，二叉树可以分为以下几种主要类型：
满二叉树
定义: 如果一棵二叉树只有度为0的结点和度为2的结点，并且度为0的结点在同一层上，则这棵二叉树为满二叉树。
等价定义: 深度为k的满二叉树有2^k-1个节点。
特点:
- 每一层都被完全填满
- 所有叶子节点都在同一层
- 节点总数 = 2^深度 - 1
- 第i层的节点数 = 2^(i-1)
示例:
1/ \2 3/ \ / \4 5 6 7
数学性质:
- 设深度为h，则节点总数N = 2^h - 1
- 叶子节点数 = 2^(h-1)
- 内部节点数 = 2^(h-1) - 1
完全二叉树
定义: 在完全二叉树中，除了最底层节点可能没填满外，其余每层节点数都达到最大值，并且最下面一层的节点都集中在该层最左边的若干位置。
特点:
- 从上到下、从左到右填充节点
- 最底层节点集中在左侧
- 可以用数组表示（不使用索引0）
- 父节点索引i，左子节点索引2i，右子节点索引2i+1
示例:
1/ \2 3/ \ /4 5 6
重要应用:
- 堆（Heap）: 完全二叉树是堆的基础结构
- 优先级队列: 底层实现通常基于堆
- 数组表示: 可以高效地用数组存储
二叉搜索树
定义: 二叉搜索树（Binary Search Tree, BST）是一种有序的二叉树，具有以下性质：
- 若左子树不空，则左子树上所有结点的值均小于根结点的值
- 若右子树不空，则右子树上所有结点的值均大于根结点的值
- 左、右子树也分别为二叉搜索树
特点:
- 中序遍历得到有序序列
- 支持高效的查找、插入、删除操作
- 平均时间复杂度O(log n)，最坏情况O(n)
示例:
8/ \3 10/ \ \1 6 14/ \ /4 7 13
操作复杂度:
- 查找: O(log n) - O(n)
- 插入: O(log n) - O(n)
- 删除: O(log n) - O(n)
平衡二叉搜索树
定义: 平衡二叉搜索树是一种特殊的二叉搜索树，其中任意节点的左右子树高度差的绝对值不超过1。
主要类型:
- AVL树: 最早的平衡二叉搜索树
- 红黑树: 应用最广泛的平衡树
- B树/B+树: 用于数据库和文件系统
AVL树特点:
- 任意节点左右子树高度差≤1
- 插入/删除后需要重新平衡
- 查找效率稳定在O(log n)
示例:
8/ \4 12/ \ / \2 6 10 14/ \
1 7
实际应用与底层实现
C++ STL中的实现
基于平衡二叉搜索树的容器:
std::map: 有序键值对std::set: 有序集合std::multimap: 有序多重键值对std::multiset: 有序多重集合
基于哈希表的容器:
std::unordered_map: 无序键值对std::unordered_set: 无序集合
性能对比
| 操作 | 平衡BST | 哈希表 |
|---|---|---|
| 查找 | O(log n) | O(1) 平均 |
| 插入 | O(log n) | O(1) 平均 |
| 删除 | O(log n) | O(1) 平均 |
| 有序遍历 | O(n) | 不支持 |
选择建议
使用平衡BST当:
- 需要有序遍历
- 需要找到最接近的值
- 内存使用要求严格
使用哈希表当:
- 只需要快速查找
- 不需要有序性
- 数据量较大
总结
二叉树作为基础数据结构，其各种变体在实际应用中发挥着重要作用：
- 满二叉树: 结构最规整，常用于理论分析（一定是完全二叉树）
- 完全二叉树: 堆的基础，数组存储效率高
- 二叉搜索树: 有序数据的高效管理
- 平衡二叉搜索树: 保证操作效率的稳定
二叉树的存储方式
二叉树的存储方式主要分为两种：链式存储和顺序存储。这两种方式各有优缺点，适用于不同的场景。
链式存储
定义: 链式存储通过指针将分布在内存中不同地址的节点串联起来，每个节点包含数据域和指针域。
节点结构:
struct TreeNode {int val; // 数据域TreeNode* left; // 左子节点指针TreeNode* right; // 右子节点指针TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
};
特点:
- 节点在内存中分布不连续
- 通过指针连接各个节点
- 空间利用率相对较低（需要存储指针）
- 插入、删除操作灵活
- 适合表示任意形状的二叉树
示例:
1/ \2 3/ \ / \4 5 6 7
链式存储的内存布局：
节点1: [val=1, left→节点2, right→节点3]
节点2: [val=2, left→节点4, right→节点5]
节点3: [val=3, left→节点6, right→节点7]
节点4: [val=4, left=null, right=null]
节点5: [val=5, left=null, right=null]
节点6: [val=6, left=null, right=null]
节点7: [val=7, left=null, right=null]
优点:
- 结构直观，易于理解
- 插入、删除操作方便
- 不需要预先分配固定空间
- 适合表示不规则树形结构
缺点:
- 空间开销较大（每个节点需要存储指针）
- 随机访问效率低
- 缓存局部性差
顺序存储
定义: 顺序存储使用数组来存储二叉树，节点按照特定规则在数组中排列。
存储规则:
- 根节点存储在索引0位置
- 对于索引为i的节点：
- 左子节点索引：
2*i + 1 - 右子节点索引：
2*i + 2 - 父节点索引：
(i-1)/2（向下取整）
- 左子节点索引：
数组表示:
// 对于完全二叉树，可以用数组表示
int tree[] = {1, 2, 3, 4, 5, 6, 7};
索引关系:
1/ \2 3/ \ / \4 5 6 7
索引: 0 1 2 3 4 5 6
值: 1 2 3 4 5 6 7节点关系:
- 节点1(索引0): 左子=2(索引1), 右子=3(索引2)
- 节点2(索引1): 左子=4(索引3), 右子=5(索引4)
- 节点3(索引2): 左子=6(索引5), 右子=7(索引6)
特点:
- 节点在内存中连续分布
- 不需要存储指针
- 空间利用率高
- 随机访问效率高
- 适合完全二叉树
适用场景:
- 完全二叉树
- 堆（Heap）实现
- 需要频繁随机访问的场景
局限性:
- 对于非完全二叉树，空间浪费严重
- 插入、删除操作复杂
- 需要预先知道树的大小
存储方式对比
| 特性 | 链式存储 | 顺序存储 |
|---|---|---|
| 内存分布 | 不连续 | 连续 |
| 空间效率 | 较低（需要指针） | 较高 |
| 访问效率 | 随机访问慢 | 随机访问快 |
| 插入删除 | 灵活方便 | 复杂 |
| 适用树型 | 任意二叉树 | 完全二叉树 |
| 缓存友好性 | 差 | 好 |
| 实现复杂度 | 简单 | 中等 |
实际应用选择
选择链式存储当:
- 树结构不规则
- 需要频繁插入删除
- 内存充足
- 追求代码简洁性
选择顺序存储当:
- 完全二叉树
- 需要频繁随机访问
- 内存紧张
- 追求访问效率
混合使用:
在实际应用中，有时会结合两种方式的优点：
- 使用链式存储表示树结构
- 使用数组缓存热点数据
- 根据访问模式动态调整
二叉树的遍历方式
二叉树的遍历是访问树中所有节点的过程，主要有两种基本遍历方式：深度优先遍历和广度优先遍历。
深度优先遍历 (DFS)
深度优先遍历先往深走，遇到叶子节点再往回走。根据访问根节点的时机，可以分为三种：
前序遍历 (Preorder Traversal)
访问顺序: 中 → 左 → 右
特点:
- 先访问根节点
- 再遍历左子树
- 最后遍历右子树
- 常用于复制二叉树、前缀表达式
示例:
1/ \2 3/ \ / \4 5 6 7前序遍历结果: [1, 2, 4, 5, 3, 6, 7]
应用场景:
- 打印目录结构
- 表达式树的前缀表示
- 二叉树的序列化
中序遍历 (Inorder Traversal)
访问顺序: 左 → 中 → 右
特点:
- 先遍历左子树
- 再访问根节点
- 最后遍历右子树
- 对于BST，中序遍历得到有序序列
示例:
1/ \2 3/ \ / \4 5 6 7中序遍历结果: [4, 2, 5, 1, 6, 3, 7]
应用场景:
- 二叉搜索树的有序遍历
- 表达式树的中缀表示
- 二叉树的验证
后序遍历 (Postorder Traversal)
访问顺序: 左 → 右 → 中
特点:
- 先遍历左子树
- 再遍历右子树
- 最后访问根节点
- 常用于释放内存、后缀表达式
示例:
1/ \2 3/ \ / \4 5 6 7后序遍历结果: [4, 5, 2, 6, 7, 3, 1]
应用场景:
- 释放二叉树内存
- 表达式树的后缀表示
- 计算目录大小
广度优先遍历 (BFS)
广度优先遍历一层一层地访问节点，也称为层序遍历。
层序遍历 (Level Order Traversal)
访问顺序: 按层从左到右访问
特点:
- 从根节点开始，逐层访问
- 每层从左到右访问
- 使用队列实现
- 常用于求树的宽度、层数
示例:
1/ \2 3/ \ / \4 5 6 7层序遍历结果: [[1], [2, 3], [4, 5, 6, 7]]
应用场景:
- 求二叉树的最大宽度
- 求二叉树的最小深度
- 打印二叉树的层次结构
遍历方式的实现
递归实现
前序遍历递归:
void preorder(TreeNode* root) {if (root == nullptr) return;// 访问根节点cout << root->val << " ";// 遍历左子树preorder(root->left);// 遍历右子树preorder(root->right);
}
中序遍历递归:
void inorder(TreeNode* root) {if (root == nullptr) return;// 遍历左子树inorder(root->left);// 访问根节点cout << root->val << " ";// 遍历右子树inorder(root->right);
}
后序遍历递归:
void postorder(TreeNode* root) {if (root == nullptr) return;// 遍历左子树postorder(root->left);// 遍历右子树postorder(root->right);// 访问根节点cout << root->val << " ";
}
迭代实现
前序遍历迭代:
vector<int> preorderTraversal(TreeNode* root) {vector<int> result;if (root == nullptr) return result;stack<TreeNode*> st;st.push(root);while (!st.empty()) {TreeNode* node = st.top();st.pop();result.push_back(node->val);if (node->right) st.push(node->right);if (node->left) st.push(node->left);}return result;
}
层序遍历迭代:
vector<vector<int>> levelOrder(TreeNode* root) {vector<vector<int>> result;if (root == nullptr) return result;queue<TreeNode*> q;q.push(root);while (!q.empty()) {int levelSize = q.size();vector<int> level;for (int i = 0; i < levelSize; i++) {TreeNode* node = q.front();q.pop();level.push_back(node->val);if (node->left) q.push(node->left);if (node->right) q.push(node->right);}result.push_back(level);}return result;
}
遍历方式的选择
选择深度优先遍历当:
- 需要访问所有节点
- 问题具有递归性质
- 内存使用要求严格
选择广度优先遍历当:
- 需要按层处理
- 求最短路径
- 需要找到最近的节点
记忆技巧:
- 前中后序指的是根节点的访问时机
- 前序: 根节点在最前面
- 中序: 根节点在中间
- 后序: 根节点在最后面
二叉树定义
链式存储的二叉树节点的定义方式。
C++代码如下：
struct TreeNode {int val;TreeNode* left;TreeNode* right;TreeNode(int x) : val(x), left(NULL), right(NULL) {}
};
python：
class TreeNode:def __init__(self, val, left = None, right = None):self.val = valself.left = leftself.right = right