二分搜索树

经典写法（内心os：就是有点繁琐hh~）

#include <iostream>
#include <queue>
#include <cassert>
using namespace std;

template <typename Key, typename Value>
class BST
{
private:
    struct Node
    {
        Key key;
        Value value;
        Node *left;
        Node *right;

        Node(Key key, Value value)
        {
            this->key = key;
            this->value = value;
            this->left = this->right = NULL;
        }

        Node(Node *node)
        {
            this->key = node->key;
            this->value = node->value;
            this->left = node->left;
            this->right = node->right;
        }
    };

    Node *root;
    int count;

    // 用于判断是否为二叉搜索树的变量
    Node *pre = nullptr;
    bool res = true;

public:
    BST()
    {
        root = NULL;
        count = 0;
    }
    ~BST()
    {
        _destroy(root);
    }

    int size()
    {
        return count;
    }

    bool isEmpty()
    {
        return count == 0;
    }

    void insert(Key key, Value value)
    {
        root = _insert(root, key, value);
    }

    bool contain(Key key)
    {
        return _contain(root, key);
    }

    Value *search(Key key)
    {
        return _search(root, key);
    }

    // 前序遍历
    void preOrder()
    {
        _preOrder(root);
    }

    // 中序遍历
    void inOrder()
    {
        _inOrder(root);
    }

    // 后序遍历
    void postOrder()
    {
        _postOrder(root);
    }

    // 层序遍历
    void levelOrder()
    {
        queue<Node *> q;
        q.push(root);
        while (!q.empty())
        {
            Node *node = q.front();
            q.pop();

            cout << node->key << " ";
            if (node->left)
                q.push(node->left);
            if (node->right)
                q.push(node->right);
        }
    }

    // 寻找最小的键值
    Key minimum()
    {
        assert(count != 0);
        Node *minNode = _minimum(root);
        return minNode->key;
    }

    // 寻找最大的键值
    Key maximum()
    {
        assert(count != 0);
        Node *maxNode = _maximum(root);
        return maxNode->key;
    }

    // 从二叉搜索树中删除最小值所在节点
    void removeMin()
    {
        if (root)
            root = _removeMin(root);
    }

    // 从二叉搜索树中删除最大值所在节点
    void removeMax()
    {
        if (root)
            root = _removeMax(root);
    }

    // 从二叉搜索树中删除键值为key的节点
    void remove(Key key)
    {
        root = _remove(root, key);
    }

    bool isValidBST()
    {
        pre = nullptr;
        res = true;
        if (!root)
            return true;
        _dfs(root);
        return res;
    }

private:
    // 判断中序遍历是否有序
    void _dfs(Node *root)
    {
        if (!root)
            return;
        _dfs(root->left);

        if (pre && pre->key >= root->key)
        {
            res = false;
            return;
        }

        pre = root;
        _dfs(root->right);
    }

    // 向以node为根的二叉搜索树中，插入节点(key, value)
    // 返回插入新节点后的二叉搜索树的根
    Node *_insert(Node *node, Key key, Value value)
    {

        if (node == NULL)
        {
            count++;
            return new Node(key, value);
        }

        if (key == node->key)
            node->value = value;
        else if (key < node->key)
            node->left = _insert(node->left, key, value);
        else // key > node->key
            node->right = _insert(node->right, key, value);

        return node;
    }

    // 查看以node为根的二叉搜索树中是否包含键值为key的节点
    bool _contain(Node *node, Key key)
    {
        if (node == NULL)
            return false;

        if (key == node->key)
            return true;
        else if (key < node->key)
            return _contain(node->left, key);
        else // key > node->key
            return _contain(node->right, key);
    }

    // 在以node为根节点的二叉搜索树中查找key所对应的value
    Value *_search(Node *node, Key key)
    {
        if (node == NULL)
            return NULL;

        if (key == node->key)
            return &(node->value);
        else if (key < node->key)
            return _search(node->left, key);
        else // key > node->key
            return _search(node->right, key);
    }

    // 对以node为根的二叉搜索树进行前序遍历
    void _preOrder(Node *node)
    {
        if (node != NULL)
        {
            cout << node->key << " ";
            _preOrder(node->left);
            _preOrder(node->right);
        }
    }

    // 对以node为根的二叉搜索树进行中序遍历
    void _inOrder(Node *node)
    {
        if (node != NULL)
        {
            _inOrder(node->left);
            cout << node->key << " ";
            _inOrder(node->right);
        }
    }

    // 对以node为根的二叉搜索树进行后序遍历
    void _postOrder(Node *node)
    {
        if (node != NULL)
        {
            _postOrder(node->left);
            _postOrder(node->right);
            cout << node->key << " ";
        }
    }

    void _destroy(Node *node)
    {
        if (node != NULL)
        {
            _destroy(node->left);
            _destroy(node->right);
            delete node;
            count--;
        }
    }

    // 在以node为根的二叉搜索树中，返回最小键值的节点
    Node *_minimum(Node *node)
    {
        if (node->left == NULL)
            return node;
        return _minimum(node->left);
    }

    Node *_maximum(Node *node)
    {
        if (node->right == NULL)
            return node;
        return _maximum(node->right);
    }

    // 删除掉以node为根的二分搜索树中的最小节点
    // 返回删除节点后新的二分搜索树的根
    Node *_removeMin(Node *node)
    {
        if (node->left == NULL)
        {
            Node *rightNode = node->right;
            delete node;
            count--;
            return rightNode;
        }

        node->left = _removeMin(node->left);
        return node;
    }

    // 删除掉以node为根的二分搜索树中的最小节点
    // 返回删除节点后新的二分搜索树的根
    Node *_removeMax(Node *node)
    {
        if (node->right == NULL)
        {
            Node *leftNode = node->left;
            delete node;
            count--;
            return leftNode;
        }

        node->right = _removeMax(node->right);
        return node;
    }

    // 删除以node为根的二分搜索树中键值为key的节点
    // 返回删除节点后的新的二分搜索树的根
    Node *_remove(Node *node, Key key)
    {
        if (node == NULL)
            return NULL;
        if (key < node->key)
        {
            node->left = _remove(node->left, key);
            return node;
        }
        else if (key > node->key)
        {
            node->right = _remove(node->right, key);
            return node;
        }
        else // key == node->key
        {
            if (node->left == NULL)
            {
                Node *rightNode = node->right;
                delete node;
                count--;
                return rightNode;
            }
            if (node->right == NULL)
            {
                Node *leftNode = node->left;
                delete node;
                count--;
                return leftNode;
            }

            // node->left != NULL && node->right != NULL
            Node *successor = new Node(_minimum(node->right));
            count++;

            successor->left = node->left;
            successor->right = _removeMin(node->right);

            delete node;
            count--;

            return successor;
        }
    }
};

void judge(bool flag)
{
    cout << endl;
    if (flag)
        cout << "It is a BSTree" << endl;
    else
        cout << "It is not a BSTree" << endl;
}

int main()
{
    int q[5] = {5, 1, 4, 3, 6};
    BST<int, int> bst = BST<int, int>();
    for (int i = 0; i < 5; ++i)
    {
        bst.insert(q[i], q[i]);
    }

    judge(bst.isValidBST());
    bst.inOrder();

    bst.remove(4);
    judge(bst.isValidBST());
    bst.inOrder();

    return 0;
}

为实现红黑树准备的二叉搜索树版本（比较惊艳，嘿嘿~）

因为红黑树的增加和删除节点操作只不过是在二叉搜索树对应操作的基础上，增加了维护红黑树性质的操作嘛，所以可以在此版本基础上，实现红黑树的操作。红黑树的实现可移步到红黑树的实现（C++）_青衫客36的博客-CSDN博客

#include <iostream>
using namespace std;

//  1  结点定义：bstreeNode
template <class T>
class bstree;

template <class T>
struct _bstTreeNode
{
    friend class bstree<T>;
    T getkey()
    {
        return key;
    }

private:
    T key;
    _bstTreeNode<T> *left;
    _bstTreeNode<T> *right;
    _bstTreeNode<T> *p;
};

//  2  二叉搜索树类声明：bstree
template <class T>
class bstree
{
public:
    bstree()
    {
        root = nullptr;
    }
    void insert(T key);
    _bstTreeNode<T> *search(T key);
    void erase(T key);
    void bstDelete(_bstTreeNode<T> *z);
    void display();
    bool isValidBST();

private:
    // 用于判断是否为二叉搜索树的变量
    _bstTreeNode<T> *pre = nullptr;
    bool res = true;

    void _display(_bstTreeNode<T> *);

    _bstTreeNode<T> *treeSuccessor(_bstTreeNode<T> *);
    void _dfs(_bstTreeNode<T> *);

    _bstTreeNode<T> *root;
};

//  3  二叉搜索树类成员定义
template <class T>
void bstree<T>::insert(T key)
{
    _bstTreeNode<T> *t = new _bstTreeNode<T>; // t为新插入的节点
    t->key = key;
    _bstTreeNode<T> *x = root;
    _bstTreeNode<T> *y = nullptr;
    while (x != nullptr) // 循环结束y指向新节点应挂载的节点
    {
        y = x;
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    t->p = y; // 将新插入的节点t挂在y指向节点上
    if (y == nullptr)
        root = t;
    else // 将新插入的节点t经判断后挂在y的左孩子或右孩子
    {
        if (t->key < y->key)
            y->left = t;
        else
            y->right = t;
    }
    t->left = nullptr;
    t->right = nullptr;
}

template <class T>
bool bstree<T>::isValidBST()
{
    pre = nullptr;
    res = true;
    if (!root)
        return true;
    _dfs(root);
    return res;
}

// 判断中序遍历是否有序
template <class T>
void bstree<T>::_dfs(_bstTreeNode<T> *root)
{
    if (!root)
        return;
    _dfs(root->left);

    if (pre && pre->key >= root->key)
    {
        res = false;
        return;
    }

    pre = root;
    _dfs(root->right);
}

template <class T>
_bstTreeNode<T> *bstree<T>::search(T key)
{
    _bstTreeNode<T> *x = root;
    while (x != nullptr && key != x->key)
    {
        if (key < x->key)
            x = x->left;
        else
            x = x->right;
    }
    return x;
}

template <class T>
void bstree<T>::erase(T key)
{
    _bstTreeNode<T> *x = search(key);
    if (x != nullptr)
        bstDelete(x);
}

template <class T>
_bstTreeNode<T> *bstree<T>::treeSuccessor(_bstTreeNode<T> *x)
{
    x = x->right;
    while (x->left != nullptr)
        x = x->left;
    return x;
}

template <class T>
void bstree<T>::bstDelete(_bstTreeNode<T> *z) // z是逻辑上被删除的节点(实际上他并没有被删除，而是修改了自己的value值为中序后继的值，然后把中序后继节点y删除了)
{
    _bstTreeNode<T> *x;                  // 取代被删除节点位置的节点
    _bstTreeNode<T> *y;                  // 真正删除的节点
    if (z->left == nullptr || z->right == nullptr) // z只有左子树或只有右子树，就直接把子树的根节点提上去
        y = z;
    else
        y = treeSuccessor(z); // z左右子树都有，那么就把z的中序后继提上去
    if (y->left != nullptr)   // 然后准备删除y，类似于链表的删除，将y的子节点挂在y的父节点下(取代y的位置)
        x = y->left;
    else
        x = y->right;
    
    if (x != nullptr)
        x->p = y->p;

    if (y->p == nullptr)
        root = x;
    else
    {
        if (y == y->p->left)
            y->p->left = x;
        else
            y->p->right = x; // 将y的父节点与x进行双向链接
    }
    if (y != z)          // 逻辑上删除的节点与真正删除的节点不是同一个，就把实际上删除的节点的值赋给逻辑上删除的节点，(是同一个节点的话，直接把该节点删了就可以了)
        z->key = y->key; // 将y的值赋给z使之满足二叉搜索树的性质
    delete y;            // 如果删除的节点是红色，直接删除就可以了，不需要调整红黑树
}

template <class T>
void bstree<T>::display()
{
    if (root != nullptr)
        _display(root);
    else
        cout << "Tree is empty! " << endl;
}

template <class T>
void bstree<T>::_display(_bstTreeNode<T> *x)
{
    if (x->left != nullptr)
        _display(x->left);
    if (x != nullptr)
    {
        cout << x->key << " ";
        if (x->p != nullptr)
        {
            cout << "x->p: " << x->p->key << " ";
        }
        if (x->left != nullptr)
        {
            cout << "x->left: " << x->left->key << " ";
        }
        if (x->right != nullptr)
        {
            cout << "x->right: " << x->right->key;
        }
    }
    cout << endl;
    if (x->right != nullptr)
        _display(x->right);
}

void judge(bool flag)
{
    if (flag)
        cout << "It is a BST" << endl;
    else
        cout << "It is not a BST" << endl;
}

//  4  测试程序：main()
// const int N = 12;

// int p[12] = {1, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15};
int p[6] = {41, 38, 31, 12, 19, 8};

int main()
{
    bstree<int> test;
    for (int i = 0; i < 6; ++i)
    {
        test.insert(p[i]);
    }
    test.display();
    judge(test.isValidBST());

    int a;
    while (cin >> a)
    {
        test.erase(a);
        // cout << test.isbstree() << endl;
        test.display();
        judge(test.isValidBST());
    }
    return 0;
}