探索数据结构：二叉搜索树的递归与非递归实现

✨✨ 欢迎大家来到贝蒂大讲堂✨✨

🎈🎈养成好习惯，先赞后看哦~🎈🎈

所属专栏：数据结构与算法
贝蒂的主页：Betty’s blog

1. 二叉搜索树的介绍

二插入搜索树（Binary Search Tree，简称 BST)，也叫做二叉排序树。它一种常见的运用于查找的数据结构。

它具有以下重要特点：

1. 每个节点最多有两个子节点，分别称为左子节点和右子节点。
2. 若左子树不为空，左子树中的所有节点的值都小于根节点的值。
3. 若右子树不为空，右子树中的所有节点的值都大于根节点的值。
4. 左右子树也都是二叉搜索树。

其中需要特别注意的是空树也是一颗二叉搜索树。而由于其性质，所以二叉搜索树在进行中序遍历就能对数据进行升序排序。

这种结构使得在其中进行查找、插入和删除操作具有较高的效率。例如，如果要查找一个特定的值，从根节点开始，如果要查找的值小于根节点的值，就向左子树查找；如果大于根节点的值，就向右子树查找。一直重复这个过程，直到找到目标值或者确定目标值不存在。

在插入操作时，也是通过比较要插入的值与当前节点的值，决定将其插入到左子树还是右子树。

删除操作则相对复杂一些，需要根据被删除节点的子节点情况进行不同的处理。

并且二叉入搜索树在很多领域都有广泛应用，比如数据库中的索引结构、文件系统的目录结构等。它能够有效地提高数据的存储和检索效率。

2. 二叉搜索树的功能

以下是二叉搜索树的常见功能：

1. 二叉搜索树的插入。
2. 二叉搜索树的查找。
3. 二叉搜索树的删除。

3. 二叉搜索树的结构

3.1. 二叉搜索树的节点

二叉搜索树的节点本质与二叉树一样，所以有三个成员变量：左子树_left，右子树_right，键值_val。当然为了适配不同的类型，我们可以定义一个模版.。

template<class K>
struct BSTreeNode
{//构造函数BSTreeNode(const K&key):_left(nullptr),_right(nullptr),_key(key){}BSTreeNode<K>* _left;//左子树BSTreeNode<K>* _right;// 右子树K _key;// 键值
};

3.2. 二叉搜索树

而我们在定义二叉搜索树时就可以利用这个节点，并初始化为空。

template<class K>
class BSTree
{typedef BSTreeNode<K> Node;
public://成员函数
private://成员变量Node* _root = nullptr;
};

4. 二叉搜索树的初始化与销毁

4.1. 构造函数/拷贝构造/赋值重载

首先我们直接定义一个无参的构造函数，因为我们在定义拷贝构造之后编译器就不会在生成默认的构造函数了。

BSTree()
{}

之后我们可以利用递归来实现一个拷贝构造函数。

BSTree(const BSTree& t)
{_root = copy(t._root);
}
Node* copy(Node* root)
{if (root == nullptr)return nullptr;Node* newnode = new Node(root->_key);newnode->_left = copy(root->_left);newnode->_right = copy(root->_right);return root;
}

最后我们通过一个简单的方式实现赋值重载——通过形参调用拷贝构造出一个临时变量，然后交换this所指向的变量，这样原本this所指向的对象出了作用域就会销毁，间接实现了实现赋值重载。

BSTree<K>& operator=(const BSTree<K> t)
{//赋值重载this->swap(_root, t._root);return *this;
}

4.2. 析构函数

析构函数需要借助递归释放所有节点，而为了方便我们传参我们可以定义子函数来帮助我们解决。

~BSTree()
{Destory(_root);
}
void Destroy(Node*&root)
{if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;
}

5. 二叉搜索树的插入

二叉搜索树的插入十分简单，从根节点开始，如果要查找的值小于根节点的值，就向左子树查找；如果大于根节点的值，就向右子树查找，一直重复这个过程。

在查找过程中可能出现两种情况：

1. 查找到空节点即要插入位置，插入成功返回true。
2. 查找到相同值的节点，插入失败返回false。

5.1. 非递归实现

非递归实现首先得保存父节点parent，方便之后插入新的节点。然后循环查找插入位置，查找失败就返回false，查找成功则判断该插入parent的左边还是右边。

bool Insert(const K& key)
{if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;//保存父节点方便插入Node* cur = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{//相同值返回falsereturn false;}}//插入cur = new Node(key);//判断该插入哪边if (key < parent->_key){parent->_left = cur;}else{parent->_right = cur;}return true;
}

5.2. 递归实现

递归实现的大逻辑与非递归实现时一样的，当key<root->_key就往左子树插入，当key > root->_key就往左子树插入。其中需要注意的是为了传参方便我们定义一个子函数来实现递归，并且利用引用传参减少拷贝并直接对原二叉搜索树进行修改。

bool InsertR(const K& key)
{return _InsertR(_root, key);
}
bool _InsertR(Node* &root, const K& key)
{//插入if (root == nullptr){root = new Node(key);return true;}if (key < root->_key){return _InsertR(root->_left, key);}else if (key > root->_key){return _InsertR(root->_right, key);}else{//相同返回falsereturn false;}
}

6. 二叉搜索树的查找

二叉搜索树的查找也十分简单，从根节点开始，如果要查找的值小于根节点的值，就向左子树查找；如果大于根节点的值，就向右子树查找，一直重复这个过程。

在查找过程中可能出现两种情况：

1. 查找到空节点，查找失败返回false。
2. 查找到相同值的节点，查找成功返回true。

6.1. 非递归实现

仔细观察我们就发现查找的逻辑其实就是插入的子逻辑，因为插入的前提就是查找，所以实现也更简单。

bool Find(const K& key)
{Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return true;}}//找到空return false;
}

6.2. 递归实现

bool FindR(const K& key)
{return _FindR(_root, key);
}
bool _FindR(Node* root, const K& key)
{if (root == nullptr){return false;}if (key < root->_key){return _FindR(root->_left, key);//左子树找}else if (key > root->_key){return _FindR(root->_right, key);}else{return true;//找到了}
}

7. 二叉搜索树的删除

二叉搜索树的删除的逻辑是最麻烦的，首先我们定义一个parent节点方便之后链接。然后通过具体情况分析：

主要可以分为以下几种情况：

1. 删除节点的左子树为空，位于父节点的右子树。

2. 删除节点的左子树为空，位于父节点的左子树。

3. 删除节点的右子树为空，位于父节点的右子树。

4. 删除节点的右子树为空，位于父节点的左子树。

5. 删除节点为根节点，并且左或右子树为空。

6. 删除节点左右子树都不为空。

当删除节点左右子树都不为空时，需采用伪删除法。即寻找到左子树的最右节点即左子树的最大值，或者是右子树的最左节点即右子树的最小值。然后赋值，最后转换为在左子树或者右子树删除节点。

当然删除节点时需要判断，其位于父节点的左子树还是右子树。

7.1. 非递归实现

bool Erase(const K& key)
{Node* parent = nullptr;Node* cur = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{//1.左为空if (cur->_left == nullptr){//判断是否删除的是根节点if (cur == _root){_root = cur->_right;}else{//判断cur为parent左子树还是右子树if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;cur = nullptr;}//2.右为空else if (cur->_right == nullptr){//判断是不是为根节点if (cur == _root){_root = cur->_left;}//判断cur为parent左子树还是右子树else{if (cur == parent->_left)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;cur = nullptr;}else//左右都不为空{//选择右子树的最左节点替换Node* pminRight = cur;Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;//判断删除节点位于父节点哪一侧if (pminRight->_left == minRight){pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;minRight = nullptr;}return true;}}//找不到直接返回falsereturn false;
}

7.2. 递归实现

递归实现采用引用传参，这时root就是parent左子树或者右子树的地址。当删除节点的左子树为空时，我们直接将右子树赋值给root，如果右子树为空，我们直接将左子树赋给root。当左右子树都不为空时，我们可以采用伪删除法将问题转换为在左子树或右子树删除某个叶子节点，从而实现递归调用。当然我们需要提前保存要删除节点，防止更新之后找不到。

bool EraseR(const K& key)
{return _EraseR(_root, key);
}
bool _EraseR(Node*& root, const K& key)
{if (root == nullptr){return false;}if (key < root->_key){return _EraseR(root->_left, key);}else if (key > root->_key){return _EraseR(root->_right, key);}//找到删除节点else{//提前保存Node* del = root;//引用传参直接修改if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{//找到左边的最右节点Node* maxLeft = root->_left;while (maxLeft->_right){maxLeft = maxLeft->_right;}swap(maxLeft->_key, root->_key);//递归在左子树删除return _EraseR(root->_left, key);}delete del;return true;}
}

8. 判断是否为二叉搜索树

为了验证我们最后生成的二叉树是二叉搜索树，我们无法通过肉眼观察，所以最好直接写一个函数判断。

通过二叉搜索树的定义，我们可以设计一个递归函数 _isValidBST(root, lower, upper) 来递归判断，函数表示考虑以 root为根的子树，判断子树中所有节点的值是否都在 (lower，upper) 的开区间范围内，即是否都小于左节点，大于右节点。如果 root节点的值_key 不在(lower，upper) 的范围内说明不满足条件直接返回，否则我们要继续递归调用检查它的左右子树是否满足，如果都满足才说明这是一棵二叉搜索树。

bool isValidBST(Node* root)
{return _isValidBST(root, LONG_MIN, LONG_MAX);
}
bool _isValidBST(Node* root, long long lower, long long upper)
{if (root == nullptr){return true;}if (root->_key <= lower || root->_key >= upper){return false;}bool left = _isValidBST(root->_left, lower, root->_key);bool right = _isValidBST(root->_right, root->_key, upper);return left && right;
}

9. 二叉搜索树的性能分析

二叉搜索树的插入与删除本质都先查找，所以查找代表了二叉搜索树的操作的性能。当二叉搜索树接近完全二叉树时，时间复杂度就为O(logN)。

但是当二叉搜索树接近有序插入时，二叉搜索树就会退化为单链表，这是时间复杂度为O(N)。

而二叉搜索树的各个操作都不会开辟大量空间，所以空间复杂度为O(1)。

10. 二叉搜索树的应用

10.1. K模型

K模型即只有_key作为关键码，结构中只存储Key，关键码即为需要搜索的值。比如需要判断某个单词是否拼写正确，首先我们将词库中所有单词集合里的每个单词作为关键码（key）来构建一棵二叉搜索树。然后，在这棵二叉搜索树中检索给定的单词是否存在。如果存在，就表明该单词拼写正确；如果不存在，就表明拼写错误。

我们上述实现的二叉搜索树就是基于K模型实现的。

10.2. KV模型

KV模型即每一个关键码_key，都有与之对应的值_Value，即结构中存储<Key, Value>的键值对。比如需要通过电话号码找到对应的联系人，这时就可以存储<tele_num，name>的键值对。然后将所有集合构建一颗二叉搜索树，之后就能在这课二叉搜索树中通过电话号码查找对应的联系人。

而实现KV模型也十分简单，只需要将节点BSTreeNode增加一个参数val，引入第二次模版参数V，然后根据实际情况修改一下即可。

11. 源码

11.1. K模型

namespace K
{template<class K>struct BSTreeNode{//构造函数BSTreeNode(const K& key):_left(nullptr), _right(nullptr), _key(key){}BSTreeNode<K>* _left;//左子树BSTreeNode<K>* _right;// 右子树K _key;// 键值};template<class K>class BSTree{typedef BSTreeNode<K> Node;public://成员函数BSTree(){}BSTree(const BSTree& t){_root = copy(t._root);}BSTree<K>& operator=(const BSTree<K> t){//赋值重载swap(_root, t._root);return *this;}bool Insert(const K& key){if (_root == nullptr){_root = new Node(key);return true;}Node* parent = nullptr;//保存父节点方便插入Node* cur = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{//相同值返回falsereturn false;}}//插入cur = new Node(key);if (key < parent->_key){//左子树parent->_left = cur;}else{parent->_right = cur;}return true;}bool Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return true;}}//找到空return false;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{//1.左为空if (cur->_left == nullptr){//判断是否删除的是根节点if (cur == _root){_root = cur->_right;}else{//判断cur为parent左子树还是右子树if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;cur = nullptr;}//2.右为空else if (cur->_right == nullptr){//判断是不是为根节点if (cur == _root){_root = cur->_left;}//判断cur为parent左子树还是右子树else{if (cur == parent->_left)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;cur = nullptr;}else//左右都不为空{//选则右子树的最左节点替换Node* pminRight = cur;Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;//判断最左节点是右子树的根节点还是右子树的最左节点if (pminRight->_left == minRight){pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;minRight = nullptr;}return true;}}//找不到直接返回falsereturn false;}bool isValidBST(Node* root){return _isValidBST(root, LONG_MIN, LONG_MAX);}bool FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key){return _InsertR(_root, key);}bool EraseR(const K& key){return _EraseR(_root, key);}~BSTree(){Destroy(_root);}private:bool _isValidBST(Node* root, long long lower, long long upper){if (root == nullptr){return true;}if (root->_key <= lower || root->_key >= upper){return false;}bool left = _isValidBST(root->_left, lower, root->_key);bool right = _isValidBST(root->_right, root->_key, upper);return left && right;}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}if (key < root->_key){return _EraseR(root->_left, key);}else if (key > root->_key){return _EraseR(root->_right, key);}//找到删除节点else{//提前保存Node* del = root;//引用传参直接修改if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{//找到左边的最右节点Node* maxLeft = root->_left;while (maxLeft->_right){maxLeft = maxLeft->_right;}swap(maxLeft->_key, root->_key);//递归在左子树删除return _EraseR(root->_left, key);}delete del;return true;}}bool _InsertR(Node*& root, const K& key){//插入if (root == nullptr){root = new Node(key);return true;}if (key < root->_key){return _InsertR(root->_left, key);}else if (key > root->_key){return _InsertR(root->_right, key);}else{//相同返回falsereturn false;}}bool _FindR(Node* root, const K& key){if (root == nullptr){return false;}if (key < root->_key){return _FindR(root->_left, key);//左子树找}else if (key > root->_key){return _FindR(root->_right, key);}else{return true;//找到了}}Node* copy(Node* root){if (root == nullptr)return nullptr;Node* newnode = new Node(root->_key);newnode->_left = copy(root->_left);newnode->_right = copy(root->_right);return newnode;}void Destroy(Node*& root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}//成员变量Node* _root = nullptr;};
}

11.2. KV模型

namespace KV
{template<class K,class V>struct BSTreeNode{//构造函数BSTreeNode(const K& key,const V&val):_left(nullptr), _right(nullptr), _key(key),_val(val){}BSTreeNode<K,V>* _left;//左子树BSTreeNode<K,V>* _right;// 右子树K _key;// 键值V _val;};template<class K,class V>class BSTree{typedef BSTreeNode<K,V> Node;public://成员函数BSTree(){}BSTree(const BSTree<K,V>& t){_root = copy(t._root);}BSTree<K,V>& operator=(const BSTree<K,V> t){//赋值重载swap(_root, t._root);return *this;}bool Insert(const K& key,const V&val){if (_root == nullptr){_root = new Node(key,val);return true;}Node* parent = nullptr;//保存父节点方便插入Node* cur = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{//相同值返回falsereturn false;}}//插入cur = new Node(key,val);if (key < parent->_key){//左子树parent->_left = cur;}else{parent->_right = cur;}return true;}Node* Find(const K& key){Node* cur = _root;while (cur){if (key < cur->_key){cur = cur->_left;}else if (key > cur->_key){cur = cur->_right;}else{return cur;}}//找到空return nullptr;}bool Erase(const K& key){Node* parent = nullptr;Node* cur = _root;while (cur){if (key < cur->_key){parent = cur;cur = cur->_left;}else if (key > cur->_key){parent = cur;cur = cur->_right;}else{//1.左为空if (cur->_left == nullptr){//判断是否删除的是根节点if (cur == _root){_root = cur->_right;}else{//判断cur为parent左子树还是右子树if (cur == parent->_left)parent->_left = cur->_right;elseparent->_right = cur->_right;}delete cur;cur = nullptr;}//2.右为空else if (cur->_right == nullptr){//判断是不是为根节点if (cur == _root){_root = cur->_left;}//判断cur为parent左子树还是右子树else{if (cur == parent->_left)parent->_left = cur->_left;elseparent->_right = cur->_left;}delete cur;cur = nullptr;}else//左右都不为空{//选则右子树的最左节点替换Node* pminRight = cur;Node* minRight = cur->_right;while (minRight->_left){pminRight = minRight;minRight = minRight->_left;}cur->_key = minRight->_key;//判断最左节点是右子树的根节点还是右子树的最左节点if (pminRight->_left == minRight){pminRight->_left = minRight->_right;}else{pminRight->_right = minRight->_right;}delete minRight;minRight = nullptr;}return true;}}//找不到直接返回falsereturn false;}bool isValidBST(Node* root){return _isValidBST(root, LONG_MIN, LONG_MAX);}Node* FindR(const K& key){return _FindR(_root, key);}bool InsertR(const K& key,const V&val){return _InsertR(_root, key, val);}bool EraseR(const K& key){return _EraseR(_root, key);}~BSTree(){Destroy(_root);}private:bool _isValidBST(Node* root, long long lower, long long upper){if (root == nullptr){return true;}if (root->_key <= lower || root->_key >= upper){return false;}bool left = helper(root->_left, lower, root->_key);bool right = helper(root->_right, root->_key, upper);return left && right;}bool _EraseR(Node*& root, const K& key){if (root == nullptr){return false;}if (key < root->_key){return _EraseR(root->_left, key);}else if (key > root->_key){return _EraseR(root->_right, key);}//找到删除节点else{//提前保存Node* del = root;//引用传参直接修改if (root->_left == nullptr){root = root->_right;}else if (root->_right == nullptr){root = root->_left;}else{//找到左边的最右节点Node* maxLeft = root->_left;while (maxLeft->_right){maxLeft = maxLeft->_right;}swap(maxLeft->_key, root->_key);//递归在左子树删除return _EraseR(root->_left, key);}delete del;return true;}}bool _InsertR(Node*& root, const K& key, const V&val){//插入if (root == nullptr){root = new Node(key,val);return true;}if (key < root->_key){return _InsertR(root->_left, key, val);}else if (key > root->_key){return _InsertR(root->_right, key, val);}else{//相同返回falsereturn false;}}Node*_FindR(Node* root, const K& key){if (root == nullptr){return false;}if (key < root->_key){return _FindR(root->_left, key);//左子树找}else if (key > root->_key){return _FindR(root->_right, key);}else{return root;//找到了}}Node* copy(Node* root){if (root == nullptr)return nullptr;Node* newnode = new Node(root->_key,root->_val);newnode->_left = copy(root->_left);newnode->_right = copy(root->_right);return newnode;}void Destroy(Node*& root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}//成员变量Node* _root = nullptr;};
}
;}delete del;return true;}}bool _InsertR(Node*& root, const K& key, const V&val){//插入if (root == nullptr){root = new Node(key,val);return true;}if (key < root->_key){return _InsertR(root->_left, key, val);}else if (key > root->_key){return _InsertR(root->_right, key, val);}else{//相同返回falsereturn false;}}Node*_FindR(Node* root, const K& key){if (root == nullptr){return false;}if (key < root->_key){return _FindR(root->_left, key);//左子树找}else if (key > root->_key){return _FindR(root->_right, key);}else{return root;//找到了}}Node* copy(Node* root){if (root == nullptr)return nullptr;Node* newnode = new Node(root->_key,root->_val);newnode->_left = copy(root->_left);newnode->_right = copy(root->_right);return newnode;}void Destroy(Node*& root){if (root == nullptr){return;}Destroy(root->_left);Destroy(root->_right);delete root;root = nullptr;}//成员变量Node* _root = nullptr;};
}