4.txt

清华大学出版社严蔚敏编著数据结构习题答案

6.45④ 编写递归算法：对于二叉树中每一个元素值为x
的结点，删去以它为根的子树，并释放相应的空间。

要求实现下列函数：
void ReleaseX(BiTree &bt, char x);
/* Delete all subtrees whose root is  */
/* the node which element value is x, */
/* then release correspondant space.  */

二叉链表类型定义：
typedef struct BiTNode {
    TElemType data;
    BiTNode  *lchild, *rchild;
} BiTNode, *BiTree;

void ReleaseX(BiTree &bt, char x)
/* Delete all subtrees whose root is  */
/* the node which element value is x, */
/* then release correspondant space.  */
{
 BiTree p;
 p=bt;
 if(p->data==x) p==NULL;
 if(p->lchild||p->rchild){
    if(p->lchild->data==x)
        p->lchild=NULL;
    if(p->rchild->data==x)
        p->rchild=NULL;
 }    
 if(p->lchild) ReleaseX(p->lchild,x);
 if(p->rchild) ReleaseX(p->rchild,x);
 
}