删除二叉树中以x为根节点的子树（包括根结点）

已知二叉树以二叉链表存储，编写算法完成：对于树中每个元素值为x的结点，删除以它为根的子树，并释放相应的空间。

思想：

删除二叉树采用后序遍历。先删除左子树，然后右子树，最后根。

利用层次遍历来删除所有以x为根结点的子树，并利用队列来进行辅助。不为x，则左右孩子入队，否则删除。直到队列为空。

代码：

void DeleteBTree(BTree T){//删除二叉树，后序遍历 if(T!=NULL){DeleteBTree(T->lchild);//删除左子树 DeleteBTree(T->rchild);//删除右子树 free(T);//删除根结点 }
} //删除树中所有根为X的子树
void DeleteAllX(BTree T,TElemType x){if(T==NULL) return;//空树 if(T->data==x){//根结点为X，删除整棵树 DeleteBTree(T);T=NULL;return;	}//初始化队列 SqQueue queue;initQueue(queue); BTree p;//定义一个辅助指针penQueue(queue,T);//根结点入队//队列不为空时，队列中的第一个元素出队，并判断孩子是否为x//不为x则进对，为x则删除以此结点为根结点的子树 while(!queueEmpty(queue)){deQueue(queue,p);//出队 if(p->lchild != NULL){//做孩子 if(p->lchild->data == x){DeleteBTree(p->lchild);//删除 p->lchild = NULL}else{enQueue(queue,p->lchild);//入队 }} if(p->rchild != NULL){//右孩子 if(p->rchild->data == x) {DeleteBTree(p->rchild);//删除 p->rchild = NULL}else{enQueue(queue,p->rchild);//入队 }} } 
}