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

C++ 二叉搜索树（BST）原理与完整实现

讲解 C++ 中二叉搜索树（BST）的核心概念、性能分析及增删查操作。通过递归与非递归方式实现节点插入、查找与删除逻辑，涵盖 Key 及 Key-Value 两种结构变体，并分析其在实际场景中的应用价值。重点修复了常见实现中的内存管理与边界条件问题，提供可直接参考的完整代码示例。

鲜活发布于 2026/3/23更新于 2026/6/2125 浏览
C++ 二叉搜索树（BST）原理与完整实现

C++ 二叉搜索树（BST）原理与完整实现

一、二叉搜索树的性能分析和概念

1.1 二叉搜索树的概念

二叉搜索树又称二叉排序树，它或者是一棵空树，或者是具有下列性质的二叉树：

  • 若它的左子树不为空，则左子树上所有结点的值都小于等于根结点的值。
  • 若它的右子树不为空，则右子树上所有结点的值都大于等于根结点的值。
  • 它的左右子树都是二叉搜索树。

二叉搜索树中可以支持插入相等的值，也可以不支持插入相等的值，具体看使用场景定义。例如 map/set/multimap/multiset 系列容器底层就是二叉搜索树，其中 map/set 不支持插入相等值，multimap/multiset 支持插入相等值。

1.2 二叉搜索树的性能分析

由于它本身和它的子树都是二叉搜索树，观察上面的特点不难发现：二叉搜索树的中序遍历一定是升序序列（所以二叉搜索树又称二叉排序树）。

二叉搜索树顾名思义，其主要用于搜索（或者搜索效率高），下面我们来分析其最优情况和最差情况。

最优情况下，二叉搜索树为完全二叉树（或者接近完全二叉树），其高度为：$\log_2 N$。 最差情况下，二叉搜索树退化为单支树（或者类似单支），其高度为：$N$。

所以综合而言二叉搜索树增删查改时间复杂度为：$O(N)$。那么这样的效率显然是无法满足我们需求的，必须将二叉搜索树优化即二叉搜索树的变形：平衡二叉搜索树 AVL 树和红黑树，才能适用于我们在内存中存储和搜索数据。

那有的人说使用二分查找也可以实现 $O(\log_2 N)$ 级别的查找效率，为啥还有将二叉搜索树变形外？需要说明的是，二分查找也可以实现 $O(\log_2 N)$ 级别的查找效率，但是二分查找有两大缺陷：

  1. 需要存储在支持下标随机访问的结构中，并且有序。
  2. 插入和删除数据效率很低，因为存储在下标随机访问的结构中，插入和删除数据一般需要挪动数据。

这里也就体现出了平衡二叉搜索树的价值。

二、二叉搜索树增删查的实现

这里主要关注增删查，修改一个 key 就可能不是二叉搜索树的结构了，所以通常不支持直接修改 key。

2.1 二叉搜索树基本结构的实现

2.1.1 节点的定义

由于后面实现二叉搜索树要访问节点成员，所以这里使用 struct 定义（默认是公有）。

template<class K> struct BSTreeNode {
    BSTreeNode* _left;
    BSTreeNode* _right;
    K _key;
    
    BSTreeNode(const K& key) :_left(nullptr), _right(nullptr), _key(key) { }
};
2.1.2 默认成员函数

由于二叉搜索树涉及到节点资源的开辟、拷贝、删除，所以这里我们需要自己写拷贝构造、赋值重载、析构函数。默认构造一般不满足我们的需求，所以看情况是否要写。而这里由于我们需要写拷贝构造（一种特殊的默认构造），所以这里一定要手写默认规则（可以缺省值）。

2.1.2.1 二叉搜索树的基本结构
template<class K> class BSTree {
     BSTreeNode<K> Node;
:
    Node* _root = ;
};
typedef
private
nullptr
2.1.2.2 二叉搜索树的默认构造
// 方法二
BSTree() = default;
2.1.2.3 二叉搜索树的拷贝构造

前面的链式结构的树的拷贝需要递归完成（即使用了递归），所以访问私有成员（在类外面调用该函数会出错）。而这个函数的实现过程仅供内部使用，所以这里应该定义一个私有函数，再定义一个公有函数来调用对应的私有函数。

public:
    // 拷贝构造
    BSTree(const BSTree<K>& t) {
        _root = Copy(t._root);
    }

private:
    Node* Copy(Node* root) {
        if (root == nullptr) {
            return nullptr;
        }
        // 注意：这里不能直接赋值 root，需要 new 一个新节点
        Node* copy = new Node(root->_key);
        copy->_left = Copy(root->_left);
        copy->_right = Copy(root->_right);
        return copy;
    }
2.1.2.4 二叉搜索树的赋值重载
public:
    // 赋值重载
    BSTree& operator=(const BSTree<K>& t) {
        swap(_root, t._root);
        return *this;
    }
2.1.2.5 二叉搜索树的析构

前面的链式结构的树的拷贝需要递归完成，所以访问私有成员（在类外面调用该函数会出错）。而这个函数的实现过程仅供内部使用，所以这里应该定义一个私有函数，再定义一个公有函数来调用对应的私有函数。

public:
    // 析构函数
    ~BSTree() {
        Destroy(_root);
    }

private:
    void Destroy(Node* root) {
        if (root == nullptr) {
            return;
        }
        Destroy(root->_left);
        Destroy(root->_right);
        delete root;
    }

2.2 二叉搜索树的插入

2.2.1 二叉搜索树的插入整体思路
  1. 树为空，则直接新增结点，赋值给 root 指针。
  2. 树不空，按二叉搜索树性质，插入值比当前结点大往右走，插入值比当前结点小往左走，找到空位置，插入新结点。
  3. 注意：如果支持插入相等的值，插入值跟当前结点相等的值可以往右走，也可以往左走，找到空位置，插入新结点。（要注意的是要保持逻辑一致性，插入相等的值不要一会往右走，一会往左走）。【这里我们不讲，一般不用】
2.2.2 二叉搜索树的插入代码实现
// 1 插入数据 - 不支持插入已有数据
bool Insert(const K& key) {
    // 树为空，则直接新增结点，赋值给 root 指针
    if (_root == nullptr) {
        _root = new Node(key);
        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;
        }
    }
    
    cur = new Node(key); // 创建新节点
    // 要判断插入的是当前节点的左子节点还是右子节点
    if (parent->_key < key) {
        parent->_right = cur;
    } else {
        parent->_left = cur;
    }
    return true;
}

2.3 二叉搜索树的查找

2.3.1 二叉搜索树的查找整体思路
  1. 从根开始比较，查找 x，x 比根的值大则往右边找，x 比根值小则往左边找。
  2. 最多查找高度次，走到空，还没找到，这个值不存在。
  3. 如果不支持插入相等的值，找到 x 即可返回。注意：如果支持插入相等的值，意味着有多个 x 存在，一般要求查找中序的第一个 x。
2.3.2 二叉搜索树的查找代码实现
// 2 查找数据
bool Find(const K& key) {
    Node* cur = _root;
    while (cur) {
        if (cur->_key < key) { // 从根开始比较，查找 x，x 比根的值大则往右边找
            cur = cur->_right;
        } else if (cur->_key > key) { // x 比根值小则往左边找
            cur = cur->_left;
        } else {
            return true; // 找到返回
        }
    }
    return false; // 走到空，还没找到，这个值不存在。
}

2.4 二叉搜索树的删除（最难）

2.4.1 二叉搜索树删除的整体思路

首先查找元素是否在二叉搜索树中，如果不存在，则返回 false。如果查找元素存在则分以下四种情况（假设要删除的结点为 x）：

  • 情况一：问题：要删除结点 x 左右孩子均为空。
    • 解决办法：把 x 结点的父亲对应孩子指针指向空，直接删除 x 结点。
  • 情况二：问题：要删除的结点 x 左孩子位空，右孩子结点不为空。
    • 解决办法：把 x 结点的父亲对应孩子指针指向 x 的右孩子，在直接删除 x 结点。
  • 情况三：问题：要删除的结点 x 右孩子位空，左孩子结点不为空。
    • 解决办法：把 x 结点的父亲对应孩子指针指向 x 的左孩子，在直接删除 x 结点。
  • 情况四（最复杂）：问题：要删除的结点 x 左右孩子结点均不为空。
    • 解决办法：无法直接删除 x 结点，因为 x 的两个孩子无处安放，只能用替换法删除。找 x 左子树的值最大结点 R（最右结点）或者 x 右子树的值最小结点 R（最左结点）替代 x，因为这两个结点中任意一个，放到 x 的位置，都满足二叉搜索树的规则。替代 x 的意思就是 x 和 R 的两个结点的值交换，转而变成删除 R 结点，R 结点符合情况 2 或情况 3，可以直接删除。

总结：情况 1 可以当成 2 或者 3 处理，效果是一样的。这些情况就好比一个人生孩子，如果只是生了一个孩子甚至没生孩子可以找父母帮忙，如果生了两个孩子父母忙不过来怎么办呢？这时候可以找一个保姆的思路。

2.4.2 二叉搜索树删除的代码实现
// 删除数据
bool Erase(const K& key) {
    // 先找到要删除的节点的位置
    Node* parent = nullptr;
    Node* cur = _root;
    
    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 (cur == parent->_left) {
                        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 (cur == parent->_left) {
                        parent->_left = cur->_left;
                    } else {
                        parent->_right = cur->_left;
                    }
                }
                delete cur; // 删除要删除的结点
            } 
            // 3 有两孩子 - 两种处理方法这里使用找右子树中最小值节点
            else {
                Node* pMinRight = cur;
                Node* minRight = cur->_right;
                // 找到右子树中值最小的节点
                while (minRight->_left) {
                    pMinRight = minRight;
                    minRight = minRight->_left;
                }
                // 交换值
                std::swap(minRight->_key, pMinRight->_key);
                // 此时 minRight 变成了待删除节点，且它没有左孩子，转化为情况 2
                if (pMinRight->_left == minRight) {
                    pMinRight->_left = minRight->_right;
                } else {
                    pMinRight->_right = minRight->_right;
                }
                delete minRight;
            }
            return true;
        }
    }
    return false;
}

2.5 二叉搜索树的排序（使用中序遍历）

由于使用到了中序遍历即使用了递归，所以访问私有成员（在类外面调用该函数会出错），所以这里应该定义一个私有函数，再定义一个公有函数来调用对应的私有函数。

// 排序 - 利用其特点这里可以使用中序遍历
void InOrder() { // 定义一个公有函数来调用对应的私有函数
    _InOrder(_root);
    cout << endl;
}

private:
void _InOrder(Node* root) { // 定义一个私有函数
    if (root == nullptr) {
        return;
    }
    _InOrder(root->_left);
    cout << root->_key << " ";
    _InOrder(root->_right);
}

三、Key 和 (Key, Value) 结构

上面我们实现的二叉搜索树，节点中只储存了一个值 (key)，key 称为关键码，关键码即为需要搜索到的值，使用这种搜索二叉树只需要判断 key 是否存在。key 的搜索场景实现的二叉搜索树支持增删查，但是不支持修改，修改 key 破坏搜索树结构了（性质）。

这里还有一种搜索二叉树：(key, value) 结构的二叉搜索树：每一个关键码还是 key，但是每一个关键码都有与之对应的值 value，value 可以任意类型对象。所以树的结构中（结点）除了需要存储 key 还要存储对应的 value，注意增/删/查还是以 key 为关键字在二叉搜索树的规则下操作，这里不支持修改 key，支持修改 value。

4.1 Key 和 (Key, Value) 结构搜索二叉树的定义

namespace key_value {
    template<class K, class V> struct BSTreeNode {
        BSTreeNode<K, V>* _left;
        BSTreeNode<K, V>* _right;
        K _key;
        V _value;
        
        BSTreeNode(const K& key, const V& value) :_left(nullptr), _right(nullptr), _key(key), _value(value) {}
    };
    
    template<class K, class V> class BSTree {
        typedef BSTreeNode<K, V> Node;
    public:
        // 强制生成
        BSTree() = default;
        
        // 拷贝构造
        BSTree(const BSTree<K, V>& t) {
            _root = Copy(t._root);
        }
        
        // 赋值重载
        BSTree& operator=(const BSTree<K, V>& t) {
            swap(_root, t._root);
            return *this;
        }
        
        // 析构
        ~BSTree() {
            Destory(_root);
            _root = nullptr;
        }
        
        bool Insert(const K& key, const V& value) {
            if (_root == nullptr) {
                _root = new Node(key, value);
                return true;
            }
            Node* parent = nullptr;
            Node* cur = _root;
            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, value);
            if (parent->_key < key) {
                parent->_right = cur;
            } else {
                parent->_left = cur;
            }
            return true;
        }
        
        Node* 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;
                }
            }
            return nullptr;
        }
        
        bool Erase(const K& key) {
            Node* parent = nullptr;
            Node* cur = _root;
            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 (cur == parent->_left) {
                                parent->_left = cur->_right;
                            } else {
                                parent->_right = cur->_right;
                            }
                        }
                        delete cur;
                    } else if (cur->_right == nullptr) {
                        if (cur == _root) {
                            _root = cur->_left;
                        } else {
                            if (cur == parent->_left) {
                                parent->_left = cur->_left;
                            } else {
                                parent->_right = cur->_left;
                            }
                        }
                        delete cur;
                    } else { // 两个孩子
                        Node* pMinRight = cur;
                        Node* minRight = cur->_right;
                        while (minRight->_left) {
                            pMinRight = minRight;
                            minRight = minRight->_left;
                        }
                        std::swap(cur->_key, minRight->_key);
                        if (pMinRight->_left == minRight) {
                            pMinRight->_left = minRight->_right;
                        } else {
                            pMinRight->_right = minRight->_right;
                        }
                        delete minRight;
                    }
                    return true;
                }
            }
            return false;
        }
        
        void InOrder() {
            _InOrder(_root);
            cout << endl;
        }
        
    private:
        void _InOrder(Node* root) {
            if (root == nullptr) {
                return;
            }
            _InOrder(root->_left);
            cout << root->_key << ":" << root->_value << endl;
            _InOrder(root->_right);
        }
        
        void Destory(Node* root) {
            if (root == nullptr) {
                return;
            }
            Destory(root->_left);
            Destory(root->_right);
            delete root;
        }
        
        Node* Copy(Node* root) {
            if (root == nullptr) return nullptr;
            Node* copy = new Node(root->_key, root->_value);
            copy->_left = Copy(root->_left);
            copy->_right = Copy(root->_right);
            return copy;
        }
        
        Node* _root = nullptr;
    };
}

四、二叉搜索树使用场景

4.1 二叉搜索树 Key 使用场景

  1. 小区无人值守车库：小区车库买了车位的业主车才能进小区，那么物业会把买了车位的业主的车牌号录入后台系统，车辆进入时扫描车牌不在系统中，在则抬杆，不在则提示非本小区车辆，无法进入。
  2. 拼写检查：检查一篇英文文章单词拼写是否正确，将词库中所有单词放入二叉搜索树，读取文章中的单词，查找是否在二叉搜索树中，不在则波浪线标红提示。

4.2 二叉搜索树 Key/Value 使用场景

  1. 简单中英互译字典：树的结构中（结点）存储 key（英文）和 value（中文），搜索时输入英文，则同时查找到了英文对应的中文。
  2. 商场无人值守车库：入口进场时扫描车牌，记录车牌和入场时间，出口离场时，扫描车牌，查找入场时间，用当前时间 - 入场时间计算出停车时长，计算出停车费用，缴费后抬杆，车辆离场。
  3. 统计单词出现次数：统计一篇文章中单词出现的次数，读取一个单词，查找单词是否存在，不存在这个说明第一次出现（单词，1），单词存在，则 ++ 单词对应的次数。

目录

  1. C++ 二叉搜索树（BST）原理与完整实现
  2. 一、二叉搜索树的性能分析和概念
  3. 1.1 二叉搜索树的概念
  4. 1.2 二叉搜索树的性能分析
  5. 二、二叉搜索树增删查的实现
  6. 2.1 二叉搜索树基本结构的实现
  7. 2.1.1 节点的定义
  8. 2.1.2 默认成员函数
  9. 2.1.2.1 二叉搜索树的基本结构
  10. 2.1.2.2 二叉搜索树的默认构造
  11. 2.1.2.3 二叉搜索树的拷贝构造
  12. 2.1.2.4 二叉搜索树的赋值重载
  13. 2.1.2.5 二叉搜索树的析构
  14. 2.2 二叉搜索树的插入
  15. 2.2.1 二叉搜索树的插入整体思路
  16. 2.2.2 二叉搜索树的插入代码实现
  17. 2.3 二叉搜索树的查找
  18. 2.3.1 二叉搜索树的查找整体思路
  19. 2.3.2 二叉搜索树的查找代码实现
  20. 2.4 二叉搜索树的删除（最难）
  21. 2.4.1 二叉搜索树删除的整体思路
  22. 2.4.2 二叉搜索树删除的代码实现
  23. 2.5 二叉搜索树的排序（使用中序遍历）
  24. 三、Key 和 (Key, Value) 结构
  25. 4.1 Key 和 (Key, Value) 结构搜索二叉树的定义
  26. 四、二叉搜索树使用场景
  27. 4.1 二叉搜索树 Key 使用场景
  28. 4.2 二叉搜索树 Key/Value 使用场景
  • 免费图片AI生成工具免费生成了解详情
  • Magick API 一键接入全球大模型注册送1000万token查看
  • 免费图片视频在线生成30秒，将你的创意变成现实开始设计
  • X/Twitter免费视频下载器免登陆无限额度免费视频解析下载了解详情
  • 100+免费在线小游戏爽一把
极客日志微信公众号二维码

微信扫一扫，关注极客日志

微信公众号「极客日志V2」，在微信中扫描左侧二维码关注。展示文案：极客日志V2 zeeklog

更多推荐文章

查看全部
  • incbin：C/C++二进制文件嵌入工具使用指南
  • IBM Watson Conversation API 实战：机场客服场景与上下文管理
  • 生成式 AI 在软件开发全流程中的应用现状与协同挑战
  • 医疗 AI 新范式：数理模型重构传统大模型
  • GitHub Copilot Agent 模式使用经验与配置指南
  • Flutter Genkit 在鸿蒙端的适配：模型幻觉审计与端云协同 AI 方案
  • 基于大模型构建专属 AI 应用的实践指南
  • Copilot 的 Agent、Ask、Edit、Plan 模式核心区别解析
  • 基于 Langchain-Chatchat 快速构建本地 LLM 智能知识库
  • Android WebView 内核升级方案详解与实战
  • 数据结构空间复杂度详解：概念与常见计算示例
  • VS Code 搭配 GitHub Copilot 实战指南：配置、避坑与高效工作流
  • Python 电力系统分析工具 PYPOWER 实战指南
  • 955 不加班公司名单及工作制说明
  • Ubuntu 20.04 NVIDIA Tesla P40 驱动安装指南（核显桌面 + 计算卡分离）
  • 91n 边缘计算设备部署轻量 TensorFlow 模型全流程
  • Windows 10 本地部署 OpenClaw 智能体实践指南
  • AIGC 基础概念与常见应用解析
  • 基于 FPGA 的高精度 TDC 设计
  • 风险管控而非修补：金仓 SQL 防火墙体系化实践

相关免费在线工具

  • 加密/解密文本

    使用加密算法（如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