【C++】带你手搓二叉搜索树(2w字详解)

二叉搜索树

• 二叉搜索树
• github地址
• 0. 前言
• 1. 二叉搜索树的定义
• 2. 整体架构设计
• • 结点设计
  • 树结构设计
• 3. 相关操作实现
• • 1. 构造与析构
  • • 构造
    • 析构
  • 2. 拷贝构造与赋值
  • • 拷贝构造
    • operator=赋值
  • 3. 插入
  • • 迭代版插入
    • 递归插入
  • 4. 查找
  • • 迭代查找：
    • 递归查找：
  • 5. 中序遍历
  • 6. 删除
  • • 迭代删除
    • • 情况一
      • 情况二
      • 情况三
      • 完整代码与逐步说明
    • 递归删除
• 4. 性能分析
• 5. 完整实现代码
• 6. 结语

二叉搜索树

github地址

有梦想的电信狗

0. 前言

​ 在学习 C++ 的过程中，STL 容器 是我们最常用的工具之一，而这些容器的底层实现，往往依赖于 二叉搜索树（BST）及其变种。理解二叉搜索树不仅能帮助我们掌握 STL 的设计思想，还能加深对数据结构本质的理解与代码实现能力。

本文将带你从零开始，手搓一个 STL 风格的二叉搜索树，并逐步分析实现背后的逻辑与原理。

文章内容结构如下：

• 基础定义 —— 了解二叉搜索树的性质与特点
• 整体架构 —— 节点设计与树类的组织方式
• 核心操作 —— 构造、析构、拷贝与赋值
• 查找与插入 —— 迭代与递归两种实现思路
• 遍历与删除 —— 中序遍历获取有序序列，复杂的删除逻辑拆解
• 性能分析 —— 不同情况下的时间复杂度与效率瓶颈

通过本篇文章，你不仅可以 亲手实现一棵可用的二叉搜索树，还将为后续学习 AVL 树、红黑树等平衡二叉树 打下扎实的基础。

1. 二叉搜索树的定义

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

• 若它的左子树不为空，则左子树上所有节点的值都小于其根节点的值
• 若它的右子树不为空，则右子树上所有节点的值都大于根节点的值
• 它的左右子树也分别为二叉搜索树
• ⼆叉搜索树中可以⽀持插⼊相等的值，也可以不⽀持插⼊相等的值，具体看使⽤场景定义.
  • 后续学习的 map/set/multimap/multiset系列容器底层就是⼆叉搜索树，其中 map/set 不⽀持插⼊相等值，multimap/multiset⽀持插⼊相等值

2. 整体架构设计

结点设计

// 二叉搜索树template<class K>struct BSTreeNode {BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;};

• 二叉搜索树常用于存储键值，方便查找关键字。因此我们的模板参数使用K来表示，结点内存放的数据为_key
• 结点中的成员变量：
  • BSTreeNode* _left：指向左孩子的指针
  • BSTreeNode* _right：指向右孩子的指针
  • K _key：存储相应的的键值
• 默认构造函数：
  • 将三个指针初始化为nullptr
  • 初始化数据_key为传入的值key
• 结点采用struct设计，默认权限为public，方便下文的BSTree类访问成员

树结构设计

template<typename K>class BSTree {typedef BSTreeNode<K> Node;public:// ...（以下为类的成员函数）private:Node* _root;};

• BSTreeNode 是模板节点，包含左右指针和键 _key。
• BSTree 以 _root 指向树根。类内 typedef BSTreeNode Node; 简化后续代码书写。
• 设计上采用裸指针管理节点（非智能指针），因此必须显式实现拷贝与析构，避免内存泄露。
• 架构图如下：

3. 相关操作实现

1. 构造与析构

构造

public:BSTree():_root(nullptr){ }

• BSTree()：默认构造，构造一颗空树，只需将根节点指针 _root 置空即可

析构

public:~BSTree() {Destroy(_root);}private:// Destroy（后序删除） void Destroy(Node*& root) { if (root == nullptr) return; // 二叉树的析构，走后序遍历删除 Destroy(root->_left); Destroy(root->_right); delete root; root = nullptr; }

• 由于析构函数无参数无返回值，而我们释放节点需要操作_root结点及其子节点管理的内存资源，因此无法通过传统传参递归的方式释放节点。

• 我们设计了一个子函数，子函数完成结点的清理释放工作，析构函数直接调用子函数即可

• 子函数void Destroy(Node*& root) ：后序遍历删除实现

  • 必须先释放左右子节点再释放父节点，因此我们采用后序遍历删除，依次递归释放左子树，右子树，最后释放根节点，这里和普通二叉树的释放结点操作相同

  • Node*& root 引用形式，函数栈帧中的形参root成为了每个节点的地址的别名。Node*& root 引用形式允许在删除左右子树后把父指针设为 nullptr，避免悬空指针。

  • 析构 ~BSTree()：调用 Destroy(_root) 做后序销毁，释放所有节点。

2. 拷贝构造与赋值

拷贝构造

public: BSTree(const BSTree<K>& tree) :_root(nullptr) { _root = Copy(tree._root); }private: Node* Copy(Node* root) { if (root == nullptr) return nullptr; else { Node* newRoot = new Node(root->_key); // 分别递归拷贝 左右子树，拷贝完后，递归回去连接 newRoot->_left = Copy(root->_left); newRoot->_right = Copy(root->_right); return newRoot; } }

• 这里和析构函数类似，利用子函数实现树的拷贝。

  • 原因是：拷贝构造函数的参数必须为const BSTree&类型，而我们拷贝树需要依次拷贝每个节点，递归拷贝节点时需要传入根节点作为参数。

• 拷贝构造 BSTree(const BSTree&)：先把 _root 初始化为 nullptr，再调用私有 Copy做深拷贝，_root接收返回的新树的根。这样可以保证两个树互不干扰。

• Copy()函数的逻辑，整体逻辑采用递归实现：
  • 遇到非空结点，对该结点进行拷贝，新结点的指针保存在函数栈帧中
  • 再分别递归拷贝左子树、右子树
  • 遇到nullptr空结点时，向上级栈帧中返回结点的指针，完成结点的链接关系
• 总结：
  • 递去时不断建立栈帧，拷贝结点
  • 归来，return时，向上级栈帧中返回所拷贝结点的指针

左子树的递归展开图如下：

operator=赋值

operator=的现代写法：

// t2 = t1public:BSTree<K>& operator=(BSTree<K> tmp) {std::swap(_root, tmp._root);return *this;}

赋值运算符 operator=(BSTree tmp)重载：采用**拷贝-并-交换（copy-and-swap）**技巧：t2 = t1

• 形参 tmp为值传递， 会调用拷贝构造生成一个局部副本（或借助移动语义），该副本 tmp 也为一个BSTree对象，和t1的内容完全一致，且有各自独立的数据空间。
• std::swap(_root, tmp._root) 交换资源，更改管理资源的指针的指向，这样 tmp 的析构会自动释放旧资源。
• 这种写法简洁且有异常安全性（strong exception guarantee）。
• 以上写法可以类比之前vector中operator=的实现，只需要把_start指针换成这里的_root指针即可

3. 插入

迭代版插入

• 默认插入的元素不能重复

// 插入时，需要先找到空位置bool insert(const K& key) {// 插入时为空树if (_root == nullptr) {_root = new Node(key);return true;}// 不是空树时Node* parent = nullptr;Node* curNode = _root;while (curNode != nullptr) {if (key > curNode->_key) {parent = curNode;curNode = curNode->_right;}else if (key < curNode->_key) {parent = curNode;curNode = curNode->_left;}else {return false;}}// 走完循环curNode 找到了可以插入的位置 // 但要插入结点，必须修改父节点的指针，父节点并不知道key是比自己大还是自己小，只知道有一个结点需要插入 // 因此要再比较一次curNode = new Node(key);if (key > parent->_key)parent->_right = curNode;elseparent->_left = curNode;return true;}

详细讲解（迭代插入逻辑）：

• 插入时，需要先找到空位置，默认插入的元素不能重复

1. 空树特判：若 _root == nullptr，直接把根设为新节点（new Node(key)）。
2. 否则从 _root 向下查找插入位置：
   • 使用 curNode 跟随，parent 保存其父节点（因为当 curNode 为 nullptr 时需要把新节点挂到 parent）。
   • 如果 key > curNode->_key，curNode沿右子树移动；key _key时，curNode沿左子树移动。
   • 如果 key == curNode->_key，返回 false（二叉搜索树默认不允许重复键）。
3. 当 curNode 走到 nullptr（找到空位）后，代表curNode已找到合适的可以插入的位置。
4. new Node(key) 建节点
   • 要插入新结点，必须修改curNode的父节点内的左右孩子指针，但父节点并不知道要插入的 key 比自己大还是自己小，只知道下面由位置可以插入，不知道插入到哪个位置
   • 因此要根据 key 与 parent->_key 的比较把它接为左/右子节点。
     • 如果 key > parent->_key → 插到右边 (parent->_right = newNode)
     • 如果 key _key → 插到左边 (parent->_left = newNode)

• 总结：

  ✔️ 循环结束时，位置已经找到了，就是 curNode == nullptr 的地方。
  ✔️ 但是插入操作不能直接修改 curNode，必须通过 parent 去改指针。
  ✔️ 而 parent 自己并不知道空位是在左边还是右边，所以需要再比较一次来决定。

关键点与陷阱：

• curNode 用来遍历，parent 跟随；这是常见的迭代插入模式。
• 新节点分配后必须从父节点parent链入整棵树
• 不允许重复键

递归插入

public: bool insert_R(const K& key) { return _insert_R(_root, key); }private: bool _insert_R(Node*& root, const K& key) { // 走到空的地方，可以开始插入了 // 这里可以记录父节点，修改父节点的指针完成插入。不过比较复杂，这里使用 if (root == nullptr) { root = new Node(key); return true; } if (key < root->_key) return _insert_R(root->_left, key); else if (key > root->_key) return _insert_R(root->_right, key); else return false; }

要点：

• _insert_R 的参数是 Node*& root（对指针的引用），这使得当 root 为 nullptr 时可以直接写 root = new Node(key); 来修改父节点的指针，而不需要再记录父节点再通过父节点的比较完成结点的插入，简化了父指针的管理。
• 按照二叉搜索树的规则，递归插入：
  • key _key时，return _insert_R(root->_left, key)递归去左子树中插入
  • key > root->_key时，return _insert_R(root->_right, key)递归去右子树中插入
  • ==时返回false，键不允许重复

递归与迭代的复杂度比较（两种方式相同）：

• 时间复杂度：

  • 平均为 O(h)，其中 h 为树的高度；
  • 若树退化为链表（完全不平衡），退化到 O(n)。

• 空间复杂度：

  • （递归版）额外为递归栈深度 O(h)，其中 h 为树的高度；

4. 查找

迭代查找：

bool find(const K& key) const {Node* curNode = _root;while (curNode) {if (key == curNode->_key)return true;else if (key > curNode->_key)curNode = curNode->_right;elsecurNode = curNode->_left;} // 循环结束时，循环内没有返回，代表没有找到，返回falsereturn false;}

• 标准 BST 查找：从根出发比较，curNode = _root，curNode 从根节点出发开始找，按照二叉搜索树的性质查找即可

• curNode 表示当前结点，curNode的移动结合了二叉搜树的性质：

  • key == curNode->_key时，成功，返回true
  • key > curNode->_key时，curNode去右子树查找
  • key _key时，curNode去左子树查找

• 循环结束时，若循环内没有返回，代表没有找到，则循环外返回false

递归查找：

public: bool find_R(const K& key) const { return _find_R(_root, key); }private: bool _find_R(const Node* root, const K& key) const { if (root == nullptr) return false; if (key < root->_key) return _find_R(root->_left, key); else if (key > root->_key) return _find_R(root->_right, key); // 不大于，不小于 表明查找成功 else return true; }

• 递归版本自然表达了 BST 的定义：

  • 若查找到为空结点，表明查找失败

• key > 当前节点的_key时，递归去右子树查找

• key < 当前节点的_key时，递归去左子树查找

• 不大于，不小于时，表明查找成功，返回true

• 参数 const Node* 保证不会修改树。

5. 中序遍历

由二叉搜索树的性质可得，对二叉搜索树进行中序遍历，可以得到升序序列

中序遍历可以用于升序打印 BST 中的键。代码如下：

public: void Inorder() const { _Inorder(_root); printf(\"\\n\"); }private: void _Inorder(Node* root = _root) const { if (root == nullptr) { return; } _Inorder(root->_left); cout << root->_key << \" \"; _Inorder(root->_right); }

要点：

• 利用子函数实现中序遍历即可

• _Inorder 是典型的递归中序：左 - 根 - 右。
• 对 BST 做中序遍历会得到有序（从小到大）序列，这也是 BST 在排序/输出上的常见用途。
• 注意：_Inorder 写成 void _Inorder(Node* root = _root) const，默认参数指向成员 _root，调用Inorder()默认从根节点开始遍历

6. 删除

迭代删除

• 删除时，需要先走查找的逻辑，找到要被删除的节点：

bool erase(const K& key) {Node* parent = nullptr;Node* curNode = _root;// _root为空时，进不去while循环，会直接return false while (curNode) {// 先找要被删除的节点if (key > curNode->_key) {parent = curNode;curNode = curNode->_right;}else if (key < curNode->_key) {parent = curNode;curNode = curNode->_left;}// 找到了，找到了，删除分为三种情况else { // ... 删除的逻辑 } } // 没找到 return false return false;}

情况一

// 找到后的删除逻辑else { // 情况一 // curNode 的左为空 if (curNode->_left == nullptr) { // 特殊情况，左为空且curNode 为_root if (curNode == _root) _root = curNode->_right; // 托孤，需要知道孤儿 应该成为 父节点的左子树还是右子树, 需要先找孤儿在左右那个子树 // 孤儿在左子树 else if (curNode == parent->_left) { parent->_left = curNode->_right; } // 孤儿在右子树 else { parent->_right = curNode->_right; } delete curNode; return true; } // 情况二 ... // 情况三 ...  return true;}

• 左子树为空（curNode->_left == nullptr）：

  • 如果该节点是根：_root = curNode->_right;

  • 否则根据 curNode 是父节点的左/右孩子，把父指针指向结点curNode->_right（托孤），再 delete curNode。

  • 这包含了叶子节点（左右都空）和只有右孩子的情况（因为左空且右可能为空或非空）。

情况二

// 找到后的删除逻辑else { // 情况一 ... // 情况二 ... // curNode 的右为空 else if (curNode->_right == nullptr) { if (curNode == _root) _root = curNode->_left; // 托孤 // 当前结点是父的左节点 else if (curNode == parent->_left) { parent->_left = curNode->_left; } // 当前结点是父的右节点 else { parent->_right = curNode->_left; } delete curNode; return true; } // 情况三 ...  return true;}

• 右子树为空（curNode->_right == nullptr）：
  • 与左子树为空时对称：
  • 如果该节点是根：_root = curNode->_left;
  • 否则根据 curNode 是父节点的左/右孩子，把父指针指向结点 curNode->_left（托孤），再 delete curNode。
  • 这包含了叶子节点（左右都空）和只有右孩子的情况（因为左空且右可能为空或非空）。

情况三

• 情况三的删除逻辑，替换法

• 需要找左子树中最大的、或右子树中最小的替换当前要被删除的结点
  • 二叉搜索树中：
    • 子树的最大结点，是树中最右边的结点
    • 子树的最小结点，是树中最左边的结点
• 这里找左子树中最大的结点

// 找到后的删除逻辑else { // 情况一 ...  // 情况二 ...  // 情况三 ... // curNode的左右都不为空，需要在树中找一个结点替换curNode else { // 找左子树中最大的结点 Node* maxNode = curNode->_left; Node* maxParent = curNode; // 有可能进不去while循环，对应于删除时的 else 条件 // 进不去while时，此时maxNode初始就是左子树的最大结点，parent和curNode重合 while (maxNode->_right != nullptr) { maxParent = maxNode; maxNode = maxNode->_right; }// 循环结束后，maxNode为左子树中最大的结点 curNode->_key = maxNode->_key;// 替换值 // 左子树的最大结点一定没有右孩子，但可能有左孩子 // maxNode可能是Parent的右孩子，且maxNode可能有左孩子 if (maxNode == maxParent->_right) { maxParent->_right = maxNode->_left; } // maxNode也可能是Parent的左孩子，且maxNode可能有左孩子 else { // maxNode是curNode->_left，此时pareng->_left就是maxNode maxParent->_left = maxNode->_left; } delete maxNode; } return true;}

• 左右子树皆非空：

  • 用左子树中的最大节点或右子树中的最小节点替换当前节点的值，然后删除左子树中的最大节点或右子树中的最小节点

  • 本代码选择用左子树的最大节点 maxNode替换curNode（即向左一次再一路向右走到最右）。

  • 找到 maxNode 及其父 maxParent 后， curNode->_key = maxNode->_key替换curNode中的值，然后把 maxNode 从树上摘除：

    • maxNode是左子树的最大值，因此maxNode一定没有右孩子，但可能会有左孩子，左孩子要挂回 maxParent
    • 且maxNode既可能是maxParent的左节点，也可能是maxParent的右节点，如下图所示(假设删除3)，两图中最大值都为2，分别是maxParent的右孩子和左孩子

  • 

  • 托孤的代码：

  •  // 左子树的最大结点一定没有右孩子，但可能有左孩子 // maxNode可能是Parent的右孩子，且maxNode可能有左孩子 if (maxNode == maxParent->_right) { maxParent->_right = maxNode->_left;// 托孤 } // maxNode也可能是Parent的左孩子，且maxNode可能有左孩子 else { // maxNode是curNode->_left，此时pareng->_left就是maxNode maxParent->_left = maxNode->_left;// 托孤 } delete maxNode;

  • 托孤需要确认孤儿结点是在parent的左子树还是右子树，正确托孤后释放结点

完整代码与逐步说明

bool erase(const K& key) {Node* parent = nullptr;Node* curNode = _root;// _root为空时，进不去while循环，会直接return false while (curNode) {// 先找要被删除的节点if (key > curNode->_key) {parent = curNode;curNode = curNode->_right;}else if (key < curNode->_key) {parent = curNode;curNode = curNode->_left;}// 找到了，找到了，删除分为三种情况else {// curNode 的左为空if (curNode->_left == nullptr) {// 特殊情况，左为空且curNode 为_rootif (curNode == _root)_root = curNode->_right;// 托孤，需要知道孤儿 应该称为 父节点的左子树还是右子树// 需要先找孤儿在左右那个子树// 孤儿在左子树else if (curNode == parent->_left) {parent->_left = curNode->_right;}// 孤儿在左子树else {parent->_right = curNode->_right;}delete curNode;return true;}// curNode 的右为空else if (curNode->_right == nullptr) {if (curNode == _root)_root = curNode->_left;// 托孤// 当前结点是父的左节点else if (curNode == parent->_left) {parent->_left = curNode->_left;}// 当前结点是父的右节点else {parent->_right = curNode->_left;}delete curNode;return true;}// curNode的左右都不为空，需要在树中找一个结点替换curNodeelse {// 需要找左子树中最大的、或右子树中最小的替换当前结点// 二叉搜索树中，子树的最大结点，是树中最右边的结点//  子树的最小结点，是树中最左边的结点// 这里找左子树中最大的结点Node* maxNode = curNode->_left;Node* maxParent = curNode;// 有可能进不去while循环，对应于删除时的 else 条件// 进不去while时，此时maxNode初始就是左子树的最大结点，parent和curNode重合while (maxNode->_right != nullptr) {maxParent = maxNode;maxNode = maxNode->_right;}// 循环结束后，maxNode为左子树中最大的结点curNode->_key = maxNode->_key;// 替换值// 左子树的最大结点一定没有右孩子，但可能有左孩子// maxNode可能是Parent的右孩子，且maxNode可能有左孩子if (maxNode == maxParent->_right) {maxParent->_right = maxNode->_left;}// maxNode也可能是Parent的左孩子，且maxNode可能有左孩子else { // maxNode是curNode->_left，此时pareng->_left就是maxNodemaxParent->_left = maxNode->_left;}delete maxNode;}return true;}}return false;}

• 左子树为空（curNode->_left == nullptr）：

  • 如果该节点是根：_root = curNode->_right;

  • 否则根据 curNode 是父节点的左/右孩子，把父指针指向 curNode->_right（托孤），再 delete curNode。

  • 这包含了叶子节点（左右都空）和只有右孩子的情况（因为左空且右可能为空或非空）。

• 右子树为空（curNode->_right == nullptr）：

  • 与左子树为空时对称：
  • 如果该节点是根：_root = curNode->_left;
  • 否则根据 curNode 是父节点的左/右孩子，把父指针指向 curNode->_left（托孤），再 delete curNode。
  • 这包含了叶子节点（左右都空）和只有右孩子的情况（因为左空且右可能为空或非空）

• 左右子树皆非空：

  • 需要找左子树中最大的、或右子树中最小的替换当前要被删除的结点
    • 二叉搜索树中：
      • 子树的最大结点，是树中最右边的结点
      • 子树的最小结点，是树中最左边的结点
  • 这里找左子树中最大的结点
  • 用左子树中的最大节点或右子树中的最小节点替换当前节点的值，然后删除左子树中的最大节点或右子树中的最小节点

  • 本代码选择用左子树的最大节点 maxNode替换curNode（即向左一次再一路向右走到最右）。

  • 找到 maxNode 及其父 maxParent 后， curNode->_key = maxNode->_key替换curNode中的值，然后把 maxNode 从树上摘除：

    • maxNode是左子树的最大值，因此maxNode一定没有右孩子，但可能会有左孩子，左孩子要挂回 maxParent
    • 且maxNode既可能是maxParent的左节点，也可能是maxParent的右节点

  • 托孤的代码：

  •  // 左子树的最大结点一定没有右孩子，但可能有左孩子 // maxNode可能是Parent的右孩子，且maxNode可能有左孩子 if (maxNode == maxParent->_right) { maxParent->_right = maxNode->_left;// 托孤 } // maxNode也可能是Parent的左孩子，且maxNode可能有左孩子 else { // maxNode是curNode->_left，此时pareng->_left就是maxNode maxParent->_left = maxNode->_left;// 托孤 } delete maxNode;

  • 托孤需要确认孤儿结点是在parent的左子树还是右子树，正确托孤后释放结点

• while循环结束后，代表三种情况中都未完成删除，返回false

递归删除

完整代码：

public: bool erase_R(const K& key) { return _erase_R(_root, key); }private: bool _erase_R(Node*& root, const K& key) { if (root == nullptr) return false; if (key > root->_key) return _erase_R(root->_right, key); else if (key < root->_key) return _erase_R(root->_left, key); // 相等时要删除 else { Node* delNode = root; // 1. curNode 左为空 if (root->_left == nullptr) { root = root->_right; } // 2. curNode 右为空 else if (root->_right == nullptr) { root = root->_left; } // 3. curNode 左右都不为空 else { // 找左子树中最大的结点 Node* maxNode = root->_left; while (maxNode->_right) {  maxNode = maxNode->_right; } std::swap(maxNode->_key, root->_key); // 交换过后，原来的maxNode是左子树中最大的结点，因此其右子树一定为空 // 再去左子树中删除一遍 return _erase_R(root->_left, key); } delete delNode; return true; }}

代码中查找的逻辑依然需要：

• root == nullptr时，返回false
• key > root->_key时，递归去右子树中查找
• key _key时，递归去左子树中查找
• else代表相等，查找到了要被删除的结点

bool _erase_R(Node*& root, const K& key) {if (root == nullptr) return false; if (key > root->_key) return _erase_R(root->_right, key); else if (key < root->_key) return _erase_R(root->_left, key); // 相等时要删除 else { // ... }}

else中的删除代码：

// 相等时要删除else { Node* delNode = root; // 这里 写成 curNode 是为了和迭代删除法的形式匹配 // 1. curNode 左为空 if (root->_left == nullptr) { root = root->_right; } // 2. curNode 右为空 else if (root->_right == nullptr) { root = root->_left; } // 3. curNode 左右都不为空 else { // 找左子树中最大的结点 Node* maxNode = root->_left; while (maxNode->_right) { maxNode = maxNode->_right; } std::swap(maxNode->_key, root->_key); // 交换过后，原来的maxNode是左子树中最大的结点，因此其右子树一定为空 // 再去左子树中删除一遍 return _erase_R(root->_left, key); } delete delNode; return true;}

• 参数 Node*& root 是==对结点指针的直接引用==，使得当我们把 root 指向 root->_right（或 _left）时，父节点相应的指针会被更新（递归中直接修改）。
• 删除时前两种情况的思路依然是托孤，第三种采用替换法：
  • Node*& root 是==对结点指针的直接引用==，托孤时无需记录parent指针，可以直接对其修改
    • 若其左子树为空，将 root 指向 root->_right（托孤），再 delete delNode。
    • 若其右子树为空，类似处理。
    • 若左右都不为空：找到左子树最大节点 maxNode，交换值（swap），然后在左子树递归删除原来持有该值的那个节点。
  • 递归的本质：
    1. 交换 key
       • root 是要被删除的结点，但它有左右孩子，不能直接删。
       • 于是我们找到左子树中最大的结点 maxNode，把 root->_key 和 maxNode->_key 交换。
       • 这样 逻辑上相当于“把删除任务转移到了 maxNode”。
    2. 为什么 maxNode 一定能删除？
       • maxNode 是左子树中最大的结点，所以它 不可能有右子树（因为再往右就超过它了）。
       • 它可能有左孩子，也可能没有。
       • 这就转化成了 情况1 或 情况2（更简单的删除）。
    3. 递归删除
       • 因为 root->_key 已经被换成了 maxNode->_key，那么树里相当于有两个相同的 key。
       • 所以我们递归到 root->_left 去 继续删除 key。
       • 最终会定位到 maxNode，并用情况1或2把它删掉。
• 递归删除写法短小且清晰，利用引用参数避免手工维护父节点 parent。
• 👉 总结一句话：
  第三种情况的递归逻辑就是：把当前结点和左子树最大结点交换，让删除目标转移到最大结点，然后递归在左子树中删除这个目标。最终会简化成情况1或2。

4. 性能分析

• 查找 / 插入 / 删除（平均）时间复杂度：O(h)，h 为树高。
• 空间：迭代版本额外 O(1)；递归版本额外 O(h) 递归栈。
• 拷贝构造/Copy: O(n) 时间与 O(h) 递归栈。

结点数为N的二叉搜索树，最多查找高度次。对于随机插入的平衡树平均 h = O(log n)；最坏情况下 h = O(n)。

• 最优情况下：⼆叉搜索树为完全⼆叉树(或者接近完全二叉树)，其高度为： log2 N

• 最差情况下：⼆叉搜索树（退化为单链表），其高度为： N

综合而言，⼆叉搜索树增删查改时间复杂度为： O(N)

那么这样的效率显然是⽆法满⾜我们需求的，后续会学习⼆叉搜索树的变形，平衡⼆叉搜索树AVL树和红⿊树，才能适⽤于我们在内存中存储和搜索数据高性能需求。

⼆分查找也可以实现 O(log2 N) 级别的查找效率，但是⼆分查找有两⼤缺陷：

• 需要存储在⽀持下标随机访问的结构中，并且有序。
• 插⼊和删除数据效率很低，因为存储在下标随机访问的结构中，插⼊和删除数据⼀般需要挪动数据。

5. 完整实现代码

// 二叉搜索树template<class K>struct BSTreeNode {//typedef BSTreeNode Node;BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}BSTreeNode<K>* _left;BSTreeNode<K>* _right;K _key;};template<typename K>class BSTree {typedef BSTreeNode<K> Node;public:BSTree():_root(nullptr){}BSTree(const BSTree<K>& tree):_root(nullptr){_root = Copy(tree._root);}// 现在写法的赋值// t2 = t1BSTree<K>& operator=(BSTree<K> tmp) {std::swap(_root, tmp._root);return *this;}~BSTree() {Destroy(_root);}// 插入时，找到一个空位置插入即可 默认插入的元素不能重复bool insert(const K& key) {// 插入时为空树if (_root == nullptr) {_root = new Node(key);return true;}// 不是空树时Node* parent = nullptr;Node* curNode = _root;while (curNode != nullptr) {if (key > curNode->_key) {parent = curNode;curNode = curNode->_right;}else if (key < curNode->_key) {parent = curNode;curNode = curNode->_left;}else {return false;}}// 走到这里，意味着curNode已经找到了位置,此时curNode为nullptr// parent 为curNode的父节点// curNode 为 结点指针的拷贝，修改curNode不能修改结点指针的指向//走完循环curNode 找到了可以插入的位置// 但要插入结点，必须修改父节点的指针，父节点并不知道key是比自己大还是自己小，只知道下面可以插// 因此要再比较一次curNode = new Node(key);if (key > parent->_key) {parent->_right = curNode;}elseparent->_left = curNode;return true;// key不可能等于parent->_key 否则上面的循环就是错误的/*else {return false;}*/}void Inorder() const {_Inorder(_root);printf(\"\\n\");}bool find(const K& key) const {Node* curNode = _root;while (curNode) {if (key == curNode->_key)return true;else if (key > curNode->_key)curNode = curNode->_right;elsecurNode = curNode->_left;}return false;}// 这里不能用引用代替指针，因为指针可以改变指向，引用一旦绑定，指向不可修改bool erase(const K& key) {Node* parent = nullptr;Node* curNode = _root;// _root为空时，进不去while循环，会直接return false while (curNode) {// 先找要被删除的节点if (key > curNode->_key) {parent = curNode;curNode = curNode->_right;}else if (key < curNode->_key) {parent = curNode;curNode = curNode->_left;}// 找到了，找到了，删除分为三种情况else {// curNode 的左为空if (curNode->_left == nullptr) {// 特殊情况，左为空且curNode 为_rootif (curNode == _root)_root = curNode->_right;// 托孤，需要知道孤儿 应该称为 父节点的左子树还是右子树// 需要先找孤儿在左右那个子树// 孤儿在左子树else if (curNode == parent->_left) {parent->_left = curNode->_right;}// 孤儿在左子树else {parent->_right = curNode->_right;}delete curNode;return true;}// curNode 的右为空else if (curNode->_right == nullptr) {if (curNode == _root)_root = curNode->_left;// 托孤// 当前结点是父的左节点else if (curNode == parent->_left) {parent->_left = curNode->_left;}// 当前结点是父的右节点else {parent->_right = curNode->_left;}delete curNode;return true;}// curNode的左右都不为空，需要在树中找一个结点替换curNodeelse {// 需要找左子树中最大的、或右子树中最小的替换当前结点// 二叉搜索树中，子树的最大结点，是树中最右边的结点//  子树的最小结点，是树中最左边的结点// 这里找左子树中最大的结点Node* maxNode = curNode->_left;Node* maxParent = curNode;// 有可能进不去while循环，对应于删除时的 else 条件// 进不去while时，此时maxNode初始就是左子树的最大结点，parent和curNode重合while (maxNode->_right != nullptr) {maxParent = maxNode;maxNode = maxNode->_right;}// 循环结束后，maxNode为左子树中最大的结点curNode->_key = maxNode->_key;// 替换值// 左子树的最大结点一定没有右孩子，但可能有左孩子// maxNode可能是Parent的右孩子，且maxNode可能有左孩子if (maxNode == maxParent->_right) {maxParent->_right = maxNode->_left;}// maxNode也可能是Parent的左孩子，且maxNode可能有左孩子else { // maxNode是curNode->_left，此时pareng->_left就是maxNodemaxParent->_left = maxNode->_left;}delete maxNode;//Node* maxNode = curNode->_left;//Node* maxParent = curNode;//while (maxNode->_right != nullptr) {//maxParent = maxNode;//maxNode = maxNode->_right;//}// 循环结束后，maxNode为左子树中最大的结点//std::swap(maxNode->_key, curNode->_key);//delete maxNode;//maxParent->_right = nullptr;// 错误逻辑}return true;}}return false;}// find函数的递归版本// 写了一个子函数，因为递归需要用到Private成员_root，来控制递归子树的分支// 如果不写子函数，需要对外提供一个getRoot供调用者使用bool find_R(const K& key) const {return _find_R(_root, key);}bool insert_R(const K& key) {return _insert_R(_root, key);}bool erase_R(const K& key) {return _erase_R(_root, key);}private:Node* Copy(Node* root) {if (root == nullptr)return nullptr;else {Node* newRoot = new Node(root->_key);// 分别递归拷贝 左右子树，拷贝完后，递归回去连接newRoot->_left = Copy(root->_left);newRoot->_right = Copy(root->_right);return newRoot;}}void Destroy(Node*& root) {if (root == nullptr)return;// 二叉树的析构，走后序遍历删除Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}void _Inorder(Node* root = _root) const {if (root == nullptr) {return;}_Inorder(root->_left);cout << root->_key << \" \";_Inorder(root->_right);}bool _find_R(const Node* root, const K& key) const {if (root == nullptr)return false;if (key < root->_key)return _find_R(root->_left, key);else if (key > root->_key)return _find_R(root->_right, key);// 不  表明查找成功elsereturn true;}// 这里参数root加引用，修改指针bool _insert_R(Node*& root, const K& key) {// 走到空的地方，可以开始插入了// 这里可以记录父节点，修改父节点的指针完成插入。不过比较复杂，这里使用if (root == nullptr) {root = new Node(key);return true;}if (key < root->_key)return _insert_R(root->_left, key);else if (key > root->_key)return _insert_R(root->_right, key);elsereturn false;}bool _erase_R(Node*& root, const K& key) {if (root == nullptr)return false;if (key > root->_key)return _erase_R(root->_right, key);else if (key < root->_key)return _erase_R(root->_left, key);// 相等时要删除else {Node* delNode = root;// 这里的 root 等价于 curNode，写成curNode是为了和迭代删除法的形式匹配// 1. curNode 左为空if (root->_left == nullptr) {root = root->_right;}// 2. curNode 右为空else if (root->_right == nullptr) {root = root->_left;}// 3. curNode 左右都不为空else {// 找左子树中最大的结点Node* maxNode = root->_left;while (maxNode->_right) {maxNode = maxNode->_right;}std::swap(maxNode->_key, root->_key);// 交换过后，原来的maxNode是左子树中最大的结点，因此其右子树一定为空// 再去左子树中删除一遍return _erase_R(root->_left, key);//return _erase_R(maxNode, key);// 不能这么写}delete delNode;return true;}}private:Node* _root;};

6. 结语

通过本文的实现，我们完整梳理了二叉搜索树的设计与核心操作：

• 从结点与树的架构设计入手，逐步实现了 构造/析构、拷贝与赋值；
• 结合 迭代与递归 两种思路，详细探讨了 插入、查找、中序遍历、删除 的实现细节与关键陷阱；
• 最后分析了二叉搜索树在不同情况下的性能表现，并指出了其在退化时的效率瓶颈。

二叉搜索树作为最基础的树形数据结构，是理解 AVL 树、红黑树等平衡二叉树 的起点。掌握 BST 的实现，不仅能加深对 STL 底层的理解，也能为后续学习更复杂的数据结构打下坚实的基础。

以上就是本文的所有内容了，如果觉得文章对你有帮助，欢迎 点赞⭐收藏 支持！如有疑问或建议，请在评论区留言交流，我们一起进步

分享到此结束啦
一键三连，好运连连！

你的每一次互动，都是对作者最大的鼓励！

---

征程尚未结束，让我们在广阔的世界里继续前行！ 🚀