二叉搜索树

AI那点小事

发布于 2022-06-15 07:58:08

6660

发布于 2022-06-15 07:58:08

文章被收录于专栏：AI那点小事

关于二叉树的基本操作请转到我的另一篇博客： http://blog.csdn.net/qq_30091945/article/details/77531651

概念

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

查找操作

算法如下： 1）树为空，返回NULL 2）树非空时，对根节点的键值与x即你想那个比较，如果相等则返回根节点 3）如果x小于根结点的键值，在左子树进行查找x 4）如果x大于根结点的键值，在右子树进行查找x 代码如下：

//按值查找结点
BinarySearchTree* Find(BinarySearchTree* BST,int data){
    BinarySearchTree* cur = BST;
    //搜索树为空，返回NULL 
    if(cur == NULL){
        return NULL; 
    }
    while(cur){
        //根节点值与data相等，返回根节点 
        if(cur->data == data){
            return cur;
        }else if(cur->data < data){
            //比data小，则在左子树里寻找 
            cur = cur->lchild;
        }else{//否则在右子树里寻找 
            cur = cur->rchild;
        }
    }
}

查找最大最小值

根据二叉搜索树的定义可以知道，最大值一定在最右分支的端节点上，最小值在最左分支的端节点上。查找最小值算法如下：

//查找最小值
BinarySearchTree* FindMin(BinarySearchTree* BST){
    BinarySearchTree* cur = BST;
    //搜索树为空时，返回NULL 
    if(cur == NULL){
        return NULL;
    } 
    while(cur){
        //左子树为空时，返回该节点 
        if(cur->lchild == NULL){
            return cur;
        }else{//否则在左子树里找最小值 
            cur = cur->lchild;
        }
    }
}

查找最大值算法如下：

//查找最大值
BinarySearchTree* FindMax(BinarySearchTree* BST){
    BinarySearchTree* cur = BST;
    //搜索树为空时，返回NULL 
    if(cur == NULL){
        return NULL;
    } 
    while(cur){
        //右子树为空时，返回该节点 
        if(cur->rchild == NULL){
            return cur;
        }else{//否则在右子树里找最小值 
            cur = cur->rchild;
        }
    }
}

插入操作

算法如下： 1）树空时，直接构造一个根节点即可。 2）树非空时，x小于根节点键值时，那么递归插入到左子树上。 3）x大于根节点键值时，那么队规插入到右子树上。算法如下：

//插入函数
BinarySearchTree* Insert(BinarySearchTree* BST,int data){
    //搜索树为空，则构建根节点 
    if(!BST){
        BST = new BinarySearchTree;
        BST->data = data;
        BST->lchild = BST->rchild = NULL; 
    }else{
        //若data小于根节点的值，则插入到左子树 
        if(data < BST->data){
            BST->lchild = BST->Insert(BST->lchild,data);
        }else if(data > BST->data){
            //若data小于根节点的值，则插入到左子树
            BST->rchild = BST->Insert(BST->rchild,data);
        }
    }
    return BST;
}

删除操作

算法如下: 1）树空时，直接返回NULL 2）树非空时，如果要删除的是叶子节点时，直接删除，并把父节点的相应指针置为NULL。 3）要删除的只有一个孩子时，把其父节点的指针指向要删除的结点的孩子结点。 4）要删除的有两个孩子结点时，用另一个结点代替被删除的结点：右子树的最小结点或者左子树的最大结点下面是3种情况图示：

算法如下：

//删除操作 
BinarySearchTree* Delete(BinarySearchTree* BST,int data){
    if(!BST){//树空时，直接返回NULL 
        return BST;
    }else if(data < BST->data){
        //data小于根节点时，到左子树去删除data 
        BST->lchild = this->Delete(BST->lchild,data);
    }else if(data > BST->data){
        //data大于根节点时，到右子树去删除data 
        BST->rchild = this->Delete(BST->rchild,data); 
    }else{//data等于根节点时 
        if(BST->lchild && BST->rchild){
            //左右子树都不空时，用右子树的最小来代替根节点
            BinarySearchTree* tmp = this->FindMin(BST->rchild);
            BST->data = tmp->data;
            //删除右子树的最小结点 
            this->Delete(BST->rchild,tmp->data);
        }else{//当左右子树都为空或者有一个空时 
            BinarySearchTree* tmp = BST;
            if(!BST->lchild){//左子树为空时 
                BST = BST->rchild;
            }else if(!BST->rchild){//右子树为空时 
                BST = BST->lchild; 
            }
            delete tmp; 
        }
    }
    return BST;
}

删除最小值

算法如下： 1）如果树为空，则返回NULL 2）当树不为空时，直至搜索左子树直至当前结点左子树为空，同时保存当前结点的父节点。 3）若当前结点为树的根结点时，直接返回根结点的右子树 4）否则，若当前结点的右子树为空，即当前结点为叶子结点时，父节点的左子树置NULL，释放当前结点。若当前结点的右子树不为空时，把当前结点的右子树放到父节点的左子树上，释放当前结点。返回跟结点。

//删除最小值
BinarySearchTree* DeleteMin(BinarySearchTree* BST){
    BinarySearchTree* cur = BST;    //当前结点 
    BinarySearchTree* parent = BST; //当前结点的父节点
    if(cur == NULL){
        return BST;
    }
    //当前结点的左子树非空则一直循环 
    while(cur->lchild != NULL){
        parent = cur;       //保存当前结点父节点 
        cur = cur->lchild;  //把当前结点指向左子树 
    }
    if(cur == BST){//当前结点为根结点，即只有右子树 
        BST = BST->rchild;
    }else{
        if(cur->rchild == NULL){//右子树为空，即为叶子节点 
            parent->lchild = NULL;      //父节点左子树置空
            delete cur;
        }else{//右子树非空 
            parent->lchild = cur->rchild;   //把当前结点右子树放到父节点的左子树上 
            delete cur;
        }
    }
    return BST;
}

删除最大值

算法如下： 1）如果树为空，则返回NULL 2）当树不为空时，直至搜索右子树直至当前结点右子树为空，同时保存当前结点的父节点。 3）若当前结点为树的根结点时，直接返回根结点的左子树 4）否则，若当前结点的左子树为空，即当前结点为叶子结点时，父节点的右子树置NULL，释放当前结点。若当前结点的左子树不为空时，把当前结点的左子树放到父节点的右子树上，释放当前结点。返回跟结点。

//删除最大值
BinarySearchTree* DeleteMax(BinarySearchTree* BST){
    BinarySearchTree* cur = BST;    //当前结点 
    BinarySearchTree* parent = BST; //当前结点的父节点
    if(cur == NULL){
        return BST;
    }
    //当前结点右子树非空则一直循环 
    while(cur->rchild != NULL){
        parent = cur;       //保存当前结点父节点 
        cur = cur->rchild;  //把当前结点指向右子树 
    }
    if(cur == BST){//当前结点为根结点，即只有左子树 
        BST = BST->lchild;
    }else{
        if(cur->lchild == NULL){//左子树为空，即为叶子节点 
            parent->rchild = NULL;      //父节点右子树置空 
            delete cur;
        }else{//左子树非空 
            parent->rchild = cur->lchild;   //把当前结点左子树放到父节点的右子树上 
            delete cur;
        }
    }
    return BST;
}

下面是基于下图所示二叉搜索树的具体实例程序结果：

全部代码如下：

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

int MAX = -32767;

class BinarySearchTree{
    private:
        int data;
        BinarySearchTree* lchild;
        BinarySearchTree* rchild;
    public:
        //查找最小值
        BinarySearchTree* FindMin(BinarySearchTree* BST){
            BinarySearchTree* cur = BST;
            //搜索树为空时，返回NULL 
            if(cur == NULL){
                return NULL;
            } 
            while(cur){
                //左子树为空时，返回该节点 
                if(cur->lchild == NULL){
                    return cur;
                }else{//否则在左子树里找最小值 
                    cur = cur->lchild;
                }
            }
        }

        //查找最大值
        BinarySearchTree* FindMax(BinarySearchTree* BST){ 
            BinarySearchTree* cur = BST;
            //搜索树为空时，返回NULL
            if(cur == NULL){
                return NULL;
            } 
            while(cur){
                //右子树为空时,返回该节点 
                if(cur->rchild == NULL){
                    return cur; 
                }else{//否则在左子树里找最小值 
                    cur = cur->rchild;
                }
            }
        }

        //按值查找结点
        BinarySearchTree* Find(BinarySearchTree* BST,int data){
            BinarySearchTree* cur = BST;
            //搜索树为空，返回NULL 
            if(cur == NULL){
                return NULL; 
            }
            while(cur){
                //根节点值与data相等，返回根节点 
                if(cur->data == data){
                    return cur;
                }else if(cur->data < data){
                    //比data小，则在左子树里寻找 
                    cur = cur->lchild;
                }else{//否则在右子树里寻找 
                    cur = cur->rchild;
                }
            }
        }

        //插入函数
        BinarySearchTree* Insert(BinarySearchTree* BST,int data){
            //搜索树为空，则构建根节点 
            if(!BST){
                BST = new BinarySearchTree;
                BST->data = data;
                BST->lchild = BST->rchild = NULL; 
            }else{
                //若data小于根节点的值，则插入到左子树 
                if(data < BST->data){
                    BST->lchild = BST->Insert(BST->lchild,data);
                }else if(data > BST->data){
                    //若data小于根节点的值，则插入到左子树
                    BST->rchild = BST->Insert(BST->rchild,data);
                }
            }
            return BST;
        }

        //二叉搜索树的构造,利用data数组构造二叉搜索树 
        BinarySearchTree* Create(int* data,int size){
            BinarySearchTree* bst = NULL; 
            for(int i = 0 ; i < size ; i++){
                bst = this->Insert(bst,data[i]);
            }
            return bst;
        }

        //递归前序遍历 
        void PreorderTraversal(BinarySearchTree* T){
            if(T == NULL){
                return;
            }
            cout<<T->data<<" ";                         //访问根节点并输出 
            T->PreorderTraversal(T->lchild);            //递归前序遍历左子树 
            T->PreorderTraversal(T->rchild);            //递归前序遍历右子树
        }

        //递归中序遍历 
        void InorderTraversal(BinarySearchTree* T){
            if(T == NULL){
                return;
            }
            T->InorderTraversal(T->lchild);             //递归中序遍历左子树 
            cout<<T->data<<" ";                         //访问根节点并输出 
            T->InorderTraversal(T->rchild);             //递归中序遍历左子树 
        }

        //递归后序遍历 
        void PostorderTraversal(BinarySearchTree* T){
            if(T == NULL){
                return;
            }
            T->PostorderTraversal(T->lchild);           //递归后序遍历左子树 
            T->PostorderTraversal(T->rchild);           //递归后序遍历右子树 
            cout<<T->data<<" ";                         //访问并打印根节点 
        }

        //删除操作 
        BinarySearchTree* Delete(BinarySearchTree* BST,int data){
            if(!BST){//树空时，直接返回NULL 
                return BST;
            }else if(data < BST->data){
                //data小于根节点时，到左子树去删除data 
                BST->lchild = this->Delete(BST->lchild,data);
            }else if(data > BST->data){
                //data大于根节点时，到右子树去删除data 
                BST->rchild = this->Delete(BST->rchild,data); 
            }else{//data等于根节点时 
                if(BST->lchild && BST->rchild){
                    //左右子树都不空时，用右子树的最小来代替根节点
                    BinarySearchTree* tmp = this->FindMin(BST->rchild);
                    BST->data = tmp->data;
                    //删除右子树的最小结点 
                    BST->rchild = this->Delete(BST->rchild,tmp->data);
                }else{//当左右子树都为空或者有一个空时 
                    BinarySearchTree* tmp = BST;
                    if(!BST->lchild){//左子树为空时 
                        BST = BST->rchild;
                    }else if(!BST->rchild){//右子树为空时 
                        BST = BST->lchild; 
                    }
                    delete tmp; 
                }
            }
            return BST;
        }

        int getdata(BinarySearchTree* BST){
            return BST->data;
        }

        //删除最小值
        BinarySearchTree* DeleteMin(BinarySearchTree* BST){
            BinarySearchTree* cur = BST;    //当前结点 
            BinarySearchTree* parent = BST; //当前结点的父节点
            if(cur == NULL){
                return BST;
            }
            //当前结点的左子树非空则一直循环 
            while(cur->lchild != NULL){
                parent = cur;       //保存当前结点父节点 
                cur = cur->lchild;  //把当前结点指向左子树 
            }
            if(cur == BST){//当前结点为根结点，即只有右子树 
                BST = BST->rchild;
            }else{
                if(cur->rchild == NULL){//右子树为空，即为叶子节点 
                    parent->lchild = NULL;      //父节点左子树置空
                    delete cur;
                }else{//右子树非空 
                    parent->lchild = cur->rchild;   //把当前结点右子树放到父节点的左子树上 
                    delete cur;
                }
            }
            return BST;
        }

        //删除最大值
        BinarySearchTree* DeleteMax(BinarySearchTree* BST){
            BinarySearchTree* cur = BST;    //当前结点 
            BinarySearchTree* parent = BST; //当前结点的父节点
            if(cur == NULL){
                return BST;
            }
            //当前结点右子树非空则一直循环 
            while(cur->rchild != NULL){
                parent = cur;       //保存当前结点父节点 
                cur = cur->rchild;  //把当前结点指向右子树 
            }
            if(cur == BST){//当前结点为根结点，即只有左子树 
                BST = BST->lchild;
            }else{
                if(cur->lchild == NULL){//左子树为空，即为叶子节点 
                    parent->rchild = NULL;      //父节点右子树置空 
                    delete cur;
                }else{//左子树非空 
                    parent->rchild = cur->lchild;   //把当前结点左子树放到父节点的右子树上 
                    delete cur;
                }
            }
            return BST;
        }
};

int main()
{
    int size;
    cout<<"请输入结点个数："<<endl; 
    cin>>size;
    int* data;
    data = new int[size];
    cout<<"请输入每个结点的值："<<endl;
    for(int i = 0 ; i < size ; i++){
        cin>>data[i];
    }
    BinarySearchTree* bst;
    bst = new BinarySearchTree;
    bst = bst->Create(data,size);

    cout<<"前序遍历（递归）："<<endl;
    bst->PreorderTraversal(bst);
    cout<<endl;

    cout<<"中序遍历（递归）："<<endl;
    bst->InorderTraversal(bst);
    cout<<endl;

    cout<<"后序遍历（递归）："<<endl;
    bst->PostorderTraversal(bst);
    cout<<endl;

    BinarySearchTree* bst_max;
    bst_max = bst->FindMax(bst);
    cout<<"二叉搜索树的最大值为："<<endl;
    cout<<bst_max->getdata(bst_max);
    cout<<endl;
    cout<<"删除最大值后："<<endl;
    bst = bst->DeleteMax(bst);
    cout<<"前序遍历（递归）："<<endl;
    bst->PreorderTraversal(bst);
    cout<<endl;

    cout<<"中序遍历（递归）："<<endl;
    bst->InorderTraversal(bst);
    cout<<endl;

    cout<<"后序遍历（递归）："<<endl;
    bst->PostorderTraversal(bst);
    cout<<endl;

    cout<<"二叉搜索树的最小值为："<<endl;
    BinarySearchTree* bst_min; 
    bst_min = bst->FindMin(bst);
    cout<<bst_min->getdata(bst_min);     
    cout<<endl;
    cout<<"删除最小值后："<<endl;
    bst = bst->DeleteMin(bst);
    cout<<"前序遍历（递归）："<<endl;
    bst->PreorderTraversal(bst);
    cout<<endl;

    cout<<"中序遍历（递归）："<<endl;
    bst->InorderTraversal(bst);
    cout<<endl;

    cout<<"后序遍历（递归）："<<endl;
    bst->PostorderTraversal(bst);
    cout<<endl;

    int num;
    cout<<"请输入要删除的结点："<<endl;
    cin>>num;
    bst = bst->Delete(bst,num);
    cout<<"删除之后："<<endl;
    cout<<"前序遍历（递归）："<<endl;
    bst->PreorderTraversal(bst);
    cout<<endl;

    cout<<"中序遍历（递归）："<<endl;
    bst->InorderTraversal(bst);
    cout<<endl;

    cout<<"后序遍历（递归）："<<endl;
    bst->PostorderTraversal(bst);
    cout<<endl;

    return 0;
 }

截图如下：