介绍

二叉查找树(Binary Search Tree)，又被称为二叉搜索树。 它是特殊的二叉树：对于二叉树，假设x为二叉树中的任意一个结点，x节点包含关键字key，节点x的key值记为key[x]。如果y是x的左子树中的一个结点，则key[y] <= key[x]；如果y是x的右子树的一个结点，则key[y] >= key[x]。那么，这棵树就是二叉查找树.

具体讲解见 https://www.cnblogs.com/skywang12345/p/3576373.html

需要注意的是插入删除

这里说一下链表实现。

#pragma once
#include <iostream>
#include <iomanip>

using namespace std;
template <typename T>
class BSTNode {
public:
    T key;
    BSTNode* parent = nullptr;
    BSTNode* left = nullptr;
    BSTNode* right = nullptr;
    BSTNode(T value) : key(value) {}
    ~BSTNode() {
        cout << "delete : " << key << endl;
    }
};

template <typename T>
class BSTTree {
public:
    BSTTree();
    ~BSTTree();

    // 三序遍历
    void preOrder();
    void inOrder();
    void postOrder();

    // (递归实现)查找"二叉树"中键值为key的节点
    BSTNode<T>* search(T key);
    // (非递归实现)查找"二叉树"中键值为key的节点
    BSTNode<T>* iterativeSearch(T key);
    // 查找最小结点：返回最小结点的键值。
    T minimum();
    // 查找最大结点：返回最大结点的键值。
    T maximum();

    // 找结点(x)的后继结点。即，查找"二叉树中数据值大于该结点"的"最小结点"。
    BSTNode<T>* successor(BSTNode<T>* x);
    // 找结点(x)的前驱结点。即，查找"二叉树中数据值小于该结点"的"最大结点"。
    BSTNode<T>* predecessor(BSTNode<T>* x);

    // 将结点(key为节点键值)插入到二叉树中
    void insert(T key);

    // 删除结点(key为节点键值)
    void remove(T key);

    // 销毁二叉树
    void destroy();

    // 打印二叉树
    void print();
    
private:
    // 前序遍历"二叉树"
    void preOrder(BSTNode<T>* tree) const;
    // 中序遍历"二叉树"
    void inOrder(BSTNode<T>* tree) const;
    // 后序遍历"二叉树"
    void postOrder(BSTNode<T>* tree) const;

    // (递归实现)查找"二叉树x"中键值为key的节点
    BSTNode<T>* search(BSTNode<T>* x, T key) const;
    // (非递归实现)查找"二叉树x"中键值为key的节点
    BSTNode<T>* iterativeSearch(BSTNode<T>* x, T key) const;

    // 查找最小结点：返回tree为根结点的二叉树的最小结点。
    BSTNode<T>* minimum(BSTNode<T>* tree);
    // 查找最大结点：返回tree为根结点的二叉树的最大结点。
    BSTNode<T>* maximum(BSTNode<T>* tree);
    // 将结点(z)插入到二叉树(tree)中
    void insert(BSTNode<T>*& tree, BSTNode<T>* z);
    // 删除二叉树(tree)中的结点(z)，并返回被删除的结点
    BSTNode<T>* remove(BSTNode<T>*& tree, BSTNode<T>* z);
    // 销毁二叉树
    void destroy(BSTNode<T>*& tree);
    // 打印二叉树
    void print(BSTNode<T>* tree, T key, int direction);

    BSTNode<T>* mRoot = nullptr;
};

template<typename T>
inline BSTTree<T>::BSTTree()
{
}

template<typename T>
inline BSTTree<T>::~BSTTree()
{
    destroy();
}

template<typename T>
inline void BSTTree<T>::insert(T value)
{
    BSTNode<T>* node = new BSTNode<T>(value);
    if (node == nullptr) {
        return;
    }
    insert(mRoot, node);
}

template<typename T>
inline void BSTTree<T>::remove(T key)
{
    BSTNode<T>* z;
    BSTNode<T>* node;
    z = search(mRoot, key);
    if (z) {
        node = remove(mRoot, z);
        if (node) {
            delete node;
        }
    }
}

template<typename T>
inline void BSTTree<T>::destroy()
{
    if (mRoot) {
        destroy(mRoot);
    }
}

template<typename T>
inline void BSTTree<T>::print()
{
    if (mRoot) {
        print(mRoot, mRoot->key, 0);
    }
}

template<typename T>
inline void BSTTree<T>::preOrder(BSTNode<T>* tree) const
{
    if (tree) {
        cout << tree->key << " ";
        preOrder(tree->left);
        preOrder(tree->right);
    }
}

template<typename T>
inline void BSTTree<T>::inOrder(BSTNode<T>* tree) const
{
    if (tree) {
        inOrder(tree->left);
        cout << tree->key << " ";
        inOrder(tree->right);
    }
}

template<typename T>
inline void BSTTree<T>::postOrder(BSTNode<T>* tree) const
{
    if (tree) {
        postOrder(tree->left);
        postOrder(tree->right);
        cout << tree->key << " ";
    }
}

template<typename T>
inline void BSTTree<T>::preOrder()
{
    preOrder(mRoot);
    cout << endl;
}

template<typename T>
inline void BSTTree<T>::inOrder()
{
    inOrder(mRoot);
    cout << endl;
}

template<typename T>
inline void BSTTree<T>::postOrder()
{
    postOrder(mRoot);
    cout << endl;
}

template<typename T>
inline BSTNode<T>* BSTTree<T>::search(T key)
{
    return search(mRoot, key);
}

template<typename T>
inline BSTNode<T>* BSTTree<T>::iterativeSearch(T key)
{
    return iterativeSearch(mRoot, key);
}

template<typename T>
inline BSTNode<T>* BSTTree<T>::search(BSTNode<T>* x, T key) const
{
    if (x == nullptr || x->key == key) {
        return x;
    }
    if (key < x->key) {
        return search(x->left, key);
    }
    else {
        return search(x->right, key);
    }
}

template<typename T>
inline BSTNode<T>* BSTTree<T>::iterativeSearch(BSTNode<T>* x, T key) const
{
    while (x != nullptr && x->key != key) {
        if (key < x->key) {
            x = x->left;
        }
        else {
            x = x->right;
        }
    }
    return x;
}

template<typename T>
inline BSTNode<T>* BSTTree<T>::minimum(BSTNode<T>* tree)
{
    if (tree == nullptr) {
        return nullptr;
    }
    while (tree->left) {
        tree = tree->left;
    }
    return tree;
}

template<typename T>
inline BSTNode<T>* BSTTree<T>::maximum(BSTNode<T>* tree)
{
    if (tree == nullptr) {
        return nullptr;
    }
    while (tree->right) {
        tree = tree->right;
    }
    return tree;
}

template<typename T>
inline void BSTTree<T>::insert(BSTNode<T>*& tree, BSTNode<T>* z)
{
    BSTNode<T>* y = nullptr;
    BSTNode<T>* x = tree;
    while (x) {
        y = x;
        if (z->key < x->key) {
            x = x->left;
        }
        else {
            x = x->right;
        }
    }

    z->parent = y;
    if (y == nullptr) {
        tree = z;
    }
    else if (z->key < y->key) {
        y->left = z;
    }
    else {
        y->right = z;
    }
}

template<typename T>
inline BSTNode<T>* BSTTree<T>::remove(BSTNode<T>*& tree, BSTNode<T>* z)
{
    BSTNode<T>* x = nullptr;
    BSTNode<T>* y = nullptr;
    if ((z->left == nullptr) || (z->right == nullptr)) {
        y = z;
    }
    else {
        y = successor(z);
    }

    if (y->left) {
        x = y->left;
    }
    else {
        x = y->right;
    }

    if (x) {
        x->parent = y->parent;
    }

    if (y->parent == nullptr) {
        tree = x;
    }
    else if (y == y->parent->left) {
        y->parent->left = x;
    }
    else {
        y->parent->right = x;
    }

    if (y != z) {
        z->key = y->key;
    }
    return y;
}

template<typename T>
inline void BSTTree<T>::destroy(BSTNode<T>*& tree)
{
    if (tree == nullptr) {
        return;
    }
    if (tree->left) {
        destroy(tree->left);
    }

    if (tree->right) {
        destroy(tree->right);
    }

    delete tree;
    tree = nullptr;
}

template<typename T>
inline void BSTTree<T>::print(BSTNode<T>* tree, T key, int direction)
{
    if (tree != nullptr)
    {
        if (direction == 0)    // tree是根节点
            cout << setw(2) << tree->key << " is root" << endl;
        else                // tree是分支节点
            cout << setw(2) << tree->key << " is " << setw(2) << key << "'s " << setw(12) << (direction == 1 ? "right child" : "left child") << endl;

        print(tree->left, tree->key, -1);
        print(tree->right, tree->key, 1);
    }
}

template<typename T>
inline T BSTTree<T>::minimum()
{
    BSTNode<T>* min = minimum(mRoot);
    if (min) {
        return min->key;
    }
    return T();
}

template<typename T>
inline T BSTTree<T>::maximum()
{
    BSTNode<T>* max = maximum(mRoot);
    if (max) {
        return max->key;
    }
    return T();
}

template<typename T>
inline BSTNode<T>* BSTTree<T>::successor(BSTNode<T>* x)
{
    // 如果x存在左孩子，则"x的前驱结点"为 "以其左孩子为根的子树的最大结点"。
    if (x->left) {
        return maximum(x->left);
    }
    // 如果x没有左孩子。则x有以下两种可能：
    // (01) x是"一个右孩子"，则"x的前驱结点"为 "它的父结点"。
    // (02) x是"一个左孩子"，则查找"x的最低的父结点，并且该父结点要具有右孩子"，找到的这个"最低的父结点"就是"x的前驱结点"
    BSTNode<T>* node = x->parent;
    while (node && x == node->left) {
        x = node;
        node = node->parent;
    }
    return node;
}

template<typename T>
inline BSTNode<T>* BSTTree<T>::predecessor(BSTNode<T>* x)
{
    // 如果x存在右孩子，则"x的后继结点"为 "以其右孩子为根的子树的最小结点"。
    if (x->right != nullptr) {
        return minimum(x->right);
    }
    // 如果x没有右孩子。则x有以下两种可能：
    // (01) x是"一个左孩子"，则"x的后继结点"为 "它的父结点"。
    // (02) x是"一个右孩子"，则查找"x的最低的父结点，并且该父结点要具有左孩子"，找到的这个"最低的父结点"就是"x的后继结点"。
    BSTNode<T>* node = x->parent;
    while (node && node->right == x) {
        x = node;
        node = node->parent;
    }
    return node;
}

这里全部写在 .h文件的原因是使用了模板类，如果实现写在cpp文件中，使用的时候要加上#include "xxx.cpp"。因为模板类在使用的时候才知道具体要变成什么类型的函数。否则会报错

    int arr[] = { 1,5,4,3,2,6 };
    int i, ilen;
    BSTTree<int>* tree = new BSTTree<int>();

    cout << "== 依次添加: ";
    ilen = sizeof(arr) / sizeof(int);
    for (i = 0; i < ilen; i++)
    {
        cout << arr[i] << " ";
        tree->insert(arr[i]);
    }

    cout << "\n== 前序遍历: ";
    tree->preOrder();

    cout << "\n== 中序遍历: ";
    tree->inOrder();

    cout << "\n== 后序遍历: ";
    tree->postOrder();
    cout << endl;

    cout << "== 最小值: " << tree->minimum() << endl;
    cout << "== 最大值: " << tree->maximum() << endl;
    cout << "== 树的详细信息: " << endl;
    tree->print();

    cout << "\n== 删除根节点: " << arr[3];
    tree->remove(arr[3]);

    cout << "\n== 中序遍历: ";
    tree->inOrder();
    cout << endl;

    // 销毁二叉树
    tree->destroy();
    delete tree;