二叉查找树（Binary Search Tree），（又：二叉搜索树，二叉排序树）它或者是一棵空树，或者是具有下列性质的二叉树： 若它的左子树不空，则左子树上所有结点的值均小于它的根结点的值； 若它的右子树不空，则右子树上所有结点的值均大于它的根结点的值； 它的左、右子树也分别为二叉排序树。

1.原理

二叉排序树的查找过程和次优二叉树类似，通常采取二叉链表作为二叉排序树的存储结构。中序遍历二叉排序树可得到一个关键字的有序序列，一个无序序列可以通过构造一棵二叉排序树变成一个有序序列，构造树的过程即为对无序序列进行排序的过程。每次插入的新的结点都是二叉排序树上新的叶子结点，在进行插入操作时，不必移动其它结点，只需改动某个结点的指针，由空变为非空即可。搜索,插入,删除的复杂度等于树高，O(log(n)).

2.代码实现

整体

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
using namespace std;

const double EPS = 1E-6;

template<typename T>struct node
{
    T value;

    node<T>* parent = nullptr;
    node<T>* left = nullptr;
    node<T>* right = nullptr;

    node(const T &v = 0) :value(v) {    };

    T operator * ()
    {
        return value;
    }
};

template<typename T> class BST
{
private:
    node<T>* root = nullptr;
    int SIZE = 0;

public:
    BST() {};
    BST(vector<T> v);
    node<T>* GetRoot() { return root; }
    bool empty() { return SIZE == 0; }
    int size() { return SIZE; }
    node<T>* find(const T &v);
    node<T>* find_predecessor(const T &v);//寻找前驱节点
    node<T>* find_successor(const T &v);//寻找后继节点
    node<T>* find_predecessor(node<T>* n);
    node<T>* find_successor(node<T>* n);
    void insert(const T &v);
    void insert(node<T>* n);
    void erase(node<T>* n);
    bool erase(const T &v);
    void clear();
    //void traversal(node<T>* root, void(*func)(T v) = [](T v)->void {cout << value << " "; });//遍历输出所有节点
    void traversal();
};

template<typename T> BST<T>::BST(vector<T> v) :BST()
{
    for (auto n : v)//C++11支持的冒号遍历
        insert(n);  //auto的作用是自动选择相应的类型
    
    return;
}

template<typename T> node<T>* BST<T>::find(const T &v)
{//二叉搜索树的查找，只需和父节点的值比较即可找到
    node<T>* temp = root;

    while (temp != nullptr)//temp为空时就表明没找到
    {
        if (v == temp->value)//找到就返回
            return temp;
        else
        {
            if (v < temp->value)
                temp = temp->left;
            else
                temp = temp->right;
        }
    }

    return nullptr;
}

//节点x的前驱，就是指key值小于x.key的节点中key值最大的那个
//若x的左子树不为空，则x前驱是x节点左子树里最靠右的那个节点
//如果x的左子树为空，那么我们就要向上找x的第一个有右孩子且左子树里没有x节点的祖先。

template<typename T> node<T>* BST<T>::find_predecessor(const T &v)
{
    node<T>* n = find(v);
    return n == nullptr ? nullptr : find_predecessor(n);
}

template<typename T> node<T>* BST<T>::find_predecessor(node<T>* n)
{
    node<T>* temp = n;

    if (temp->left != nullptr)//如果节点有左子树
    {
        temp = temp->left;

        while (temp->right != nullptr)//找左子树中最右边的叶子
            temp = temp->right;

        return temp;
    }

    while (temp->parent != nullptr && temp->parent->left == temp)
        temp = temp->parent;

    return temp->parent;
}

//节点x的后继，就是指key值大于x.key的节点中key值最小的那个
//若x的右子树不为空，则x后继是x节点右子树里最靠左的那个节点
//如果x的右子树为空，那么我们就要向上找x的第一个有左孩子且右子树里没有x节点的祖先。

template<typename T> node<T>* BST<T>::find_successor(const T &v)
{
    node<T>* n = find(v);
    return n == nullptr ? nullptr : find_successor(n);
}

template<typename T> node <T>* BST<T>::find_successor(node<T>* n)
{
    node<T>* temp = n;

    if (temp->right != nullptr)//若右子树不为空
    {
        temp = temp->right;

        while (temp->left != nullptr)//找右子树中最左边的叶子
            temp = temp->left;

        return temp;
    }

    while (temp->parent != nullptr && temp->parent->right != temp)
        temp = temp->parent;

    return temp->parent;
}

//新插入的节点一定会取代一个原来的叶子节点，我们只要确定被取代的是哪一个叶子节点就行了
//我们从根节点开始，利用二叉搜索树的性质比对值来向下查找，直到到达最后的叶子节点，这个节点就是要用插入节点替换的叶子节点。

template<typename T> void BST<T>::insert(const T &v)
{
    node<T>* n = new node<T>(v);
    insert(n);
    return;
}

template<typename T> void BST<T>::insert(node<T>* n)
{
    node<T>* temp = root;
    SIZE++;

    if (temp == nullptr)
    {//如果根节点为空，则直接插入
        root = n;
        return;
    }

    while (true)//循环找出插入的位置
    {
        if (temp->value > n->value)
        {//插入在左子树的情况
            if (temp->left != nullptr)
                temp = temp->left;//左子树不为空则继续找
            else
            {
                temp->left = n;//如果左子树为空则直接插入
                n->parent = temp;//修改父节点为temp指向的节点
                return;
            }
        }
        else
        {//插入右子树的情况，同上
            if (temp->right != nullptr)
                temp = temp->right;
            else
            {
                temp->right = n;
                n->parent = temp;
                return;
            }
        }
    }

    return;
}

//删除的情况比插入复杂，一共有3种可能的情况。
//1，被删除的节点x没有NIL节点以外的孩子节点时，直接删除，修改父节点指针指向NIL节点即可。
//2，被删除的节点x只有一个孩子时，用这个孩子节点替换被删除节点的位置即可。
//3，被删除的节点x有两个孩子时，我们就要查找x节点的后继y节点，注意y节点一定在x节点的右子树中而且y节点没有左孩子，此时，我们先用y节点的右孩子代替y节点原先的位置，然后再用y节点代替x节点位置即可完成删除操作。

template<typename T> bool BST<T>::erase(const T &v)
{
    node<T>* temp = find(v);

    if (temp != nullptr)
        erase(temp);
    else
        return false;

    return true;
}

template<typename T> void BST<T>::erase(node<T>* n)
{
    SIZE--;

    node<T>* temp;

    if (n->left == nullptr && n->right == nullptr)
        temp = nullptr;//情况1：没有子节点
    else if (n->left == nullptr || n->right == nullptr)
    {//情况2：有一个子节点
        temp = n->left == nullptr ? n->right : n->left;
        temp->parent = n->parent;//因为temp要取代n，所以temp要完全复制n的信息。又因temp是n的一个子节点，故只需复制n的parent就够了
    }
    else//情况3：有两个子节点
    {
        temp = find_successor(n);//用n节点的后继y来取代n
        node<T>* successor_right;//后继y可能有右儿子，所以需要先用y的右儿子取代y，再让y取代n

        if (temp->right == nullptr)//没有右儿子的话就用nullptr来取代y
            successor_right = nullptr;
        else
        {
            successor_right = temp->right;
            successor_right->parent = temp->parent;//用y的右儿子取代y
        }

        if (temp->parent->left == temp)//这里用来修改y的父节点，使y的右儿子完全取代y
            temp->parent->left = successor_right;
        else
            temp->parent->right = successor_right;

        //至此，对y的处理就已经完成了。接下来就是让y取代n了
        //这一步只需要把y的值赋值给n，然后删除y就好了

        n->value = temp->value;
        delete temp;

        return;
    }

    //情况一和情况二到此为止取代n节点的temp已经确定，而且当temp不是nullptr的时候，temp也已经复制了必要的n的属性，剩下的就是让n的父节点指向temp了
    //注意被删除的节点有可能是根节点，所以当我们发现被删除的是根节点时，不需要让n的父节点指向temp，因为n没有父节点了，但是这个时候必须修改root指针的指向

    if (n->parent != nullptr)
    {
        if (n->parent->left == temp)
            n->parent->left = temp;
        else
            n->parent->right = temp;
    }
    else
        root = temp;

    delete n;

    return;
}

template<typename T>void BST<T>::clear()
{
    if (root == nullptr)
        return;

    queue<node<T>*> q;

    q.push(root);

    while (!q.empty())
    {
        node<T>* temp = q.front();
        q.pop();

        if (temp->left != nullptr)
            q.push(temp->left);

        if (temp->right != nullptr)
            q.push(temp->right);

        delete temp;

        SIZE--;
    }

    root = nullptr;

    return;
}

//第一个参数是为了进行递归而设立的。
//第二个参数是一个函数指针，这个函数指针指向一个没有返回值同时有一个int类型参数的函数，
//并且我用lambda表达式给这个函数指针赋了一个默认值，这个默认函数的功能是输出参数k，用来遍历输出每一个节点的值，
//大家可以用别的lambda表达式或者函数来覆盖这个默认值，以达到定制功能的目的

//template<typename T> void BST<T>::traversal(node<T>* root, void(*func)(T v))
//{
//    if (root = nullptr)
//        return;
//
//    traversal(root->left);
//    func(root->value);
//    traversal(root->right);
//
//    return;
//}

template<typename T> void BST<T>::traversal()
{//广搜遍历输出
    if (root == nullptr)
        return;

    queue<node<T>*> q;
    
    q.push(root);

    while (!q.empty())
    {
        node<T>* temp = q.front();
        q.pop();

        cout << temp->value << " ";

        if (temp->left != nullptr)
            q.push(temp->left);

        if (temp->right != nullptr)
            q.push(temp->right);
    }

    return;
}

输出的那一块注释掉的是lambda语法写的输出。因为我这里写的是模板类，导致会有错误。把所有和模板有关的改成int就可以用了。

前中后序遍历后面再写吧。