二叉树理论基础

发布于：2025-06-26 ⋅ 阅读:(23) ⋅ 点赞:(0)

二叉树理论基础详解

概述

二叉树是数据结构中最基础也是最重要的非线性数据结构之一。它不仅在算法设计中广泛应用，更是许多高级数据结构的基础。掌握二叉树的各种类型和特性，对于理解更复杂的树形结构和图算法至关重要。

二叉树的基本概念

二叉树（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）是一种有序的二叉树，具有以下性质：

  1. 若左子树不空，则左子树上所有结点的值均小于根结点的值
  2. 若右子树不空，则右子树上所有结点的值均大于根结点的值
  3. 左、右子树也分别为二叉搜索树

特点:

  • 中序遍历得到有序序列
  • 支持高效的查找、插入、删除操作
  • 平均时间复杂度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。

主要类型:

  1. AVL树: 最早的平衡二叉搜索树
  2. 红黑树: 应用最广泛的平衡树
  3. 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当:

  • 需要有序遍历
  • 需要找到最接近的值
  • 内存使用要求严格

使用哈希表当:

  • 只需要快速查找
  • 不需要有序性
  • 数据量较大

总结

二叉树作为基础数据结构，其各种变体在实际应用中发挥着重要作用：

  1. 满二叉树: 结构最规整，常用于理论分析（一定是完全二叉树）
  2. 完全二叉树: 堆的基础，数组存储效率高
  3. 二叉搜索树: 有序数据的高效管理
  4. 平衡二叉搜索树: 保证操作效率的稳定

二叉树的存储方式

二叉树的存储方式主要分为两种：链式存储和顺序存储。这两种方式各有优缺点，适用于不同的场景。

链式存储

定义: 链式存储通过指针将分布在内存中不同地址的节点串联起来，每个节点包含数据域和指针域。
在这里插入图片描述

节点结构:

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 = val
        self.left = left
        self.right = right

网站公告

今日签到

点亮在社区的每一天
去签到

热门文章

最新发布