假定二叉树采用二叉树存储结构，设计一个算法，删除该二叉树全部结点（不是叶子结点）

Question

假定二叉树采用二叉树存储结构，设计一个算法，删除该二叉树全部结点（不是叶子结点）

Answer 1

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

如果对你有帮助，可以点击我这个回答右上方的【采纳】按钮，给我个采纳吗，谢谢