数据结构 排序二叉树

又一次被树折磨，这一次是排序二叉树，似乎能够理解为什么set容器能够实现插入后自动排序了，也去查了一下资料，set底层确实是以二叉树实现的。

一点点注意事项： 如果序列本身为升序或者降序，会形成斜树（即链表，起不到优化作用） BST + 限制 = AVL树

接下来就是AVL树（二叉平衡树）了，准备坐大牢，已经在思考红黑树会有多坐牢了，不过学完树之后似乎只剩图和串了，之后就要开始算法坐大牢了……

日常： 快放假了，但是一堆期末考试在等着我，估计了一下约莫有八九门的样子，希望别挂科（应该不会，感觉学的还是挺好的，就是历史闭卷有点难绷），距离四级还有六天，似乎注定要裸考了，乐

代码实现：

#define _CRT_SECURE_NO_WARNINGS
#include<iostream>
using namespace std;
template<class T>
class BST_Node
{
public:
    T data;
    BST_Node<T>* left;
    BST_Node<T>* right;
public:
    BST_Node()
    {
        left = nullptr;
        right = nullptr;
    }
};
template<class T>
class BST
{
public:
    BST_Node<T>* root;
public:
    BST(T k)
    {
        root = new BST_Node<T>;
        if (root == nullptr)
        {
            cout << "建树失败" << endl;
        }
        else
        {
            root->data = k;
        }
    }
    //非递归实现插入
    BST_Node<T>* Insert_non_recursion(T k)
    {
        BST_Node<T>* s = new BST_Node<T>;
        if (s == nullptr)
        {
            cout << "插入失败" << endl;
        }
        else
        {
            s->data = k;
            s->left = nullptr;
            s->right = nullptr;
            //通过p进行遍历，pre指向p父亲节点
            BST_Node<T>* p = root;
            BST_Node<T>* pre = nullptr;
            while (p != nullptr)
            {
                if (k < p->data)
                {
                    pre = p;
                    p = p->left;
                }
                else
                {
                    pre = p;
                    p = p->right;
                }
            }
            if (k < pre->data)
            {
                pre->left = s;
            }
            else
            {
                pre->right = s;
            }
            return root;
        }
    }
    //递归实现插入(必须要有返回值)
    //往 以ro为根节点的树中插入数据x 
    //if(x<ro->data)  以ro->left为根节点的子树中插入数据x 
    //if(x>ro->data)  以ro->right为根节点的子树中插入数据x
    //递归出口：  if(ro==NULL)创建新结点s,return s; 
    BST_Node<T>* Insert(BST_Node<T>* ro,T k)
    {
        if (ro == nullptr)
        {
            BST_Node<T>* s = new BST_Node<T>;
            s->data = k;
            s->left = nullptr;
            s->right = nullptr;
            return s;
        }
        if (k < ro->data)
        {
            //ro->left接收返回值
            ro->left = Insert(ro->left, k);
            //把变化后的子树的根节点返回
            return ro;
        }
        else
        {
            //ro->right接收返回值
            ro->right = Insert(ro->right, k);
            //把变化后的子树的根节点返回
            return ro;
        }
    }
    //查找
    void Find(T k)
    {
        BST_Node<T>* p = root;
        while (p != nullptr && p->data != k)
        {
            if (k < p->data)
            {
                p = p->left;
            }
            else
            {
                p = p->right;
            }
        }
        if (p == nullptr)
        {
            cout << "不存在" << endl;
        }
        else
        {
            cout << "存在" << endl;
        }
    }
    //递归实现中序遍历
    void mid_Order(BST_Node<T>* ro)
    {
        if (ro == nullptr)
        {
            return;
        }
        if (ro->left != nullptr)
        {
            mid_Order(ro->left);
        }
        cout << ro->data << ' ';
        if (ro->right != nullptr)
        {
            mid_Order(ro->right);
        }
    }
    //找以ro为根节点的树中最靠右节点
    BST_Node<T>* Find_p(BST_Node<T>* ro)
    {
        BST_Node<T>* p = ro;
        while (p->right != nullptr)
        {
            p = p->right;
        }
        return p;
    }
    BST_Node<T>* Del(BST_Node<T>* ro,T k)
    {
        //删除后让谁顶替
        //分三种情况
        //1.所在节点度为0（叶子节点）
        //直接删除，该位置置空
        //2.所在节点度为1
        //找到该节点并删除，让其唯一的一个孩子顶替该节点位置
        //(情况一可以看成情况二，只需写一份代码)
        //3.所在节点度为2
        //找到该节点并删除，用该节点的右子树中最靠左节点
        //或左子树最靠右节点代替删除节点
        //（将问题进行转换）找到该节点，把其数据域改为左子树最靠右节点数据域的值，对左子树进行递归，删除左子树最右节点
        
        //原问题：在以root为根的树中删除数据k
        if (ro->data > k)
        {
            //问题转换成，在以ro->left为根的子树中删除数据k
            ro->left = Del(ro->left, k);
            //return ro;转换为最后返回ro
        }
        else if (ro->data < k)
        {
            //问题转换成，在以ro->right为根的子树中删除数据k
            ro->right = Del(ro->right, k);
            //return ro;转换为最后返回ro
        }
        else
        {
            //即ro->data == k
            //判断该节点的度

            //有两个孩子
            if (ro->left != nullptr && ro->right != nullptr)
            {
                //找到root左子树最靠右节点p
                BST_Node<T>* p = Find_p(ro->left);
                ro->data = p->data;
                //问题转换成，在以ro->left为根的子树中删除数据p->data
                ro->left = Del(ro->left, p->data);
                //return ro;转换为最后返回ro
            }
            else
            {
                //只有一个孩子(若度为0则将其右孩子视为存在，将度为1和度为0的情况统一起来)
                BST_Node<T>* ch = nullptr;//记录孩子
                if (ro->left != nullptr)
                {
                    ch = ro->left;
                }
                else
                {
                    ch = ro->right;
                }
                delete ro;
                ro = nullptr;
                return ch;
            }
        }
        return ro;
    }
};
int main()
{
    BST<int> bstree(85);
    for (int i = 0; i < 10; ++i)
    {
        bstree.Insert(bstree.root, i);
    }
    for (int i = 100; i < 110; ++i)
    {
        bstree.Insert_non_recursion(i);
    }
    bstree.mid_Order(bstree.root);
    bstree.Del(bstree.root, 85);
    bstree.Del(bstree.root, 100);
    cout << endl;
    bstree.mid_Order(bstree.root);
    return 0;
}
//如果序列本身为升序或者降序，会形成斜树（即链表，起不到优化作用）
//BST + 限制 = AVL树