文章目录

前言💎一、二叉搜索树的概念💎二、二叉搜索树的操作💍2.1 查找（Search）💍2.2 插入（Insert）💍2.3 删除（Delete）2.3.1 示例：2.3.2 步骤（后继节点）：2.3.3 具体过程（后继节点）：总结：

💎三、二叉搜索树的实现💍3.1 结点类（BSTreeNode）💍3.2 二叉搜索树类（BinarySearchTree）3.2.1 框架3.2.2 插入（Insert）3.2.3 查找（Find）3.2.4 递归中序遍历（InOrder）3.2.5 删除（Erase）3.2.6 析构函数（~BSTree）3.2.7 拷贝构造函数（）3.2.8 赋值运算符重载

💎四、二叉搜索树的应用💍4.1 K模型💍4.2 KV模型4.2.1 KV模型全部代码

结语

前言

在计算机科学领域，二叉搜索树（Binary Search Tree, BST）是一种基础且重要的数据结构。它以其独特的性质——左子树所有节点的值小于根节点，右子树所有节点的值大于根节点——为基础，实现了高效的查找、插入和删除操作。C++作为一种高效、灵活的编程语言，为二叉搜索树的实现提供了强大的支持。

本文旨在详细介绍如何在C++中构建和操作二叉搜索树。我们将从二叉搜索树的基本概念出发，逐步深入到其实现细节，包括节点的定义、树的构建、查找、插入和删除操作等。通过本文的学习，读者将能够掌握二叉搜索树的核心原理，并能够在C++中熟练地实现和操作这种数据结构。

💎一、二叉搜索树的概念

二叉搜索树（Binary Search Tree，简称 BST）是一种特殊的二叉树数据结构，具有以下特点：

节点结构：每个节点包含三个部分：键值（key）、左子节点（left child）、右子节点（right child）。左子树性质：对于每个节点，其左子树上的所有节点的值都小于该节点的值。右子树性质：对于每个节点，其右子树上的所有节点的值都大于该节点的值。递归定义：二叉搜索树中的每个子树也是二叉搜索树。

注意：空树也是一个二叉搜索树。

💎二、二叉搜索树的操作

💍2.1 查找（Search）

查找操作用于在二叉搜索树中查找某个特定的值。查找过程是基于树的有序性规则：每个节点的左子树节点值小于当前节点，右子树节点值大于当前节点。

从根节点开始：

如果查找值等于当前节点的值，则查找成功，返回该节点。如果查找值小于当前节点的值，进入左子树继续查找。如果查找值大于当前节点的值，进入右子树继续查找。如果在遍历中遇到空节点，表示该值不存在于树中。

时间复杂度：

最坏情况：O(n)（树退化为链表时）。平均情况：O(log n)（当树接近平衡时）。

💍2.2 插入（Insert）

插入操作在二叉搜索树中加入一个新节点，并且保证树的结构依旧符合二叉搜索树的特性。

插入时，从根节点开始：

如果插入值小于当前节点值，进入左子树。如果左子树为空，则将新值插入到左子树位置；如果不为空，则递归进入左子树继续查找插入位置。如果插入值大于当前节点值，进入右子树。如果右子树为空，则将新值插入到右子树位置；否则递归进入右子树查找位置。

插入操作不会改变树的其他结构，只会影响插入路径上的节点。

时间复杂度：

最坏情况：O(n)（树退化为链表时）。平均情况：O(log n)（当树接近平衡时）。

💍2.3 删除（Delete）

删除操作比查找和插入稍微复杂，因为需要处理几种不同的情况。

删除节点时有以下三种情况：

被删除节点是叶子节点：直接删除该节点即可，不影响树的其他结构。被删除节点有一个子节点：将该节点的唯一子节点提升为其位置。也就是说，用其子节点替换它。被删除节点有两个子节点：需要找到被删除节点的后继节点（即右子树中的最小节点）或者前驱节点（即左子树中的最大节点），用它来替换被删除节点的值。然后再递归删除后继节点或前驱节点，以保持二叉搜索树的结构。

删除操作通过局部调整树的结构，维持了二叉搜索树的有序性。

时间复杂度：

最坏情况：O(n)（树退化为链表时）。平均情况：O(log n)（当树接近平衡时）。

2.3.1 示例：

删除具有两个子节点的节点（如节点 <code>10）时，通常的步骤如下：

2.3.2 步骤（后继节点）：

找到后继节点：对于有两个子节点的节点，通常选择该节点右子树中的最小节点作为后继节点。在你的例子中，节点 16 是 10 的右子节点，接着我们继续寻找 16 的左子节点，最终找到的是 16 的左子节点最小值节点——16 本身没有左子节点，所以 16 是后继节点。替换被删除节点的值：用后继节点（16）的值替换被删除节点 10 的值。删除后继节点：由于后继节点已经移到 10 的位置，接着我们要递归删除后继节点原来的位置（16）。如果后继节点有子节点，那么需要将这些子节点重新连接。

2.3.3 具体过程（后继节点）：

第一步：选择节点 16 作为 10 的替代者（也就是后继节点）。第二步：将节点 16 移动到节点 10 的位置，当前节点 16 在其右子树继续保持不变。第三步：接着你发现节点 16 的左子节点是空的，所以可以直接删除原位置的 16。

总结：

删除具有两个子节点的节点时，后继节点是被删除节点的右子树中最小的节点。将后继节点值替换被删除节点的值，并删除原来后继节点的位置，保持树的结构。

💎三、二叉搜索树的实现

二插搜索树只是一种结构，它本质上是由一个个结点链接而成，因此我们首先需要定义一个结点类，这个结点用来存储数据。有了结点类之后就需要定义一个二叉搜索树的类，这个类主要是用来维护结构的，实现增删查改等功能，因为它是维护结构的，因此这个类里面的成员变量只需要一个根节点即可，有了这个根节点就能对整个数的结构进行维护管理。

💍3.1 结点类（BSTreeNode）

template<class K>

struct BSTreeNode {

BSTreeNode<K>* left;// 左孩子结点

BSTreeNode<K>* right;// 右孩子结点

K _key;// 关键值

BSTreeNode(const K& key)

:left(nullptr)

,right(nullptr)

,_key(key)

{}

}

💍3.2 二叉搜索树类（BinarySearchTree）

3.2.1 框架

template <class K>

class BSTree

{

typedef BSTreeNode<K> Node;

public:

BSTree()

:_root(nullptr)

{}

// 成员函数...

private:

Node* _root;

};

3.2.2 插入（Insert）

非递归实现

bool Insert(const K& key) {

// 如果树为空，则将新节点作为根节点插入

if (!_root) {

_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; // 如果插入值已存在，返回 false

}

}

// 此时，cur 为 nullptr，parent 为最后访问的非空节点

cur = new Node(key); // 创建新节点

// 判断将新节点插入到父节点的左子树还是右子树

if (parent->_key < key) {

parent->right = cur; // 插入到父节点的右子树

}

else {

parent->left = cur; // 插入到父节点的左子树

}

return true; // 插入成功

}

非递归实现

使用了递归来插入节点。这种方式避免了手动管理父节点和当前节点的指针，逻辑更加简洁。

public:

// 对外暴露的插入接口，调用递归的私有插入函数

bool Insert(const K& key) {

// 调用私有的递归插入函数，从根节点开始递归插入

return _Insert(_root, key);

}

private:

// 私有的递归插入函数

// root：当前递归到的节点，key：要插入的值

bool _Insert(Node*& root, const K& key) {

// 递归的基本情况：当前子树为空，直接在此位置插入新节点

if (!root) {

root = new Node(key); // 创建新节点并插入

return true; // 插入成功

}

// 如果插入值大于当前节点的值，则递归进入右子树

if (root->_key < key) {

return _Insert(root->right, key);

}

// 如果插入值小于当前节点的值，则递归进入左子树

else if (root->_key > key) {

return _Insert(root->left, key);

}

// 如果值相等，表示节点已经存在，返回 false 表示插入失败

else {

return false;

}

}

解释 Node*& root

Node*& root 是 指针的引用，它允许我们在函数中直接修改传入的指针本身，而不仅仅是修改指针指向的对象。这种方式确保了当我们在递归过程中插入新节点时，父节点的指针会被正确更新。

Node*：指向 Node 对象的指针。也就是表示一个树节点的地址。

&：引用符号，表示我们传递的是这个指针本身的引用，而不是它指向的对象的引用。

为什么使用 Node*&？

在递归插入过程中，我们需要更新树的结构。特别是在树的某个位置插入一个新节点时，需要修改父节点的 left 或 right 指针。如果我们只是传递 Node*，在函数内部对该指针的修改不会影响外部（即不会修改父节点的子指针）。使用 Node*& 可以确保对指针的修改被反映到上一层调用中。

实际操作流程：

当你递归调用 _Insert 时，当前子树的根节点通过 Node*& root 传入。如果到达 nullptr，创建一个新节点，并通过 root = new Node(key) 将新节点的指针赋值给当前递归层中的 root。由于 root 是一个指针的引用，所以修改了它之后，父节点的 left 或 right 指针会正确指向新节点。

3.2.3 查找（Find）

非递归形式

bool Find(const K& key) {

Node* cur = _root; // 从根节点开始查找

// 使用 while 循环遍历树

while (cur) {

// 如果当前节点的键值小于目标值，进入右子树查找

if (cur->_key < key) {

cur = cur->right;

}

// 如果当前节点的键值大于目标值，进入左子树查找

else if (cur->_key > key) {

cur = cur->left;

}

// 如果当前节点的键值等于目标值，查找成功，返回 true

else {

return true;

}

}

// 如果遍历完树都没有找到目标值，返回 false

return false;

}

递归形式

public:

// 对外的接口，启动递归查找操作

bool Find(const K& key) {

return _Find(_root, key);

}

private:

// 递归查找函数

bool _Find(Node* root, const K& key) {

// 基本情况：如果当前节点为空，表示没找到，返回 false

if (!root) return false;

// 如果当前节点的值小于目标值，则递归查找右子树

if (root->_key < key) {

return _Find(root->right, key);

}

// 如果当前节点的值大于目标值，则递归查找左子树

else if (root->_key > key) {

return _Find(root->left, key);

}

// 如果当前节点的值等于目标值，说明找到了，返回 true

else {

return true;

}

}

3.2.4 递归中序遍历（InOrder）

public:

void InOrder(){

_InOrder(_root);

cout << endl;

}

private:

void _InOrder(Node* root) const {

if (!root) return;

_InOrder(root->left);

cout << root->_key << " ";

_InOrder(root->right);

}

这里的中序遍历用的是递归的方式来实现的，但是递归函数一定是需要一个参数的，要中序遍历整个二叉树，用户一定是要把根节点 _root 传给这个函数，但是根节点 _root 是私有的成员变量，用户是访问不到的，因此我们不能直接提供中序遍历函数给用户。正确的做法是，虽然用户访问不到根结点，但是类里面可以访问呀，所以我们可以在类里面实现一个中序遍历的子函数 _InOrder，在这个子函数中实现中序遍历的逻辑，然后我们再去给用户提供一个中序遍历的函数接口 InOrder，由它去调用 _InOrder。这样以来用户就可以正常去使用中序遍历啦。

3.2.5 删除（Erase）

非递归形式

// 定义一个函数，用于删除二叉搜索树中的指定键值，返回是否成功删除

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) {

if (cur == _root) { // 如果当前节点是根节点

_root = cur->right; // 让右子树成为新的根节点

}

else { // 否则，根据当前节点是父节点的左孩子还是右孩子来更新父节点的子节点

if (parent->right == cur)

parent->right = cur->right;

else

parent->left = cur->right;

}

}

// 右子树为空的情况

else if (!cur->right) {

if (cur == _root) { // 如果当前节点是根节点

// 注意这里应该是 _root = cur->left; 而不是 _root = cur->right;

_root = cur->left; // 让左子树成为新的根节点

}

else { // 否则，根据当前节点是父节点的左孩子还是右孩子来更新父节点的子节点

if (parent->right == cur)

parent->right = cur->left;

else

parent->left = cur->left;

}

}

// 左右子树都不为空的情况

else {

// 找到左子树中的最大节点（即左子树的最右节点）

Node* leftmax_parent = cur;

Node* leftmax = cur->left;

while (leftmax->right) {

leftmax_parent = leftmax;

leftmax = leftmax->right;

}

// 将左子树的最大节点的键值替换为要删除的节点的键值

swap(cur->_key, leftmax->_key);

// 删除左子树中的最大节点（此时它已经移动到了要删除节点的位置）

if (leftmax_parent->left == leftmax) {

leftmax_parent->left = leftmax->left;

}

else {

leftmax_parent->right = leftmax->left; // 注意这里应该是leftmax的左子节点，因为leftmax没有右子节点

}

// 注意：此时cur已经指向了被替换的节点（即左子树中的最大节点），但这个节点现在是要被删除的节点

// 因此，下面的delete操作实际上删除的是左子树中的最大节点（其键值已被替换到原要删除的节点上）

// 理论上，我们不需要再次对cur进行操作，因为cur的键值已经被替换，并且其物理位置（即内存地址）将在下面的delete中被释放

// 但为了代码的清晰性和一致性，这里保留cur = leftmax;虽然在实际执行到delete前，cur的值已经不再重要

cur = leftmax;

}

delete cur; // 释放要删除节点的内存

return true; // 返回删除成功

}

}

return false; // 如果没有找到要删除的键值，返回删除失败

}

递归形式

public:

// 公共接口，用于从二叉搜索树中删除指定键值的节点

bool Erase(const K& key) {

return _Erase(_root, key); // 调用私有递归函数来执行删除操作

}

private:

// 私有递归函数，用于从以root为根的子树中删除指定键值的节点

bool _Erase(Node*& root, const K& key) {

if (!root) { // 如果当前节点为空，说明键值不存在于树中

return false; // 返回删除失败

}

if (root->_key < key) { // 如果当前节点的键值小于要删除的键值

return _Erase(root->right, key); // 在右子树中继续查找并删除

}

else if (root->_key > key) { // 如果当前节点的键值大于要删除的键值

return _Erase(root->left, key); // 在左子树中继续查找并删除

}

else { // 找到了要删除的节点

Node* del = root; // 保存要删除的节点

// 1. 左子树为空，用右子树替换当前节点

if (!root->left) {

root = root->right; // 右子树成为新的子树根节点

}

// 2. 右子树为空，用左子树替换当前节点

else if (!root->right) {

root = root->left; // 左子树成为新的子树根节点

}

// 3. 左右子树都不为空，找到左子树中的最大节点（或右子树中的最小节点）

// 并将其键值替换到当前节点，然后删除那个最大（或最小）节点

else {

Node* leftmax = root->left; // 从左子树开始查找最大节点

while (leftmax->right) { // 找到左子树中最右边的节点

leftmax = leftmax->right;

}

// 交换当前节点和左子树中最大节点的键值

swap(root->_key, leftmax->_key);

return _Erase(root->left, key);

}

delete del;

return true;

}

}

3.2.6 析构函数（~BSTree）

// BSTree类的公有析构函数

public:

~BSTree() {

// 调用私有辅助函数Destroy来递归地销毁整棵树

Destroy(_root);

}

// BSTree类的私有辅助函数，用于递归地销毁整棵树

private:

void Destroy(Node*& root) {

// 如果当前节点为空，则直接返回，不执行任何操作

if (!root) return;

// 递归地销毁左子树

Destroy(root->left);

// 递归地销毁右子树

Destroy(root->right);

// 删除当前节点，并释放其占用的内存

delete root;

}

3.2.7 拷贝构造函数（）

// BSTree类的公有拷贝构造函数

// 它接受一个同类型的常量引用作为参数，用于初始化新创建的对象

public:

BSTree(const BSTree<K>& t) {

// 调用私有辅助函数Copy来递归地复制源树的所有节点

_root = Copy(t._root);

}

// BSTree类的私有辅助函数，用于递归地复制整棵树

private:

Node* Copy(Node* root) {

// 如果当前节点为空，则返回nullptr，表示该子树不需要复制

if (!root) return nullptr;

// 为当前节点创建一个新的副本，并复制其键值

Node* copyroot = new Node(root->_key);

// 递归地复制左子树，并将复制后的根节点指针赋给新节点的左子节点指针

copyroot->left = Copy(root->left);

// 递归地复制右子树，并将复制后的根节点指针赋给新节点的右子节点指针

copyroot->right = Copy(root->right);

// 返回新创建的节点的指针，作为当前子树的根节点

return copyroot;

}

关于拷贝构造函数的几点说明：

深拷贝：这个拷贝构造函数实现的是深拷贝，即它不仅复制了源树的节点结构，还为每个节点分配了新的内存空间，并复制了节点的值。这样，新创建的树和源树在内存中是完全独立的。递归实现：拷贝过程是通过递归来实现的。对于每个节点，都创建一个新的节点副本，并递归地复制其左子树和右子树。性能：由于需要为每个节点分配新的内存并复制其值，因此拷贝构造函数的性能可能较低，特别是对于大型树来说。然而，这是确保新树和源树在内存中独立所必需的。异常安全性：在实际应用中，如果new Node(root->_key)或递归调用Copy时发生异常，可能会导致内存泄漏。因此，在实际的拷贝构造函数实现中，可能需要使用智能指针（如std::unique_ptr或std::shared_ptr）来自动管理内存，或者添加适当的异常处理代码来确保在发生异常时能够正确地释放已分配的内存。不过，在提供的代码片段中并没有包含异常处理逻辑。构造函数初始化列表：虽然在这个特定的例子中，直接在构造函数体内调用Copy函数是可行的，但在某些情况下，使用构造函数初始化列表来初始化成员变量可能更高效或更简洁。然而，由于Copy函数返回的是一个指针，而不是一个可以直接在初始化列表中使用的值，因此在这个例子中不能使用构造函数初始化列表。

3.2.8 赋值运算符重载

BSTree<K>& operator=(BSTree<K> t) {

swap(_root, t._root);

return *this;

}

💎四、二叉搜索树的应用

💍4.1 K模型

定义：K模型即只有key作为关键码，结构中只需存储key即可，关键码即为需要搜索到的值。应用场景：当只需要判断某个key值是否存在时，可以使用K模型。例如，给出一个单词word，判断该单词是否拼写正确，可以构建一个包含所有正确单词的二叉搜索树，然后在这个树中检索该单词是否存在。特点：K模型的二叉搜索树中，每个节点只包含一个键值（key），节点之间通过左右指针相连，形成一棵二叉树。查找、插入和删除操作都是基于键值来进行的。

以上所有的代码全都是关于二叉搜索树K模型的。

💍4.2 KV模型

定义：KV模型即每一个关键码key都有与之对应的值Value，即<Key, Value>的键值对。应用场景：当需要存储和查找键值对时，可以使用KV模型。例如，英汉词典就是英文与中文的对应关系，通过英文可以快速找到与其对应的中文，英文单词与其对应的中文<word, chinese>就构成一种键值对。特点：KV模型的二叉搜索树中，每个节点包含一个键值（key）和一个对应的值（value），节点之间同样通过左右指针相连。查找、插入和删除操作都是基于键值来进行的，但在操作完成后可以返回或修改对应的值

4.2.1 KV模型全部代码

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()

:_root(nullptr)

{ }

// 递归插入

bool Insert(const K& key, const V& value) {

return _Insert(_root, key, value);

}

// 递归查找

Node* Find(const K& key) {

return _Find(_root, key);

}

// 递归调用删除

bool Erase(const K& key) {

return _Erase(_root, key);

}

// 递归调用中序遍历

void InOrder() {

_InOrder(_root);

cout << endl;

}

private:

bool _Erase(Node*& root, const K& key) {

if (!root) return false;

if (root->_key < key) return _Erase(root->right, key);

else if (root->_key > key) return _Erase(root->left, key);

else {

Node* del = root;

// 1.左为空

if (!root->left) root = root->right;

// 2.右为空

else if (!root->right) root = root->left;

// 3.左右都不为空

else {

Node* leftmax = root->left;

while (leftmax->right) {

leftmax = leftmax->right;

}

swap(root->_key, leftmax->_key);

return _Erase(root->left, key);

}

delete del;

return true;

}

}

bool _Insert(Node*& root, const K& key, const V& value) {

if (!root) {

root = new Node(key, value);

return true;

}

if (root->_key < key) return _Insert(root->right, key, value);

else if (root->_key > key) return _Insert(root->left, key, value);

else return false;

}

Node* _Find(Node* root, const K& key) {

if (!root) return nullptr;

if (root->_key < key) return _Find(root->right, key);

else if (root->_key > key) return _Find(root->left, key);

else return root;

}

void _InOrder(Node* root) {

if (!root) return;

_InOrder(root->left);

cout << root->_key << ":" << root->_value << " ";

_InOrder(root->right);

}

private:

Node* _root;

};

void TestBSTree1() {

BSTree<string, string> dict;

dict.Insert("insert", "插入");

dict.Insert("sort", "排序");

dict.Insert("right", "右边");

dict.Insert("date", "日期");

string str;

while (cin >> str){

BSTreeNode<string, string>* ret = dict.Find(str);

if (ret){

cout << ret->_value << endl;

}

else{

cout << "无此单词" << endl;

}

}

}

void TestBSTree2() {

// 统计水果出现的次数

string arr[] = { "西瓜", "西瓜", "苹果", "西瓜", "苹果", "苹果", "西瓜", "苹果", "香蕉", "苹果", "香蕉" };

BSTree<string, int> countTree;

for (auto& str : arr) {

auto ret = countTree.Find(str);

if (!ret) countTree.Insert(str, 1);

else ret->_value++;

}

countTree.InOrder();

}

}

结语

通过本文的学习，我们深入了解了C++中二叉搜索树的构建与操作方法。从节点的定义到树的构建，再到查找、插入和删除等核心操作，每一步都充满了挑战与收获。二叉搜索树不仅是我们学习数据结构的重要一环，更是解决实际问题时的一种有力工具。

今天的分享到这里就结束啦！如果觉得文章还不错的话，可以三连支持一下，17的主页还有很多有趣的文章，欢迎小伙伴们前去点评，您的支持就是17前进的动力！