} while∥借助中序遍历找到元素x及其前驱和后继结点 ifpt) return error;∥.找到待删结点 Delete BSTree(ptr),W删除ⅹ结点 if(pre&&pre->rtag) pre> rchild=suc;∥修改线索 eturn OK. 1//BSTree Delete key void Delete BSTree(BiThr Tree&Ty课本上给出的删除二叉排序树的子树T的算 法按照线索二叉树的结构作了一些改动 if(T-ltag&&r>rtag)∥结点无右子树此时只需重接其左子树 T-T->lchild else if((T->tag&&!I→rtag)/结点无左子树此时只需重接其右子树 T=T->rchild else if(T->ltag&&!I→rtag)/结点既有左子树又有右子树 while(!r->rtag S-l r=> rchild;∥我找到结点的前驱r和r的双亲s T->data=r>data;/用r代替T结点 f(s!=1 S->rchild=r->lchild else s-> Lchild=r> Child;∥重接r的左子树到其双亲结点上 q-r, please free(q,∥删除结点 i/Delete BSTree 分析本算法采用了先求出x结点的前驱和后继,再删除x结点的办法,这样修改线 索时会比较简单,直接让前驱的线索指向后继就行了如果试图在删除x结点的同 时修改线索,则问题反而复杂化了 9.38 void bs tree merge( BiTree&r, BiTree&S把二叉排序树S合并到T中 if(S->lchild) BSTree Merge(T, S->Child) ifS→ rchild) BSTree merge(T,S→> schild),∥合并子树 Insert Key(TS;/插入元素 i//BSTree Merge}//while //借助中序遍历找到元素 x 及其前驱和后继结点 if(!ptr) return ERROR; //未找到待删结点 Delete_BSTree(ptr); //删除 x 结点 if(pre&&pre->rtag) pre->rchild=suc; //修改线索 return OK; }//BSTree_Delete_key void Delete_BSTree(BiThrTree &T)//课本上给出的删除二叉排序树的子树 T 的算 法,按照线索二叉树的结构作了一些改动 { q=T; if(!T->ltag&&T->rtag) //结点无右子树,此时只需重接其左子树 T=T->lchild; else if(T->ltag&&!T->rtag) //结点无左子树,此时只需重接其右子树 T=T->rchild; else if(!T->ltag&&!T->rtag) //结点既有左子树又有右子树 { p=T;r=T->lchild; while(!r->rtag) { s=r; r=r->rchild; //找到结点的前驱 r 和 r 的双亲 s } T->data=r->data; //用 r 代替 T 结点 if(s!=T) s->rchild=r->lchild; else s->lchild=r->lchild; //重接 r 的左子树到其双亲结点上 q=r; }//else free(q); //删除结点 }//Delete_BSTree 分析:本算法采用了先求出 x 结点的前驱和后继,再删除 x 结点的办法,这样修改线 索时会比较简单,直接让前驱的线索指向后继就行了.如果试图在删除 x 结点的同 时修改线索,则问题反而复杂化了. 9.38 void BSTree_Merge(BiTree &T,BiTree &S)//把二叉排序树 S 合并到 T 中 { if(S->lchild) BSTree_Merge(T,S->lchild); if(S->rchild) BSTree_Merge(T,S->rchild); //合并子树 Insert_Key(T,S); //插入元素 }//BSTree_Merge