二叉排序树的插入算法和删除某一节点算法

灰太狼 2022-05-21 12:24 188阅读 0赞

二叉排序树的插入和删除某一节点  
![这里写图片描述][70]

#include <iostream>
    using namespace std;
    typedef int KeyType;
    typedef int InfoType;
    typedef struct
    {
        KeyType key;
        InfoType otherinfo;
    }ElemType;
    typedef struct BSTNode
    {
        ElemType data;
        struct BSTNode *lchild,*rchild;
    }BSTNode,*BST;
    void InsertBST(BST &T,ElemType e)
    {
        BSTNode *S;
        if(!T)
        {
            S=new BSTNode;
            S->data=e;
            S->lchild=S->rchild=NULL;
            T=S;
        }
        else if(e.key<T->data.key) InsertBST(T->lchild,e);
        else if(e.key>T->data.key) InsertBST(T->rchild,e);
    }
    void CreateBST(BST &T)
    {
        ElemType e;
        T=NULL;
        cin>>e.key;
        for(int i=1;i<=15;i++)
        {
            InsertBST(T,e);
            cin>>e.key;
        }
    }
    void SearchBST(BST &T,KeyType key)
    {
        if(T&&key==T->data.key) cout<<"查找成功！"<<endl;
        else if(T&&key<T->data.key) return SearchBST(T->lchild,key);
        else if(T&&key>T->data.key) return SearchBST(T->rchild,key);
        else cout<<"查找失败"<<endl;
    }
    void DeleteBST(BST &T,KeyType key)
    {
        BST P,F,Q,S;
        P=T;F=NULL;
        while(P)
        {
            if(P->data.key==key) break;
            F=P;
            if(P->data.key>key) P=P->lchild;
            else P=P->rchild;
        }
        if(!P) return;
        Q=P;
        if((P->lchild)&&(P->rchild))
        {
            S=P->lchild;
            while(S->rchild)
            {
                Q=S;
                S=S->rchild;
            }
            P->data=S->data;
            if(Q!=P) Q->rchild=S->lchild;
            else Q->lchild=S->lchild;
            delete S;
            return;
        }
        else if(!P->rchild)
        {
            P=P->lchild;
        }
        else if(!P->lchild)
        {
          P=P->rchild;
        }
        if(!F) T=P;
        else if(Q==F->lchild) F->lchild=P;
        else F->rchild=P;
        delete Q;
    }
    void Show(BST T)
    {
        if(T)
        {
            Show(T->lchild);
            cout<<T->data.key<<" ";
            Show(T->rchild);
        }
    }
    int main()
    {
        BST T;
        int key1,key2;
        CreateBST(T);
        Show(T);
        cout<<endl;
        cin>>key1;
        SearchBST(T,key1);
        DeleteBST(T,14);
        Show(T);
    }

[70]: /images/20220521/135103d79d88496abef665050e2dcd6f.png