删除二叉树中值为k的节点，并释放以他为根的子树的所有节点

为了解决根节点释放的问题，在func外部加了一层函数.

void func2(BiTree *T, ElemType x){
	if((*T)->date == x){
		func(*T,x);
		*T=NULL;
	}
	func(*T,x);
}

这个算法是释放树中所有节点内存的算法，但是有个问题，根节点无法被释放

//释放子树所有节点的内存
void func1(BiTree T){
	if(T){
		func1(T->lchild);
		T->lchild = NULL;
		func1(T->rchild);
		T->rchild = NULL;
		free(T);
	}
}

这个算法也有同样的问题，无法释放根节点

//删除以k为根的子树
void func(BiTree T, ElemType x){
	if(T){
		if(T->date == x){
			func1(T);
		}
		else{
			if(T->lchild && T->lchild->date == x){
				func1(T->lchild);
				T->lchild = NULL;
		    }
		    else func(T->lchild,x);
			if(T->rchild && T->rchild->date == x){
				func1(T->rchild);
				T->rchild = NULL;
			}
			else func(T->rchild,x);
		} 
	}
}

测试环境

#include 
#include
#include
#define maxsize 100
#define ElemType char 
//二叉树的创建序列 
//ab#df###c#e##
//abd##e##cf###
//ab##c## 
typedef struct BiNode{
	ElemType date;
	struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

BiNode* CreateBiTree();
void Traverse(BiNode *p);
void func(BiTree T, ElemType x);
void func2(BiTree *T, ElemType x);
void func1(BiTree T);

int main(){
	BiTree t = CreateBiTree();
	Traverse(t);
	func2(&t,'a');
	printf("n");
	Traverse(t);
	return 0;
}
void func2(BiTree *T, ElemType x){
	if((*T)->date == x){
		func(*T,x);
		*T=NULL;
	}
	func(*T,x);
}

//删除值为X的节点以及它为根的子树，并释放这些节点的空间 
void func(BiTree T, ElemType x){
	if(T){
		if(T->date == x){
			func1(T);
		}
		else{
			if(T->lchild && T->lchild->date == x){
				func1(T->lchild);
				T->lchild = NULL;
		    }
		    else func(T->lchild,x);
			if(T->rchild && T->rchild->date == x){
				func1(T->rchild);
				T->rchild = NULL;
			}
			else func(T->rchild,x);
		} 
	}
}

void func1(BiTree T){
	if(T){
		func1(T->lchild);
		T->lchild = NULL;
		func1(T->rchild);
		T->rchild = NULL;
		free(T);
	}
}
 
//用递归方法以中序遍历的方式创建二叉树 
BiNode* CreateBiTree(){
	BiNode *p;
	char a;
	scanf("%c",&a);
	if(a=='#')
	p=NULL;
	else{
		p=(BiNode *)malloc(sizeof(BiNode));
		p->date=a;
		p->lchild=CreateBiTree();
		p->rchild=CreateBiTree();
	}	
	return p;
}
//递归方法中序遍历二叉树 
void Traverse(BiNode *p){
	if(p==NULL){
		return;
	}
	else{
		printf("%c",p->date);
		Traverse(p->lchild);
		Traverse(p->rchild);
	}
	return;
}