数据结构考研分类复习真题 第六章 答案 (五)[31]

[题目分析] 删除以元素值x为根的子树只要能删除其左右子树就可以释放值为x的根结点因此宜采用后序遍历删除值为x结点意味着应将其父结点的左(右)子女指针置空用层次遍历易于找到某结点的父结点本题要求删除树中每一个元素值为 x的结点的子树因此要遍历完整棵二叉树

void DeleteXTree(BiTree bt) //删除以bt为根的子树

{DeleteXTree(bt>lchild); DeleteXTree(bt>rchild);//删除bt的左子树右子树

free(bt); }// DeleteXTree //释放被删结点所占的存储空间

void Search(B:Tree btElemType x)

//在二叉树上查找所有以x为元素值的结点并删除以其为根的子树

{BiTree Q[];//Q是存放二叉树结点指针的队列容量足够大

if(bt)

{if(bt>data==x) {DeleteXTree(bt); exit();}//若根结点的值为x则删除整棵树

{QueueInit(Q); QueueIn(Qbt);

while(!QueueEmpty(Q))

{p=QueueOut(Q);

if(p>lchild) // 若左子女非空

if(p>lchild>data==x) //左子女结点值为 x应删除当前结点的左子树

{DeleteXTree(p>lchild); p>lchild=null;} //父结点的左子女置空

else Enqueue (Qp>lchild);// 左子女入队列

if(p>rchild) // 若右子女非空

if(p>rchild>data==x) //右子女结点值为 x应删除当前结点的右子树

{DeleteXTree(p>rchild); p>rchild=null;} //父结点的右子女置空

else Enqueue (Qp>rchild);// 右子女入队列

}//while

}//if(bt) }//search

[] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] [] []