跳到主要内容
极客日志极客日志面向AI+效率的开发者社区
首页博客我的书AI学习GitHub 精选镜像AI工具UI配色美学关于
搜索内容 / 工具 / 仓库 / 镜像...⌘K搜索
注册
博客列表
C++算法

C++ 模拟实现二叉搜索树

二叉搜索树是一种利用左小右大特性实现高效查找的数据结构。详细解析了 C++ 中 BST 的节点设计、插入、查找、删除及中序遍历的实现细节，重点讲解了删除操作中左右子树均非空时的替换策略。内容涵盖仅 Key 与 Key-Value 两种应用场景的代码实现，并通过完整测试用例演示了基本用法。理解 BST 逻辑是掌握 map/set 等关联式容器底层机制的重要前提。

www发布于 2026/2/24更新于 2026/10/2291 浏览

概述

二叉搜索树（Binary Search Tree，BST）是计算机科学中经典的树形数据结构。它利用'左子树值≤根节点值≤右子树值'的结构性约束，实现了高效的动态查找、插入和删除操作。在理想平衡状态下，这些操作的时间复杂度可控制在 O(logN)；而在最坏的单支树场景下，则退化为 O(N)。

C++ 标准库中的 map、set、multimap、multiset 等关联式容器，其核心逻辑正是基于二叉搜索树构建（红黑树作为其平衡优化版本）。本文将拆解节点设计、树的构建及核心操作的实现逻辑，涵盖'仅存关键码'与'键值对'两种典型应用场景，并给出完整的 C++11 代码示例。

性能分析

  • 最好情况：树的结构接近完全二叉树，高度为 logN，此时查找、插入、删除操作的时间复杂度为 O(logN)。
  • 最坏情况：树退化为单支树，高度为 N，此时操作的时间复杂度退化为 O(N)。

二叉搜索树结构图

核心实现

节点定义

二叉搜索树本质是由节点连接而成的链式结构。每个节点包含关键码、左孩子指针和右孩子指针。

#pragma once
#include <iostream>
using namespace std;

// 二叉搜索树节点结构
template <class K>
struct BSTNode {
    K _key;              // 节点存储的关键码
    BSTNode<K>* _left;   // 左孩子节点指针
    BSTNode<K>* _right;  // 右孩子节点指针

    // 构造函数：初始化节点
    BSTNode(const K& key) : _key(key), _left(nullptr), _right(nullptr) {}
};

类封装

将二叉搜索树封装为类，根节点作为私有成员以保证数据封装性。使用 C++11 的 using 简化节点类型名。

template <class K>
class BSTree {
     Node = BSTNode<K>;  
:
    
    ;
    ;
    ;
    ;

:
    
     _InOrder(Node* root);
    Node* _root = ;    
};
using
// C++11 类型别名
public
// 核心操作声明
bool Insert(const K& key)
bool Find(const K& key)
bool Erase(const K& key)
void InOrder()
private
// 私有辅助函数：中序遍历的递归实现
void
nullptr
// 根节点指针，初始化为空

插入操作

插入逻辑遵循 BST 规则：若树为空，直接创建新节点作为根；若不为空，按大小关系遍历找到空位置后插入。若不支持重复值，遇到相等值则返回失败。

template <class K>
bool BSTree<K>::Insert(const K& key) {
    // 情况 1：树为空，直接创建根节点
    if (_root == nullptr) {
        _root = new Node(key);
        return true;
    }

    // 情况 2：树不为空，遍历找到插入位置
    Node* cur = _root;
    Node* parent = nullptr;  // 记录当前节点的父节点

    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;  // 大于当前节点，向右遍历
        } else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;   // 小于当前节点，向左遍历
        } else {
            // 找到相等值，不插入（若支持重复值，可改为向右/左遍历）
            return false;
        }
    }

    // 找到空位置，创建新节点并连接到父节点
    cur = new Node(key);
    if (parent->_key < key) {
        parent->_right = cur;  // 新节点值更大，连接到父节点右孩子
    } else {
        parent->_left = cur;   // 新节点值更小，连接到父节点左孩子
    }
    return true;
}

查找操作

从根节点开始比较：查找值大于根节点则向右查找，小于则向左查找。遍历至空节点说明查找失败，找到相等值则返回成功。

template <class K>
bool BSTree<K>::Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_key < key) {
            cur = cur->_right;  // 大于当前节点，向右查找
        } else if (cur->_key > key) {
            cur = cur->_left;   // 小于当前节点，向左查找
        } else {
            return true;        // 找到目标值，返回成功
        }
    }
    return false;               // 遍历至空，查找失败
}

删除操作

删除是 BST 中最复杂的操作，需分三种情况处理：

  1. 左孩子为空：将父节点的对应指针指向当前节点的右孩子。
  2. 右孩子为空：将父节点的对应指针指向当前节点的左孩子。
  3. 左右孩子都不为空：采用'替换法'，找右子树的最小节点（或左子树的最大节点）替换目标节点，再删除替换节点。
template <class K>
bool BSTree<K>::Erase(const K& key) {
    Node* cur = _root;
    Node* parent = nullptr;

    while (cur) {
        if (cur->_key < key) {
            parent = cur;
            cur = cur->_right;
        } else if (cur->_key > key) {
            parent = cur;
            cur = cur->_left;
        } else {
            // 找到要删除的节点
            // 情况 1：左孩子为空（叶子节点/仅右孩子）
            if (cur->_left == nullptr) {
                if (cur == _root) {
                    _root = cur->_right;
                } else {
                    if (parent->_left == cur) {
                        parent->_left = cur->_right;
                    } else {
                        parent->_right = cur->_right;
                    }
                }
                delete cur;
            }
            // 情况 2：右孩子为空（叶子节点/仅左孩子）
            else if (cur->_right == nullptr) {
                if (cur == _root) {
                    _root = cur->_left;
                } else {
                    if (parent->_right == cur) {
                        parent->_right = cur->_left;
                    } else {
                        parent->_left = cur->_left;
                    }
                }
                delete cur;
            }
            // 情况 3：左右孩子都不为空（替换法删除）
            else {
                // 找右子树的最小节点（最左节点）作为替换节点
                Node* replaceParent = cur;
                Node* replace = cur->_right;
                while (replace->_left) {
                    replaceParent = replace;
                    replace = replace->_left;
                }
                // 替换目标节点的关键码
                cur->_key = replace->_key;
                // 连接替换节点的父节点与替换节点的右孩子
                if (replaceParent->_left == replace) {
                    replaceParent->_left = replace->_right;
                } else {
                    replaceParent->_right = replace->_right;
                }
                delete replace;
            }
            return true;
        }
    }
    return false;  // 未找到目标节点，删除失败
}

中序遍历

二叉搜索树的中序遍历结果为升序序列，是验证树结构正确性的核心方式。

template <class K>
void BSTree<K>::_InOrder(Node* root) {
    if (root == nullptr) return;
    _InOrder(root->_left);      // 遍历左子树
    cout << root->_key << " "; // 访问当前节点
    _InOrder(root->_right);     // 遍历右子树
}

template <class K>
void BSTree<K>::InOrder() {
    _InOrder(_root);
    cout << endl;
}

应用场景

仅关键码（Key）场景

节点仅存储关键码 key，操作仅关注'key 是否存在'。典型场景包括小区车库车牌验证、英文单词拼写检查等。

键值对（Key/Value）场景

节点存储 key + value，增删查以 key 为关键字，支持修改 value。典型场景包括中英互译字典、停车计费系统、单词词频统计等。

// 键值对版本的节点结构
template <class K, class T>
struct BSTNodeKV {
    K _key;
    T _value;
    BSTNodeKV<K, T>* _left;
    BSTNodeKV<K, T>* _right;

    BSTNodeKV(const K& key, const T& value)
        : _key(key), _value(value), _left(nullptr), _right(nullptr) {}
};

// 键值对版本的二叉搜索树
template <class K, class T>
class BSTreeKV {
    using Node = BSTNodeKV<K, T>;
public:
    bool Insert(const K& key, const T& value) {
        if (_root == nullptr) {
            _root = new Node(key, value);
            return true;
        }
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                return false;  // 不支持重复 key
            }
        }
        cur = new Node(key, value);
        if (parent->_key < key) {
            parent->_right = cur;
        } else {
            parent->_left = cur;
        }
        return true;
    }

    T* Find(const K& key) {
        Node* cur = _root;
        while (cur) {
            if (cur->_key < key) {
                cur = cur->_right;
            } else if (cur->_key > key) {
                cur = cur->_left;
            } else {
                return &(cur->_value);  // 返回 value 地址，支持修改
            }
        }
        return nullptr;
    }

    bool Erase(const K& key) {
        Node* cur = _root;
        Node* parent = nullptr;
        while (cur) {
            if (cur->_key < key) {
                parent = cur;
                cur = cur->_right;
            } else if (cur->_key > key) {
                parent = cur;
                cur = cur->_left;
            } else {
                if (cur->_left == nullptr) {
                    if (cur == _root) _root = cur->_right;
                    else if (parent->_left == cur) parent->_left = cur->_right;
                    else parent->_right = cur->_right;
                    delete cur;
                } else if (cur->_right == nullptr) {
                    if (cur == _root) _root = cur->_left;
                    else if (parent->_right == cur) parent->_right = cur->_left;
                    else parent->_left = cur->_left;
                    delete cur;
                } else {
                    Node* replaceParent = cur;
                    Node* replace = cur->_right;
                    while (replace->_left) {
                        replaceParent = replace;
                        replace = replace->_left;
                    }
                    cur->_key = replace->_key;
                    cur->_value = replace->_value;
                    if (replaceParent->_left == replace) replaceParent->_left = replace->_right;
                    else replaceParent->_right = replace->_right;
                    delete replace;
                }
                return true;
            }
        }
        return false;
    }

    void InOrder() {
        _InOrder(_root);
        cout << endl;
    }

private:
    void _InOrder(Node* root) {
        if (root == nullptr) return;
        _InOrder(root->_left);
        cout << "key: " << root->_key << ", value: " << root->_value << " ";
        _InOrder(root->_right);
    }
    Node* _root = nullptr;
};

测试示例

void TestBSTree() {
    BSTree<int> t;
    int a[] = {8, 3, 1, 10, 6, 4, 7, 14, 13};
    for (auto e : a) {
        t.Insert(e);
    }
    cout << "中序遍历（升序）：";
    t.InOrder();  // 输出：1 3 4 6 7 8 10 13 14

    cout << "查找 6：" << (t.Find(6) ? "成功" : "失败") << endl;
    cout << "删除 3：" << (t.Erase(3) ? "成功" : "失败") << endl;
    cout << "删除后中序遍历：";
    t.InOrder();  // 输出：1 4 6 7 8 10 13 14
}

void TestBSTreeKV() {
    BSTreeKV<string, int> dict;
    dict.Insert("apple", 1);
    dict.Insert("banana", 2);
    dict.Insert("orange", 3);
    cout << "中序遍历键值对：";
    dict.InOrder();

    // 修改 banana 的 value
    int* p = dict.Find("banana");
    if (p) *p = 20;
    cout << "修改后中序遍历：";
    dict.InOrder();
}

int main() {
    TestBSTree();
    TestBSTreeKV();
    return 0;
}

总结

二叉搜索树的核心在于'有序性'，所有操作均围绕这一特性展开。本文实现的基础版本覆盖了核心功能，实际工程中（如 C++ 标准库）会通过红黑树对其进行平衡优化，避免单支树的性能退化。理解二叉搜索树的底层逻辑，是掌握关联式容器和高效检索算法的关键基础。

目录

  1. 概述
  2. 性能分析
  3. 核心实现
  4. 节点定义
  5. 类封装
  6. 插入操作
  7. 查找操作
  8. 删除操作
  9. 中序遍历
  10. 应用场景
  11. 仅关键码（Key）场景
  12. 键值对（Key/Value）场景
  13. 测试示例
  14. 总结

更多推荐文章

查看全部
  • C++ 红黑树原理与实现详解
  • Rust、Go、Java、Python、Node.js 内存管理深度对比
  • 5 款开源 PPT 生成大模型实测：ChatGPT 与文心一言等技术对比
  • AI 大模型在专利翻译中的应用与核心功能解析
  • 递归与链表实战：汉诺塔、链表操作及快速幂详解
  • AIGC 时代下的模型上下文协议 MCP 详解
  • 前端状态管理进阶：Recoil 原子化实战指南
  • 基于 DeepSeek 和 Cursor 构建智能代码审查工具实践
  • QQ 机器人接入 OpenClaw 配置指南
  • 全球顶级AI大模型最新排名出炉！Gemini 3.1 Pro与GPT-5.4智能并列第一，中国 GLM-5强势杀入前 5，DeepSeek V3.2 成性价比之王！
  • Python 基础语法完全指南：变量、类型、运算符与字符串处理
  • 九联UNT413A 刷机流程解析与注意事项
  • Midjourney AI 图像生成器使用教程详解
  • FPGA DDR4 读写基础：MIG IP 核控制信号详解
  • 大模型技术入门与进阶学习指南
  • LangChain 大模型对话记忆模块实战与 Web 应用搭建
  • Python FastAPI 入门实战：从环境搭建到数据模型
  • 基于 SwiftUI 开发 iOS Ollama 客户端实践
  • 精选 13 个优质编程学习资源与工具
  • Seedance 2.0 实操教程：从入门到 AI 导演模式

相关免费在线工具

  • 加密/解密文本

    使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online

  • Gemini 图片去水印

    基于开源反向 Alpha 混合算法去除 Gemini/Nano Banana 图片水印，支持批量处理与下载。 在线工具，Gemini 图片去水印在线工具，online

  • Base64 字符串编码/解码

    将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online

  • Base64 文件转换器

    将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online

  • Markdown转HTML

    将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online

  • HTML转Markdown

    将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online