【数据结构】二叉搜索树（二叉排序树）

目录

前言

一、什么是二叉搜索树

二、二叉搜索树的实现

节点

属性和接口的声明

插入

查找

删除

拷贝构造

析构

中序遍历

三、二叉搜索树的性能分析

总结

前言

        之前，我们学习了树这一数据结构，并尝试实现了堆以及链式二叉树的相关功能：

【数据结构】树型结构详解 + 堆的实现（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;elseparent->_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;elseparent->_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;elserightMinParent->_right = rightMin->_right;delete rightMin;//删除该节点return true;}}}//没找到，返回falsereturn 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;elseparent->_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;elseparent->_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;elserightMinParent->_right = rightMin->_right;delete rightMin;//删除该节点return true;}}}//没找到，返回falsereturn 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容器打下坚实的基础。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤