C语言实现二叉树的插入和删除

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

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

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

                1>找到删除节点以及它的父节点在删除节点的左子树中，向下向右遍历，找到替代节点以及它的父节点；
                2>删除节点的父节点中对应的指针指向替代节点；
                3>替代节点中的右子节点指针指向删除节点的右子树；
                4>如果替代节点的父节点不是删除节点，则将替代节点的左子节点指针指向删除节点的左子树，并且替代节点的父节
                    点中对应的指针指向替代节点的左子节点；
                5>释放删除节点的空间；
        注意：
                1>第二步中找到的替代节点，可能会有左子树，但一定没有右子树。
                2>第五步要判断替代节点的父节点不是删除节点后，才将替代节点的左子节点指针指向删除节点的左子树，否则
                    会出现替代节点左子节点指针指向自己的情况，从而丢失替代节点的左子树。
        第三种方式的图画显示：两种方式；

#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; }

//输出结果截图：