二叉搜索树——详解及代码实现

完整代码：

#include<iostream>
#include<unordered_map>
#include<vector>
#define elem int
using namespace std;

//二叉树操作
class TreeNode
{
    public:
        elem data;
        TreeNode *lchild;
        TreeNode *rchild;
        TreeNode(elem a) : data(a), lchild(NULL), rchild(NULL){};


        //前序遍历
        void PreOrderTraverse(TreeNode* root){
            if(NULL == root)
                return;
            cout<<root->data;
            PreOrderTraverse(root->lchild);
            PreOrderTraverse(root->rchild);
        }

        //中序遍历
        void InOrderTraverse(TreeNode* root){
            if(NULL == root)
                return;
            PreOrderTraverse(root->lchild);
            cout<<root->data;
            PreOrderTraverse(root->rchild);
        }

        //后序遍历
        void PostOrderTraverse(TreeNode* root){
            if(NULL == root)
                return;
            PreOrderTraverse(root->lchild);
            PreOrderTraverse(root->rchild);
            cout<<root->data;
        }


};

//二叉搜索树
class BST{
    private: 
        TreeNode *root;
    public:

        //判断一棵树是不是二叉搜索树
        bool IsBST(TreeNode *T)
        {
            TreeNode *p;
            if(T==NULL)return true;
            if(!IsBST(T->lchild)||!IsBST(T->rchild))return false;
            p=T->lchild;
            if(p){
                while(p->rchild)
                    p=p->rchild;
                if(p->data>T->data)return false;
            }
            p=T->rchild;
            if(p){
                while(p->lchild)
                    p=p->lchild;
                if(p->data<T->data)return false;
            }
            return true;
        }
        
        //插入二叉树(递归实现)
        TreeNode *Insert_Node(TreeNode* root,int val)
        {
            if(root==NULL)
            {
                root = new TreeNode(val);
                return root;
            }

            if(val<=root->data)
            {
                root->lchild=Insert_Node(root->lchild,val);
            }else{
                root->rchild=Insert_Node(root->rchild,val);
            }
        }

        //根据数组建立二叉树
        void BuildTree(const vector<int>& arr)
        {
            for(int i=0;i<arr.size();i++)
            {
                Insert_Node(root,arr[i]);
            }
        }

        //搜索某个节点是否存在
        bool Search_Node(TreeNode* root,int val)
        {
            if(root==NULL)return false;
            if(val==root->data)return true;
            if(val<=root->data){
                return Search_Node(root->lchild,val);
            }else{
                return Search_Node(root->rchild,val);
            }
        }

        //删除指定节点
        TreeNode *Delete_Node(TreeNode *root)
        {
                //当前节点没有左右子树时(即叶节点)直接删除
                if(root->lchild==NULL&&root->rchild==NULL){
                    TreeNode *temp=root;
                    delete root;
                    temp = NULL;
                    return temp;
                //当前节点没有右子树时，返回当前节点的左子树
                }else if (root->lchild!=NULL&&root->rchild==NULL){
                    TreeNode *temp=root->lchild;
                    delete root;
                    return temp;
                //当前节点没有左子树时，返回当前节点的右子树
                }else if(root->lchild==NULL&&root->rchild!=NULL){
                    TreeNode *temp=root->rchild;
                    delete root;
                    return temp;
                //方法1
                //当前节点(root)既有左子树又有右子树时，找到左子树中的最大值(又叫作直接前驱)(即左子树中最右边的值，所以他没有右子树)，将其右子树赋值为当前(即要删除节点）的右子树，然后删除当前节点(root)
                }else if(root->lchild!=NULL&&root->rchild!=NULL){
                    TreeNode *cur=root->lchild;
                    while(cur->rchild!=NULL){
                        cur=cur->rchild;
                    }
                    cur->rchild=root->rchild;
                    TreeNode *temp=root->lchild;
                    delete root;
                    return temp;
                }
                //方法2
                //当前节点(root)既有左子树又有右子树时，找到右子树中的最小值(又叫做直接后继)(即右子树中最左边的值，所以他没有左子树)，将其右子树赋值为当前(即要删除节点）的左子树，然后删除当前节点(root)
                /*}else if(root->lchild!=NULL&&root->rchild!=NULL){
                    TreeNode *cur=root->rchild;
                    while(cur->lchild!=NULL){
                        cur=cur->lchild;
                    }
                    cur->lchild=root->lchild;
                    TreeNode *temp=root->rchild;
                    delete root;
                    return temp;
                }*/
        }

        //根据传入val删除对应节点
        TreeNode *Delete_Node_byval(TreeNode* root,int val)
        {
            if(root==NULL)return NULL;
            //删除值比当前节点小时，向左子树递归删除
            if(val<root->data){
                root->lchild=Delete_Node_byval(root->lchild,val);

            //删除值比当前节点大时，向右子树递归删除
            }else if(val>root->data){
                root->rchild=Delete_Node_byval(root->rchild,val);

            //当前节点为要删除的节点
            }else{
                return Delete_Node(root);
            }
        }

        //计算二叉树的深度
        int Max_BT_Hight(TreeNode* root)
        {
            int left_hight=0;
            int right_hight=0;
            int max_hight=0;

            if(root->lchild!=NULL){
                left_hight=Max_BT_Hight(root->lchild);
            }
            if(root->rchild!=NULL){
                right_hight=Max_BT_Hight(root->rchild);
            }
            left_hight>right_hight?max_hight=left_hight+1:max_hight=right_hight+1;
            return max_hight;
        }
};