前言

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

今天，我们将在简单二叉树的基础上，进一步学习一种更为复杂的结构——二叉搜索树。

之前我们利用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容器打下坚实的基础。如果你觉得博主讲的还不错，就请留下一个小小的赞在走哦，感谢大家的支持❤❤❤

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

前言

一、什么是二叉搜索树

二、二叉搜索树的实现

节点

属性和接口的声明

插入

查找

删除

拷贝构造

析构

中序遍历

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

热门文章

最新文章

相关课程

相关电子书

探索云世界

热门

云计算

大数据

云原生

人工智能

数据库

开发与运维

活动广场

任务中心

训练营

直播

乘风者计划

下载

镜像站

技术资料

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

前言

一、什么是二叉搜索树

二、二叉搜索树的实现

节点

属性和接口的声明

插入

查找

删除

拷贝构造

析构

中序遍历

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

热门文章

最新文章

相关课程

相关电子书