【数据结构】二叉搜索树（二叉排序树）
【数据结构】二叉搜索树（二叉排序树）
前言
之前，我们学习了树这一数据结构，并尝试实现了堆以及链式二叉树的相关功能：
【数据结构】树型结构详解 + 堆的实现（c语言）（附源码）_树形结构 编译器-CSDN博客 【数据结构】二叉树（c语言）（附源码）_二叉树数据结构代码-CSDN博客
今天，我们将在简单二叉树的基础上，进一步学习一种更为复杂的结构——二叉搜索树。
之前我们利用c语言实现了顺序表、链表、二叉树等数据结构。但是在实现一些复杂数据结构时，c语言显得相对繁琐，并且容易出现代码冗余的问题。由于我们现在已经具备了一定的c++代码基础，因此在之后的数据结构学习中，我们将用c++实现。
正文开始
一、什么是二叉搜索树
二叉搜索树（Binary Search Tree），也叫二叉排序树或者二叉查找树， 是一种特殊的二叉树结构。它或者是一棵空树，或者具有以下特点：
1. 如果根节点的左子树不为空，则左子树上的所有节点都小于等于根节点的值。 2. 如果根节点的右子树不为空，则右子树上的所有节点都大于等于根节点的值。 3. 它的每一棵子树也都符合前两点特性（每棵子树也都是二叉搜索树）。
简单地说，二叉搜索树是一棵中序遍历结果有序的二叉树。
一般情况下，二叉搜索树不允许有相同的值出现。当然，你在设计二叉搜索树的时候也可以允许相同值出现，只要满足二叉搜索树的特性即可。注意：二叉搜索树不一定是一棵完全二叉树。
二、二叉搜索树的实现
接下来，我们尝试实现二叉搜索树的结构及其常用方法。
节点
首先是它的节点的结构。二叉搜索树的节点包含一个数据域和指向两孩子的指针：
//节点
template<class K>
struct BSTNode
{
K _key;//数据域
BSTNode<K>* _left;//指向左孩子的指针
BSTNode<K>* _right;//指向右孩子的指针
//节点构造
BSTNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
};可以看到，节点的定义当中，模板参数被命名为"K"。这里的"K"通常表示键（key）的类型，特别应用于key_value（键值对，可以理解为一个二元组，每一个key都有对应的value）的场景。一般情况下，key的值是不允许修改的，但是其对应的value可以修改。本次实现二叉搜索树的过程当中，我们仅实现带有key的结构，至于key_value结构，会在之后的AVL树和红黑树中实现。
属性和接口的声明
接下来是二叉搜索树类的成员变量和成员函数的声明：
//二叉搜索树
template<class K>
class BST
{
typedef BSTNode<K> Node;//重命名，简化代码
public:
//强制生成无参构造
BST() = default;
//拷贝构造
BST(const BST<K>& t);
//析构
~BST();
//插入
bool Insert(const K& key);
//删除
bool Erase(const K& key);
//查找
Node* Find(const K& key);
//中序遍历
void Inorder();
private:
Node* _root = nullptr;//根节点的指针
};插入
现在我们开始实现二叉搜索树节点的插入。为了保持搜索树的特性，有如下插入步骤：
1. 如果树为空，则直接将新节点赋值给根节点的指针。 2. 如果树不为空，则需要根据新节点的值进行搜索，如果某节点的值大于新节点，则向右走；若小于新节点，则向左走。走到空位置之后，按照值插入节点即可。 3. 如果要插入重复的值，则遇到相同值的节点之后可以向左走，也可以向右走，直到找到空位置插入。（我们的实现默认不支持插入重复值）
代码实现：
//插入
bool Insert(const K& key)
{
if (_root == nullptr)//树为空，直接插入
{
_root = new Node(key);
return true;
}
else//树不为空，进行搜索
{
Node* cur = _root;//从根节点开始搜索
Node* parent = nullptr;//记录cur的父亲节点
while (cur)//走到空为止
{
if (key < cur->_key)//值小向左走
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)//值大向右走
{
parent = cur;
cur = cur->_right;
}
else//这里不允许重复的值插入
{
return false;
}
}
//此时cur走到空，进行插入
cur = new Node(key);
if (key < parent->_key)//值小，往左边插
{
parent->_left = cur;
}
else//值大，往右边插
{
parent->_right = cur;
}
return true;
}
}这里我们定义了一个parent指针，用于记录cur的父亲节点。当cur走到空时，parent刚好指向插入位置的父亲节点，然后与parent值进行大小比较，插入新节点。
查找
二叉搜索树的特性使其具备了较高的查找效率。查找步骤如下：
1. 从根节点开始，与要查找的值进行比较，如果要找的值比根小，则向左走，否则向右走。循环往复。 2. 如果走到空，则说明不存在，返回空指针。 3. 如果不支持插入重复值，找到后返回节点地址。 4. 如果支持插入重复值，则找到后一般返回中序遍历结果的第一个节点。
代码实现：
//查找
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;
}删除
删除节点是所有接口中实现难度最大的一个。我们默认需要按值来删除元素，所以要先进行查找，找到之后再删除该节点。删除节点之后，为了保持二叉搜索树的原有特性，就需要调整其他节点。根据被删除的节点，有四种情况需要分析讨论：
1. 被删除节点的左右孩子均为空
2. 被删除的节点只有左孩子
3. 被删除的节点只有右孩子
4. 被删除的节点既有左孩子，又有右孩子
这里说明一下寻找右子树最小值的方法：从右孩子开始，一直访问其左孩子节点，直到访问到空为止。这里访问到的最后一个节点即是右子树的最小值。（左子树最大值也同理）
接下来，我们尝试实现删除节点的操作：
//删除
bool Erase(const K& key)
{
//首先按值查找要被删除的节点
Node* cur = _root;
Node* parent = nullptr;//记录父亲节点
while (cur)
{
if (key < cur->_key)//值小向左走
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)//值大向右走
{
parent = cur;
cur = cur->_right;
}
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;//删除该节点
return true;
}
//有一个右孩子的情况
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;//删除该节点
return true;
}
//有两个孩子的情况
else
{
//首先寻找右子树的最小值
Node* rightMin = cur->_right;//从右孩子开始搜索
Node* rightMinParent = cur;//记录最小值的父亲节点
while (rightMin->_left)//left走到空，rightMin即为右子树的最小值
{
rightMinParent = rightMin;
rightMin = rightMin->_left;//一直向左走，找最小值
}
//将最小值赋值给被删除节点
cur->_key = rightMin->_key;
//将替代节点的右孩子托付给父亲
//先判断自己是父亲节点的哪一个孩子
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;//删除该节点
return true;
}
}
}
//没找到，返回false
return false;
}这里有两点需要注意：
1. 第一种情况可以和第二/第三种情况合并，将空指针托付给父亲节点不会影响整体操作。 2. 第四种情况当中，如果我们找的是右子树的最小值，那么它或是叶子节点（第一种情况），或只有右孩子（第三种情况），不会有左孩子；如果我们找的是左子树的最大值，那么它或是叶子节点（第一种情况），或只有左孩子（第二种情况），不会有右孩子。所以代码中可以非常确定托付哪一个孩子。
拷贝构造
接下来我们实现拷贝构造。该接口比较简单，直接递归拷贝即可。代码如下：
//拷贝构造
BST(const BST<K>& t)
{
_root = _Copy(t._root);
}
Node* _Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
Node* newRoot = new Node(root->_key);//创建新的根节点
newRoot->_left = _Copy(root->_left);//拷贝左子树
newRoot->_right = _Copy(root->_right);//拷贝右子树
return newRoot;//返回根节点
}析构
与拷贝构造相同，析构时递归释放每一个节点。代码如下：
//析构
~BST()
{
_Destroy(_root);
}
void _Destroy(Node* root)
{
if (root == nullptr)
{
return;
}
_Destroy(root->_left);//销毁左子树
_Destroy(root->_right);//销毁右子树
delete root;//删除根节点
}中序遍历
由于二叉搜索树的中序遍历结果是有序的，所以我们来实现一个中序遍历接口。中序遍历的代码与传统的二叉树完全相同。
实现如下：
//中序遍历
void Inorder()
{
_Inorder(_root);
cout << endl;
}
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);//遍历左子树
cout << root->_key << ' ';//访问根节点
_Inorder(root->_right);//遍历右子树
}最后，我们来使用一下我们实现的二叉搜索树：
int main()
{
BST<int> t;
int a[] = { 8, 3, 1, 10, 6, 4, 7, 14, 13 };
for (auto& e : a)//循环插入
{
t.Insert(e);
t.Inorder();
}
cout << endl;
for (auto& e : a)//循环删除
{
t.Erase(e);
t.Inorder();
}
return 0;
}运行结果：
程序全部代码
二叉搜索树的全部实现代码如下：
#include <iostream>
using namespace std;
//节点
template<class K>
struct BSTNode
{
K _key;//数据域
BSTNode<K>* _left;//指向左孩子的指针
BSTNode<K>* _right;//指向右孩子的指针
//节点构造
BSTNode(const K& key)
:_key(key)
, _left(nullptr)
, _right(nullptr)
{}
};
//二叉搜索树
template<class K>
class BST
{
typedef BSTNode<K> Node;//重命名，简化代码
public:
//强制生成无参构造
BST() = default;
//拷贝构造
BST(const BST<K>& t)
{
_root = _Copy(t._root);
}
//析构
~BST()
{
_Destroy(_root);
}
//插入
bool Insert(const K& key)
{
if (_root == nullptr)//树为空，直接插入
{
_root = new Node(key);
return true;
}
else//树不为空，进行搜索
{
Node* cur = _root;//从根节点开始搜索
Node* parent = nullptr;//记录cur的父亲节点
while (cur)//走到空为止
{
if (key < cur->_key)//值小向左走
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)//值大向右走
{
parent = cur;
cur = cur->_right;
}
else//这里不允许重复的值插入
{
return false;
}
}
//此时cur走到空，进行插入
cur = new Node(key);
if (key < parent->_key)//值小，往左边插
{
parent->_left = cur;
}
else//值大，往右边插
{
parent->_right = cur;
}
return true;
}
}
//删除
bool Erase(const K& key)
{
//首先按值查找要被删除的节点
Node* cur = _root;
Node* parent = nullptr;//记录父亲节点
while (cur)
{
if (key < cur->_key)//值小向左走
{
parent = cur;
cur = cur->_left;
}
else if (key > cur->_key)//值大向右走
{
parent = cur;
cur = cur->_right;
}
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;//删除该节点
return true;
}
//有一个右孩子的情况
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;//删除该节点
return true;
}
//有两个孩子的情况
else
{
//首先寻找右子树的最小值
Node* rightMin = cur->_right;//从右孩子开始搜索
Node* rightMinParent = cur;//记录最小值的父亲节点
while (rightMin->_left)//left走到空，rightMin即为右子树的最小值
{
rightMinParent = rightMin;
rightMin = rightMin->_left;//一直向左走，找最小值
}
//将最小值赋值给被删除节点
cur->_key = rightMin->_key;
//将替代节点的右孩子托付给父亲
//先判断自己是父亲节点的哪一个孩子
if (rightMin == rightMinParent->_left)
rightMinParent->_left = rightMin->_right;
else
rightMinParent->_right = rightMin->_right;
delete rightMin;//删除该节点
return true;
}
}
}
//没找到，返回false
return false;
}
//查找
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;
}
//中序遍历
void Inorder()
{
_Inorder(_root);
cout << endl;
}
private:
Node* _Copy(Node* root)
{
if (root == nullptr)
{
return nullptr;
}
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;//删除根节点
}
void _Inorder(Node* root)
{
if (root == nullptr)
{
return;
}
_Inorder(root->_left);//遍历左子树
cout << root->_key << ' ';//访问根节点
_Inorder(root->_right);//遍历右子树
}
Node* _root = nullptr;//根节点的指针
};三、二叉搜索树的性能分析
接下来，我们简单分析一下二叉搜索树的性能。
设二叉树的节点数为N：
在较好情况下，二叉搜索树接近于完全二叉树的状态，它的高度为log₂N；
在极端情况下，二叉搜索树是单支树的状态，高度为N。
综合而言， 二叉搜索树增、删、改的时间复杂度为O(N)。
在较好情况下，其增删改的效率可接近于O(logN)，但是它的效率受高度影响较大。所以传统的二叉搜索树显然不满足我们高效查找的需求。之后我们会学习自平衡的二叉搜索树（如AVL树、红黑树），它们会尽量降低二叉搜索树的高度，提高效率。
总结
今天我们学习了一种特殊的二叉树结构--二叉搜索树，它的特性使其具备了较好的查找效率。掌握二叉搜索树的知识，将为我们后续学习STL中的set和map容器打下坚实的基础。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤
腾讯云开发者
