二叉搜索树完全指南：接口完善与搜索场景实战

目录

一、二叉搜索树接口代码

1.1 交换函数

1.2 中序遍历

1.3 默认构造与拷贝构造

1.4 赋值重载

1.5 析构函数

二、key搜索场景/key-value搜索场景

2.1 key 搜索场景

2.2 key/value 搜索场景

2.3 key/value 搜索场景代码

一、二叉搜索树接口代码

1.1 交换函数

先给大家看一个很实用的小接口，交换函数，代码写起来特别简单：

void swap(SBTree& other) { std::swap(_root, other._root); }

别看这代码只有一行，里面其实藏着两个值得一提的小知识点：

第一个知识点，为什么只交换 _root 就够了？

因为二叉搜索树的所有节点结构都挂在根节点下面，所以交换两个树的根指针，本质上就把两棵树的 “所有权” 给彻底互换了，原来属于 A 树的所有节点，现在全归 B 树管，反之亦然。更妙的是，这么做效率极高，就是 O (1) 的时间复杂度，完全不用去遍历或者复制任何节点。

第二个知识点，std::swap是C++标准库提供的通用交换函数，专门用来安全地交换两个对象的值。

这里用它来交换两个指针，既省去了咱们自己写临时变量中转的麻烦，又能保证代码的简洁和规范。

1.2 中序遍历

接下来是二叉搜索树里特别核心的一个接口，中序遍历。代码分成了两层设计，先看给外部调用的公有接口：

void Inorder() { inorder(_root); cout << endl; }

这个公有函数很省心，外部用的时候不用传任何参数，它内部直接把根节点_root塞给私有的递归函数，等遍历完了还顺手加个换行，让输出结果整整齐齐的。

然后是真正干活的私有递归实现：

void inorder(Node* root) { if (root == nullptr) { return; } inorder(root->left); cout << root->_key << " " << root->_value << endl; inorder(root->right); }

递归逻辑也很直白：先判断当前节点是不是空，是空就直接返回，这是递归的终止条件；然后严格按“左 - 根 - 右”的顺序来：先递归扎进左子树，接着打印当前节点的 _key 和 _value，最后再递归遍历右子树。

这里必须提一个二叉搜索树的关键知识点：二叉搜索树的中序遍历结果一定是升序的。原因很简单，它的规则就是“左小右大”，所以按“左 - 根 - 右”走一遍，刚好把所有节点从小到大排了个序 ，这也是中序遍历最实用的地方，能直接用来验证树的结构有没有乱。

1.3 默认构造与拷贝构造

接下来是两个和对象创建相关的核心接口，默认构造函数和拷贝构造函数，咱们一个个来看。

先看默认构造函数，咱们直接写了SBTree() = default;。

这里藏着个C++11的实用知识点：= default到底是干嘛的？

其实就是明确告诉编译器：“别给我整复杂的，就生成一个最标准的默认构造函数就行”。这么写既省得我们自己写空函数体，又能保证编译器会乖乖把 _root 初始化成 nullptr（毕竟我们在类里给了缺省值），轻轻松松搞定空树的初始化。

然后是拷贝构造函数，当我们想基于一棵现成的树，完完整整 “克隆” 出一棵独立的新树时，就全靠它了：

SBTree(const SBTree& tree) { _root = Copy(tree._root); }

它的逻辑很直白，就是调用私有的Copy函数，把传入的 tree 的根节点塞进去，让 Copy 去递归复制所有节点，最后把新生成的根节点赋给当前树的 _root，这样两棵树就彻底分离开了。

重点来了，这个Copy函数是怎么做到递归复制整棵树的呢？咱们看代码：

Node* Copy(Node* root) { if (root == nullptr) { return nullptr; } Node* newnode = new Node(root->_key, root->_value); newnode->left = Copy(root->left); newnode->right = Copy(root->right); return newnode; }

递归的思路其实很好理解，也是分三步走：

• 第一步，先判断当前节点是不是空，如果是空，直接返回 nullptr—— 这是递归的终止条件，碰到叶子节点的空孩子就立刻停手。
• 第二步，要是当前节点不为空，那就先 new 一个新节点 newnode，把当前节点的 _key 和 _value 都复制过去 —— 这一步相当于 “先把自己复制好”。
• 第三步，接着递归处理左子树和右子树：让 newnode->left 接住 Copy(root->left) 的返回值（也就是复制好的左子树的根），右子树同理。最后把 newnode 返回去，让上一层的节点接住。

这里必须敲黑板提一个关键知识点：为什么要这么费劲地递归复制？直接把根指针赋值过去不行吗？

答案是绝对不行。如果只复制根指针，那两棵树会共享同一片节点内存，你在A树里删了个节点，B树里对应的节点也会凭空消失，这就是危险的 “浅拷贝”。

而我们现在这种逐个节点递归复制的方式，叫“深拷贝”，能保证两棵树完全独立，你改你的、我改我的，互不干扰，这才是安全的拷贝方式。

1.4 赋值重载

最后给大家看一个设计得特别巧妙的接口，赋值重载，代码短得惊人，但里面藏着C++里非常经典的技巧：

SBTree& operator= (const SBTree tree) { swap(tree); return *this; }

别看这代码只有三行，这可是大名鼎鼎的Copy-and-Swap（拷贝并交换）技巧，咱们来拆解一下它的妙处：

首先看参数，这里故意用了值传递而不是引用传递，这是第一个关键点。当你用值传递的时候，编译器会自动调用咱们前面写的拷贝构造函数，帮你生成一个tree的副本，相当于把深拷贝的活儿直接甩给了拷贝构造函数，咱们自己不用再写一遍重复的逻辑。

然后是 swap(tree)：把当前对象的 _root 和这个临时副本的 _root 交换一下。这么一弄，当前对象就顺理成章地拿到了副本里的所有新节点；而副本原来揣着的、当前对象旧的那些节点，会在函数结束的时候，随着临时副本 tree 的析构自动被释放掉 —— 连内存泄漏的问题都一起解决了，简直一举两得。

最后是 return *this：返回当前对象的引用，这是为了支持链式赋值，比如 a = b = c 这种写法，符合 C++ 的常规操作习惯。

这里必须提一下 Copy-and-Swap 的核心知识点：它除了代码简洁之外，还有一个巨大的优点，异常安全。因为深拷贝是在swap之前完成的，如果拷贝构造函数不小心抛了异常，当前对象的状态完全不会被破坏，还是原来的样子，不会出现 “半吊子” 的赋值结果，非常稳健。

1.5 析构函数

最后是负责 “善后” 的核心接口，析构函数，专门用来清理树里的所有节点，避免内存泄漏，代码同样分成了两层：

先看公有的析构函数：

~SBTree() { destory(_root); _root = nullptr; }

它的逻辑很清晰：当树对象的生命周期结束时（比如函数返回、程序退出），会自动调用这个析构函数。它先让私有的 destory 去递归清理所有节点，等清理完了，还顺手把 _root 置为 nullptr—— 这一步是个好习惯，能防止后面有人误操作_root变成野指针。

然后是真正干活的私有递归函数 destory：

void destory(Node* root) { if (root == nullptr) { return; } destory(root->left); destory(root->right); delete(root); }

这里必须敲黑板：它用的是后序遍历，也就是严格的“左 - 右 - 根”顺序。为什么非得这样？

因为如果先删了父节点，那左孩子和右孩子的指针就直接丢了，再也找不到它们，内存就彻底泄漏了。所以得先递归扎进左子树删干净，再递归右子树删干净，最后才能放心地 delete 当前的 root 节点。

这里补充两个关键知识点：第一个，后序遍历是二叉树析构的唯一正确选择。核心原因就是“必须先释放孩子，才能释放父亲”，顺序乱了就会出问题。第二个，析构后置空根指针是个防御性编程的好习惯—— 虽然对象已经要销毁了，置空看起来多此一举，但万一后面有代码不小心访问了旧的_root，置空后至少能快速触发空指针错误，比野指针的随机崩溃好排查多了。

二、key搜索场景/key-value搜索场景

2.1 key 搜索场景

在 key 搜索场景下，我们只把key作为唯一的关键码，树的结构里也只需要存 key 就行。搜索的目标很单纯，就是判断这个 key 在不在树里。这种场景下实现的二叉搜索树，支持增、删、查，但绝对不支持修改 key，因为 key 是维持树结构的核心，一改就把 “左小右大” 的规矩给破坏了。

给大家举两个很常见的 key 搜索场景例子：第一个是小区无人值守车库：物业会把买了车位的业主车牌号录入系统，车辆进小区时扫一下车牌，查一下在不在系统里，在就抬杆，不在就提示非本小区车辆，不让进。第二个是英文单词拼写检查：把词库里所有单词都放进二叉搜索树，然后读取文章里的单词，挨个查在不在树里，不在的话就用波浪线标红提示拼写错误。

2.2 key/value 搜索场景

key/value场景就比纯 key场景多了一层关联：每一个关键码 key，都对应着一个 value，这个value可以是任意类型的对象。所以树的节点里，除了存key，还得存对应的value。增、删、查的逻辑还是以 key 为核心，按二叉搜索树的规矩来，但好处是能通过 key 快速找到它对应的 value。

这种场景下的二叉搜索树，支持修改 value，但依然不支持修改 key——key 一动树结构就乱了，但 value 随便改，不影响结构。

key/value 的场景就更丰富了，比如：第一个是简单的中英互译字典：节点里存 key（英文）和 value（中文），搜索时输入英文，就能直接找到对应的中文释义。第二个是商场无人值守车库：入口扫车牌，把车牌（key）和入场时间（value）存进树里；出口再扫车牌，找到对应的入场时间，用当前时间一减算出停车时长，再算停车费，缴完费就抬杆放行。第三个是统计文章单词词频：读一个单词，先查在不在树里，不在就说明是第一次出现，存进去（单词，1）；要是已经存在，就把对应的次数 ++ 就行。

2.3 key/value 搜索场景代码

我之前带着大家写的是纯 key 搜索场景的代码，key/value 场景的代码其实不用大改，只要在原来的基础上稍作调整就行。

namespace key_value{ template <class K, class V> class SBTnode{ public: K _key;V _value; SBTnode<K, V>* left; SBTnode<K, V>* right; SBTnode(const K& key, const V& value) :_key(key) , _value(value) , left(nullptr) , right(nullptr) {} }; template <class K, class V> class SBTree{ using Node = SBTnode<K, V>; public: void swap(SBTree& other){std::swap(_root, other._root);} void Inorder(){ inorder(_root); cout << endl; } void inorder(Node* root){ if (root == nullptr) return; inorder(root->left); cout << root->_key << " " << root->_value << endl; inorder(root->right); } SBTree() = default; SBTree(const SBTree& tree){_root = Copy(tree._root);} Node* Copy(Node* root){ if (root == nullptr) return nullptr; Node* newnode = new Node(root->_key, root->_value); newnode->left = Copy(root->left); newnode->right = Copy(root->right); return newnode; } SBTree& operator= (const SBTree tree){ swap(tree); return *this; } ~SBTree(){ destory(_root); _root = nullptr; } void destory(Node* root){ if (root == nullptr) return; destory(root->left); destory(root->right); delete(root); } 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 Insert(const K& key, const V& value){ Node* cur = _root; Node* parent = nullptr; if (_root == nullptr){ _root = new Node(key, value); return true; } 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->left = cur; else if (parent->_key < key) parent->right = cur; return true; } 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 (parent->left == cur) parent->left = cur->right; else if (parent->right == cur) parent->right = cur->right; } } else if (cur->right == nullptr){ if (cur == _root) _root = cur->left; else{ if (parent->left == cur) parent->left = cur->left; else if (parent->right == cur) parent->right = cur->left; } } 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 if (replaceparent->right == replace) replaceparent->right = replace->right; cur = replace; } delete (cur); return true; } } return false; } protected: Node* _root=nullptr; }; }