已知二叉树以二叉链表存储,编写算法完成:对于树中每个元素值为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);//入队 }} }
}