欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

C语言实现二叉树的插入和删除(实例教程)

程序员文章站 2022-09-28 16:53:04
二叉树的插入删除: //首先介绍二叉树的插入: //首先需要明白插入的规则:每个建好的结点p都需要从跟结点开始与根结点相比较数据域,如果根结点的数据域小于结点p,则接着将结...

二叉树的插入删除:

//首先介绍二叉树的插入:
//首先需要明白插入的规则:每个建好的结点p都需要从跟结点开始与根结点相比较数据域,如果根结点的数据域小于结点p,则接着将结点p与根结点的右子树相比较,否则p将与根结点的左子树相比较;
//继续往下类推,一直到最后一次比较完后,指针head的左子树或者右子树为空,退出循环(也就是,当到达叶子结点时),因为每次进入循环都要把head结点赋给parent双亲结点,所以这个结点也表示双亲结点;
//之后将双亲结点parent与p->data(也就是key的值)比较,如果双亲结点大,那么,p为双亲结点的左子树,否则为双亲结点的右子树;

C语言实现二叉树的插入和删除(实例教程)

//介绍二叉树的删除:
//二叉树的删除有三种情况:
//1>删除的结点为叶子结点;
//删除节点是叶节点,即没有子节点,或者说左右子节点都是NULL。这种情况下,只需要把删除节点的父节点中对应的指针指向NULL即可。然后释放掉删除节点的空间;
//2>删除的结点有左子树或者右子树,只能有一个;
//删除节点有一个子节点(左子节点或右子节点),这种情况下,把删除节点的父节点中对应的指针指向删除节点的子节点即可。然后释放掉删除节点的空间;
//3>删除的结点左右子树都有,两个都有;
//删除节点有两个子节点,这种情况下,必须要找到一个替代删除节点的替代节点,并且保证二叉树的排序性。根据二叉树的排序性,可知替代节点的键值必须最接近删除节点键值。比删除节点键值小的所有键值中最大那个,或者是比删除节点键值大的所有键值中最小的那个,是符合要求的。这两个键值所在的节点分别在删除节点的左子树中最右边的节点,删除节点右子树中最左边的节点;

//以图例的形式表示第三种方式的删除;

第三种方式的删除: 最重要的是找到删除结点以及它的父结点;

1>找到删除节点以及它的父节点在删除节点的左子树中,向下向右遍历,找到替代节点以及它的父节点;

2>删除节点的父节点中对应的指针指向替代节点;

3>替代节点中的右子节点指针指向删除节点的右子树;

4>如果替代节点的父节点不是删除节点,则将替代节点的左子节点指针指向删除节点的左子树,并且替代节点的父节

点中对应的指针指向替代节点的左子节点;

5>释放删除节点的空间;

注意:

1>第二步中找到的替代节点,可能会有左子树,但一定没有右子树。

2>第五步要判断替代节点的父节点不是删除节点后,才将替代节点的左子节点指针指向删除节点的左子树,否则

会出现替代节点左子节点指针指向自己的情况,从而丢失替代节点的左子树。

第三种方式的图画显示:两种方式;

C语言实现二叉树的插入和删除(实例教程)

C语言实现二叉树的插入和删除(实例教程)

#include<stdio.h>  
#include<stdlib.h>  
#define N 9  
int a[]={3,2,5,8,4,7,6,9,10};  
  
//二叉树的结点类型;  
typedef struct tree  
{  
    int data;  
    struct tree *lchild;  
    struct tree *rchild;  
}BitTree;  
  
//在二叉排序树中插入查找关键字可以;  
void Inserter(BitTree *bt,int key)    
{  
    BitTree *parent;   //表示双亲结点;  
    BitTree *head = bt;  
    BitTree *p=(BitTree *)malloc(sizeof(BitTree));  
    p->data=key;   //保存结点数据;  
    p->lchild=p->rchild=NULL;  //左右子树置空;  
      
    //查找需要添加的父结点,这个父结点是度为0的结点;  
    while(head)   
    {  
        parent=head;  
        if(key<head->data)   //若关键字小于结点的数据;  
            head=head->lchild; //在左子树上查找;   
        else   //若关键字大于结点的数据;  
            head=head->rchild;  //在右子树上查找;  
    }  
    //判断添加到左子树还是右子树;  
    if(key<parent->data)   //小于父结点;  
        parent->lchild=p;    //添加到左子树;  
    else    //大于父结点;  
        parent->rchild=p;   //添加到右子树;  
}  
  
//n个数据在数组data[]中;  
BitTree *Createer(BitTree *bt,int data[],int n)    
{  
    bt=(BitTree *)malloc(sizeof(BitTree));  
    bt->data=data[0];  
    bt->lchild=bt->rchild=NULL;  
    for(int i=1;i<n;i++)  
        Inserter(bt,data[i]);  
    return bt;  
}  
  
//中序遍历;  
void PreOrder(BitTree *bt)  
{  
    if(bt)  
    {  
        PreOrder(bt->lchild);  
        printf("%d ",bt->data);  
        PreOrder(bt->rchild);  
    }  
}  
  
//删除结点;  
void Deleteer(BitTree *bt,int key)  
{  
    BitTree *L,*LL;    //在删除左右子树都有的结点时使用;  
    BitTree *p=bt;  
    BitTree *parent=bt;  
    int child=0;  //0表示左子树,1表示右子树;  
    if(!bt)    //如果排序树为空,则退出;  
        return ;  
    while(p)  //二叉排序树有效;  
    {  
        if(p->data==key)  
        {  
            if(!p->lchild&&!p->rchild)  //叶结点(左右子树都为空);  
            {  
                if(p==bt)  //被删除的结点只有根结点;  
                    free(p);  
                else if(child==0)  
                {  
                    parent->lchild=NULL;  //设置父结点左子树为空;  
                    free(p);   //释放结点空间;  
                }  
                else   //父结点为右子树;  
                {  
                    parent->rchild=NULL;  //设置父结点右子树为空;  
                    free(p);  //释放结点空间;  
                }  
            }  
  
            else if(!p->lchild)  //左子树为空,右子树不为空;  
            {  
                if(child==0)    //是父结点的左子树;  
                    parent->lchild=p->rchild;  
                else      //是父结点的右子树;  
                    parent->rchild=p->rchild;  
                free(p);  //释放被删除的结点;  
            }  
  
            else if(!p->rchild)  //右子树为空,左子树不为空;  
            {  
                if(child==0)  //是父结点的左子树;  
                    parent->lchild=p->lchild;  
                else      //是父结点的右子树;  
                    parent->rchild=p->lchild;  
                free(p);  //释放被删除的结点;  
            }  
  
            else  
            {  
                LL=p;  //保存左子树的结点;  
                L=p->rchild;  //从当前结点的右子树进行查找;  
                if(L->lchild)  //左子树不为空;  
                {  
                    LL=L;  
                    L=L->lchild;   //查找左子树;  
                    p->data=L->data;  //将左子树的数据保存到被删除结点;  
                    LL->lchild=L->lchild;  //设置父结点的左子树指针为空;  
                    for(;L->lchild;L=L->lchild);  
                    L->lchild=p->lchild;  
                    p->lchild=NULL;  
                }  
                else  
                {  
                    p->data=L->data;  
                    LL->rchild=L->rchild;  
                }  
            }  
            p=NULL;  
        }  
  
        else if(key<p->data)  //需删除记录的关键字小于结点的数据;  
        {  
            //要删除的结点p是parent的左子树;  
            child=0;  //标记在当前结点左子树;  
            parent=p;//保存当前结点作为父结点;  
            p=p->lchild;  //查找左子树;  
        }  
  
        else  //需删除记录的关键字大于结点的数据;  
        {  
            //要删除的结点p是parent的右子树;  
            child=1;  //标记在当前结点右子树查找;  
            parent=p;  //保存当前结点作为父结点;  
            p=p->rchild;  //查找右子树;  
        }  
    }  
}  
  
int main(void)  
{  
    BitTree *bt;  //保存二叉排序树根结点;  
    printf("数组数据为:\n");  
    for(int i=0;i<N;i++)  
        printf("%d ",a[i]);  
    printf("\n\n");  
  
    bt=Createer(bt,a,N);  
    printf("遍历后的二叉排序树为(中序遍历输出):\n");  
    PreOrder(bt);  
    printf("\n\n\n");  
  
    printf("     **将数据8插入到二叉树中**\n\n");  
    printf("插入后的二叉树为(中序遍历输出):\n");  
    Inserter(bt,8);  
    PreOrder(bt);  
    printf("\n\n\n");  
      
    printf("     **将数据5从二叉树中删除**\n\n");  
    printf("删除后的二叉树为(中序遍历输出):\n");  
    Deleteer(bt,5);   //删除拥有左右子树的结点有问题;  
    PreOrder(bt);  
    printf("\n");  
    return 0;  
}  

//输出结果截图:

C语言实现二叉树的插入和删除(实例教程)