【深入C++】二叉搜索树

文章目录

什么是二叉搜索树

二叉搜索树（Binary Search Tree, BST）是一种特殊的二叉树，其每个节点最多有两个子节点，分别称为左子节点和右子节点。BST具有以下性质：

1. 左子树的所有节点值都小于根节点的值：即对于每一个节点，其左子树上所有节点的值都比该节点的值小。
2. 右子树的所有节点值都大于根节点的值：即对于每一个节点，其右子树上所有节点的值都比该节点的值大。
3. 每个子树也是二叉搜索树：这意味着BST的定义在每个节点的子树上都成立。

形如下面这棵树就是一颗二叉搜索树：

8
     /   \310
   / \\1614
     / \     /
    4713

二叉搜索树的接口

要写二叉搜索树的接口，我们先得定义一颗二叉搜索树：

定义二叉搜索树的节点：

template<classK>structBSTreeNode{
    K _key;
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;BSTreeNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}};

定义二叉搜索树：

template<classK>classBSTree{typedef BSTreeNode<K> Node;public:private:
    Node* _root =nullptr;};

1.查找操作

由于二叉搜索树的性质，所以这里我们可以直接用while循环来查找，不需要进行递归来查找：

boolFind(const K& key){
    Node* cur = _root;while(cur){//小于当前节点，在左子树if(cur->_key > key)cur = cur->_left;//大于当前节点，在右子树elseif(cur->_key < key) cur = cur->_right;//等于当前节点，返回trueelsereturntrue;}returnfalse;}

2.插入操作

插入操作我们只需要找到插入的位置，然后插入节点即可，如果没有找到，则返回false，如果找到了并成功插入了，则返回true。

boolInsert(const K& key){//没有根节点的情况if(_root ==nullptr){
        _root =newNode(key);returntrue;}//遍历节点
    Node* cur = _root;//记录当前节点的父节点
    Node* parent =nullptr;while(cur){
        parent = cur;if(cur->_key > key)cur = cur->_left;elseif(cur->_key < key) cur = cur->_right;elsereturnfalse;}//找到插入的地方，直接new
    cur =newNode(key);//判断插入到父节点的左节点还是右节点if(parent->_key < key) parent->_right = cur;else parent->_left = cur;returntrue;}

3.中序遍历

对于中序遍历，我们需要写一个辅助函数，来传递当前this指针对应的root。

voidInOrder(){_InOrder(_root);}void_InOrder(Node* root){if(root ==nullptr)return;_InOrder(root->_left);
    cout << root->_key <<' ';_InOrder(root->_right);}

4.删除操作

插入操作分三种情况：

我们拿下面这个二叉搜索树为例子：

将节点进行归类：

我们先讨论删除没有孩子的节点，对于没有孩子的节点我们可以直接进行删除。
其次，我们来讨论删除一个孩子的节点，假如我们删除14，我们需要知道14的父亲，将10和14的左孩子串起来。

可以将一个孩子的节点归结为这几种情况。
接下来就是有两个孩子的节点：

我们拿3这个节点为例子：

删除3节点，我们应该用左子树最大，或者右子树最小进行替换，然后转化成删除左子树最大，或者右子树最小的节点，就相当于把删除有两个孩子的节点转换成删除一个孩子的节点或者没有孩子的节点。

boolErase(const K& key){//三种情况：//1.一个孩子//2.没有孩子//3.两个孩子：左子树的最大，右子树的最小//左子树的最左，右子树的最右
    Node* cur = _root;
    Node* parent =nullptr;while(cur){if(cur->_key > key){
            parent = cur;
            cur = cur->_left;}elseif(cur->_key < key){
            parent = cur;
            cur = cur->_right;}else{//删除//0-1个孩子的情况if(cur->_left ==nullptr){//删除根节点的情况if(parent ==nullptr)_root = cur->_right;else{if(parent->_left == cur) parent->_left = cur->_right;else parent->_right = cur->_right;}delete cur;returntrue;}elseif(cur->_right ==nullptr){//删除根节点if(parent ==nullptr) _root = cur->_left;else{if(parent->_left == cur)parent->_left = cur->_left;else parent->_left = cur->_left;}delete cur;returntrue;}//两个孩子的情况else{//找右子树最小的节点作为最大的节点
                Node* rightminp =nullptr;
                Node* rightmin = cur->_right;//left不为空就一直向left走while(rightmin->_left !=nullptr){
                    rightminp = rightmin;
                    rightmin = rightmin->_left;}
                cur->_key = rightmin->_key;if(rightminp !=nullptr) rightminp->_left = rightmin->_right;else cur->_right = rightmin->_right;delete rightmin;returntrue;}}}returnfalse;}

删除成功返回true，删除失败没找到则返回false。

所有代码

#pragmaonce#include<iostream>usingnamespace std;template<classK>structBSTreeNode{
    K _key;
    BSTreeNode<K>* _left;
    BSTreeNode<K>* _right;BSTreeNode(const K& key):_key(key),_left(nullptr),_right(nullptr){}};template<classK>classBSTree{typedef BSTreeNode<K> Node;public:boolInsert(const K& key){if(_root ==nullptr){
            _root =newNode(key);returntrue;}
        Node* cur = _root;
        Node* parent =nullptr;while(cur){
            parent = cur;if(cur->_key > key)cur = cur->_left;elseif(cur->_key < key) cur = cur->_right;elsereturnfalse;}
        cur =newNode(key);if(parent->_key < key) parent->_right = cur;else parent->_left = cur;returntrue;}boolFind(const K& key){
        Node* cur = _root;while(cur){if(cur->_key > key)cur = cur->_left;elseif(cur->_key < key) cur = cur->_right;elsereturntrue;}returnfalse;}boolErase(const K& key){//三种情况：//1.一个孩子//2.没有孩子//3.两个孩子：左子树的最大，右子树的最小//左子树的最左，右子树的最右
        Node* cur = _root;
        Node* parent =nullptr;while(cur){if(cur->_key > key){
                parent = cur;
                cur = cur->_left;}elseif(cur->_key < key){
                parent = cur;
                cur = cur->_right;}else{//删除//0-1个孩子的情况if(cur->_left ==nullptr){//删除根节点的情况if(parent ==nullptr)_root = cur->_right;else{if(parent->_left == cur) parent->_left = cur->_right;else parent->_right = cur->_right;}delete cur;returntrue;}elseif(cur->_right ==nullptr){//删除根节点if(parent ==nullptr) _root = cur->_left;else{if(parent->_left == cur)parent->_left = cur->_left;else parent->_left = cur->_left;}delete cur;returntrue;}//两个孩子的情况else{//找右子树最小的节点作为最大的节点
                    Node* rightminp =nullptr;
                    Node* rightmin = cur->_right;//left不为空就一直向left走while(rightmin->_left !=nullptr){
                        rightminp = rightmin;
                        rightmin = rightmin->_left;}
                    cur->_key = rightmin->_key;if(rightminp !=nullptr) rightminp->_left = rightmin->_right;else cur->_right = rightmin->_right;delete rightmin;returntrue;}}}returnfalse;}voidInOrder(){_InOrder(_root);}private:void_InOrder(Node* root){if(root ==nullptr)return;_InOrder(root->_left);
        cout << root->_key <<' ';_InOrder(root->_right);}
    Node* _root =nullptr;};

总结

二叉搜索树（BST）是一种在计算机科学中广泛应用的数据结构，具有高效的查找、插入和删除操作。通过遵循节点值的有序性规则，BST能够在平均情况下实现对数时间复杂度的操作，使其成为处理动态数据集的理想选择。

在本篇博客中，我们详细介绍了二叉搜索树的定义和性质，并通过示例展示了其基本结构。我们还探讨了BST的三大主要操作：插入、查找和删除，并分析了这些操作的实现方法和时间复杂度。

尽管二叉搜索树在平衡状态下具有高效的性能，但在最坏情况下，BST可能会退化成链表。因此，在实际应用中，经常需要采用自平衡二叉搜索树（如AVL树和红黑树）来保证其性能。

通过对BST的深入理解和实践，相信你能够在各种编程场景中灵活运用这一重要的数据结构，从而提高程序的效率和性能。如果你对二叉搜索树有任何疑问或希望了解更多高级应用，欢迎在评论区留言讨论。