BST 二叉搜索树 C++ 算法导论

算法全是看算法导论的，这的确是本好书，值得收藏。只是看着有点脑袋疼。。。。（开溜。。。。）

#include <iostream>
#include <cstdlib>
using namespace std;

template<class T>
struct BST_Node {//节点数据结构
    T key;
    BST_Node<T> *left, *right, *parent;//左、右孩子、父节点
    BST_Node() { key = 0; left = right = parent = nullptr; }
    BST_Node(T key, BST_Node *left, BST_Node *right, BST_Node *parent) {
        this->key = key;
        this->left = left;
        this->right = right;
        this->parent = parent;
    }

};

template <class T>
class BSTree {//二叉搜索树
public:
    BSTree() { root = 0; }
    ~BSTree() { this->destroy(this->root); }
    bool insert_key(const T z);
    bool search_key(BST_Node<T> *&x, const T key) const;
    bool delete_key(const T key);
    bool is_empty_tree()const { return this->root == nullptr; }
    T min_element() const;
    T max_element() const;
    BST_Node<T> *successor(BST_Node<T> *x) const;//前驱节点
    BST_Node<T> *predecessor(BST_Node<T> *x) const;//后继节点
    void inOrder();//中序遍历
private:
    BST_Node<T> *root;//根节点
    BST_Node<T> *min_element(BST_Node<T> *x) const;
    BST_Node<T> *max_element(BST_Node<T> *x) const;
    BST_Node<T> *inOrder(BST_Node<T> *x);
    BST_Node<T> *delete_key(BST_Node<T> *&t, BST_Node<T> *z);
    void destroy(BST_Node<T> * t);
};

inline void menu() 
{
    cout << "1、插入新值\n2、查找值\n3、删除值\n";
    cout << "4、最大值\n5、最小值\n6、退出\n";
}

inline void cls() { system("pause"); system("cls"); }
inline void output(BSTree<long long> *tree) { tree->inOrder(); cout << endl; cls();}

int main()
{
    BSTree<long long> *tree = new BSTree<long long>();
    BST_Node<long long> * t = nullptr;
    long long select = 0, x = 0;
    bool loop = true;
    while (loop) {
        if (!tree->is_empty_tree()) { cout << "中序遍历： \n"; tree->inOrder(); cout << endl; }
        menu();
        cin >> select;
        switch (select) {
            case 1: {
                cout << "输入key:" << endl;
                cin >> x;
                cout << (tree->insert_key(x) == true ? "插入成功\n" : "插入失败\n") << "操作后中序遍历的结果： \n";
                output(tree);
                break;
            }
            case 2: {
                cout << "输入查找的key:" << endl;
                cin >> x;
                cout << (tree->search_key(t, x) == true ? "找到了\n" : "未找到\n");
                cls();
                break;
            }
            case 3: {
                cin >> x;
                cout << (tree->delete_key(x) == true ? "删除成功\n" : "删除失败\n") << "操作后中序遍历的结果： \n";
                output(tree);
                break;
            }
            case 4: cout << "最大值： " << tree->max_element() << endl; output(tree); break;
            case 5: cout << "最小值： " << tree->min_element() << endl; output(tree); break;
            case 6: loop = false; break;
            default: cout << "指令不正确，请重新输入\n"; cls(); break;

        }
    }
    return 0;
}

template<class T>
bool BSTree<T>::insert_key(const T key)
{
    BST_Node<T> *x = nullptr, *y = nullptr, *z = nullptr;
    x = this->root;
    z = new BST_Node<T>(key, nullptr, nullptr, nullptr);
    if (z == nullptr) return false;
    while (x != nullptr) {
        y = x;
        if (z->key < x->key) x = x->left;
        else x = x->right;
    }
    z->parent = y;
    if (y == nullptr) this->root = z;
    else if (z->key < y->key) y->left = z;
    else y->right = z;
    return true;
}

template<class T>
bool BSTree<T>::search_key(BST_Node<T> *&x,const T key) const
{
    x = this->root;
    while (x != nullptr && key != x->key) {
        if (key < x->key) x = x->left;
        else x = x->right;
    }
    return x == nullptr ? false : true;
}

template<class T>
bool BSTree<T>::delete_key(const T key)
{
    BST_Node<T> *x = nullptr, *y = nullptr;
    if (this->search_key(x, key) == true) {
        if ((y = this->delete_key(this->root, x)) != nullptr) {
            delete y;
            return true;
        }
    }
    return false;
}

template<class T>
BST_Node<T>* BSTree<T>::delete_key(BST_Node<T>*& t, BST_Node<T>* z)
{
    BST_Node<T> *x = nullptr, *y = nullptr;
    if (z->left == nullptr || z->right == nullptr) y = z;
    else y = this->successor(z);
    if (y->left != nullptr) x = y->left;
    else x = y->right;
    if (x != nullptr) x->parent = y->parent;
    if (y->parent == nullptr) t = 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<class T>
void BSTree<T>::destroy(BST_Node<T>* t)
{
    if (t == nullptr) return;
    if (t->left != nullptr) this->destroy(t->left);
    if (t->right != nullptr) this->destroy(t->right);
    delete t;
}

template<class T>
T BSTree<T>::min_element() const
{
    return (this->min_element(this->root))->key;
}

template<class T>
T BSTree<T>::max_element() const
{
    return (this->max_element(this->root))->key;
}

template<class T>
BST_Node<T> *BSTree<T>::min_element(BST_Node<T>* x) const
{
    if (x == nullptr)return nullptr;
    while (x->left != nullptr) x = x->left;
    return x;
}

template<class T>
BST_Node<T> *BSTree<T>::max_element(BST_Node<T>* x) const
{
    if (x == nullptr)return nullptr;
    while (x->right != nullptr) x = x->right;
    return x;
}

template<class T>
BST_Node<T>* BSTree<T>::inOrder(BST_Node<T>* x)
{
    if (x != nullptr) {
        this->inOrder(x->left);
        cout << x->key << " ";
        this->inOrder(x->right);
    }
    return nullptr;
}

template<class T>
BST_Node<T>* BSTree<T>::successor(BST_Node<T>* x) const
{
    if (x->right != nullptr) return this->min_element(x->right);
    BST_Node<T> *y = x->parent;
    while (y != nullptr && x == y->right) {
        x = y;
        y = y->parent;
    }
    return y;
}

template<class T>
BST_Node<T>* BSTree<T>::predecessor(BST_Node<T>* x) const
{
    if (x->left != nullptr) return this->max_element(x->left);
    BST_Node<T> *y = x->parent;
    while (y != nullptr && x == y->left) {
        x = y;
        y = y->parent;
    }
    return y;
}

template<class T>
void BSTree<T>::inOrder()
{
    this->inOrder(this->root);
}

附上算法导论二叉搜索树讲解截图，非常感谢这本书的作者。