实验5 结合二叉树的二叉排序树设计

深碍√TFBOYSˉ_ 2022-06-02 21:10 115阅读 0赞

实验5 结合二叉树的二叉排序树设计  
  
  
【实验内容】  
二叉排序树采用二叉链表存储。写一个算法，删除结点值是X的结点。要求删除该结点后,此树仍然是一棵二叉排序树，并且高度没有增长（注：可不考虑被删除的结点是根的情况）。  
  
  
【实验目的】  
1、了解二叉排序树的定义，并结合二叉树的数据结构；  
2、掌握二叉排序树的排序方法。  
  
  
【实验步骤与要求】  
1、了解二叉排序树的定义，并结合二叉树的数据结构；

2、掌握二叉排序树的排序方法。

代码：

#include<stdio.h>
    #include<string.h>
    #include<stdlib.h>
    typedef struct Node
    {
        int data;
        struct Node *lchild,*rchild;
    }node;
    node* Build(int data)//创建一个头结点
    {
        node *p=malloc(sizeof(node));
        p->data=data;
        p->lchild=NULL;
        p->rchild=NULL;
        return p;
    }
    node* insert(node *p,int data)//插入一个数据
    {
        if(p==NULL)//遍历到空的时候创建一个节点
        {
            node *t=malloc(sizeof(node));
            t->data=data;
            t->lchild=NULL;
            t->rchild=NULL;
            return t;
        }
        if(p->data>data)//插入的值比当前节点的值更小，遍历左子树
        {
            if(p->lchild)//如果左子树存在就只是继续往左子树找
                insert(p->lchild,data);
            else//否则继续遍历左子树，但是此时会访问空节点，用该创建的节点去更新该节点的左子树
                p->lchild=insert(p->lchild,data);
        }
        else if(p->data<data)//同理
        {
            if(p->rchild)
                insert(p->rchild,data);
            else
                p->rchild=insert(p->rchild,data);
        }
        return NULL;//说明书中已有相同的值返回NULL
    }
    void bianli(node *p)//前序遍历树
    {
        if(p)
        {
            printf("%d ",p->data);
            bianli(p->lchild);
            bianli(p->rchild);
        }
    }
    node* find(node *p,int data)//查找数据为data节点的父节点的地址
    {
        if(p==NULL)
            return NULL;
        if(p->lchild&&p->lchild->data==data)//左子树存在并且值与data相等，返回本节点地址
        {
            return p;
        }
        else if(p->rchild&&p->rchild->data==data)//同样处理右子树
        {
            return p;
        }
        else//当该节点左右子树的值都与目标值不相等，继续递归遍历
        {
            node *temp=NULL;
            if(p->lchild)//左子树存在遍历左子树
                temp=find(p->lchild,data);
            if(temp==NULL)//左子树不存在或者没找到去右子树找
            {
                if(p->rchild)
                    temp=find(p->rchild,data);
            }
            return temp;
        }
    }
    node* delet(node *head,int data)//删除一个值为data的节点
    {
        node *p,*nparent,*d,*dparent;
        if(head==NULL)//特殊处理空树
        {
            printf("树为空\n");
            return head;
        }
        if(head->data==data)//特殊处理要删除的为头结点情况
        {
            if(head->lchild==NULL&&head->rchild==NULL)//当该树只存在头结点
            {
                free(head);
                head=NULL;
            }
            else if(head->lchild&&head->rchild==NULL)//该树只存在左子树
            {
                p=head;
                head=head->lchild;
                free(p);
            }
            else if(head->rchild&&head->lchild==NULL)//该树只存在右子树
            {
                p=head;
                head=head->rchild;
                free(p);
            }
            else//该树左右子树都存在，就取左子树中的最大值作为当前头结点，并删掉原来位置的节点
            {
                p=head->lchild;
                while(p->rchild)//找左子树中最大值
                {
                    p=p->rchild;
                }
                if(p==head->lchild)//如果找到的值就是左子树中的根节点，说明左子树根节点没有右子树，要特殊处理直接与他下一个节点相连
                {
                    head->data=p->data;
                    head->lchild=p->lchild;
                    free(p);
                }
                else//否则就将找到的最大值节点的左子树移到当前节点的右子树位置
                {
                    nparent=find(head,p->data);
                    head->data=p->data;
                    nparent->rchild=p->lchild;
                    free(p);
                }
            }
            return head;
        }
        nparent=find(head,data);//要删除的值不为头结点的情况，查找要删除值的父节点地址
        if(nparent==NULL)//找不到节点
        {
            printf("删除失败，找不到此节点!\n");
            return head;
        }
        int tag;
        if(nparent->lchild&&nparent->lchild->data==data)//判断该节点为父节点的左儿子还是右儿子
        {
            d=nparent->lchild;
            tag=0;//代表要删除的值为父节点的左儿子
        }
        else
        {
            d=nparent->rchild;
            tag=1;//为右儿子
        }
        if(d->lchild==NULL&&d->rchild==NULL)//假如要删除的节点为叶子节点，根据是父亲节点的左儿子还是右儿子直接删掉
        {
            free(d);
            if(!tag)
                nparent->lchild=NULL;
            else
                nparent->rchild=NULL;
        }
        else if(d->lchild&&d->rchild==NULL)//假如要删除的节点只有左儿子，那么将该节点父节点更新为该节点的左儿子
        {
            if(!tag)//判断该节点为父节点的哪个儿子
            {
                nparent->lchild=d->lchild;
                free(d);
            }
            else
            {
                nparent->rchild=d->lchild;
                free(d);
            }
        }
        else if(d->rchild&&d->lchild==NULL)//假如要删除的节点只有右儿子，那么将该节点父节点的右儿子更新为该节点的右儿子
        {
            if(!tag)
            {
                nparent->lchild=d->rchild;
                free(d);
            }
            else
            {
                nparent->rchild=d->rchild;
                free(d);
            }
        }
        else//要删除的节点左右儿子都有
        {
            p=d->lchild;
            while(p->rchild)//找左子树中最大值
            {
                p=p->rchild;
            }
            if(p==d->lchild)//如果找到的值就是左子树中的根节点，说明左子树根节点没有右子树，要特殊处理直接与他下一个节点相连
            {
                d->data=p->data;
                d->lchild=p->lchild;
                free(p);
            }
            else//否则就将找到的最大值节点的左子树移到当前节点的右子树位置
            {
                dparent=find(head,p->data);
                d->data=p->data;
                dparent->rchild=p->lchild;
                free(p);
            }
        }
        return head;//返回head，作用为当更新树的根节点时更新
    }
    int main()
    {
        node *head;
        int n,x,i,m;
        scanf("%d",&n);
        for(i=0;i<n;i++)
        {
            scanf("%d",&x);
            if(i==0)
                head=Build(x);
            else
                insert(head,x);
        }
        printf("生成树的前序遍历结果：\n");
        bianli(head);
        printf("\n请输入删除的组数:");
        scanf("%d",&m);
        for(i=0;i<m;i++)
        {
            scanf("%d",&x);
            printf("删除情况:\n");
            head=delet(head,x);
            if(head==NULL)
                printf("树为空\n");
            else
            {   bianli(head);
                printf("\n");
            }
        }
        return 0;
    }