5)二叉排序树的删除 要求:删除一个结点后,仍然保持二叉排序树 的有序性 删除结点的算法: (1)确定被删除结点: A.有没有被删除的结点; B.若有,则确定被删除的结点是根结点还 是一般结点 (2)如果被删除结点是根结点,则调用删除根结点的 算法; (3)如果被删除结点是一般结点,则调用删除一般结 点的算法
v 要求：删除一个结点后，仍然保持二叉排序树 的有序性 删除结点的算法： （1）确定被删除结点： A. 有没有被删除的结点； B. 若有，则确定被删除的结点是根结点还 是一般结点 （2）如果被删除结点是根结点，则调用删除根结点的 算法； （3）如果被删除结点是一般结点，则调用删除一般结 点的算法
删除二叉排序树的根结点的算法 (1)根结点有左右子树的情况下,选择根结点的 左子树中的最大结点为新的根结点;/域者是 右子树中的最小结点为新的根结点; 最大结点—中序遍历 (2)如果根结点没有左子树,则以右子树的根 结点作为新的根结点; (3)如果根结点没有右子树,则以左子树的根 结点作为新的根结点
（1） 根结点有左右子树的情况下，选择根结点的 左子树中的最大结点为新的根结点；/或者是 右子树中的最小结点为新的根结点； ** 最大结点——中序遍历 （2）如果根结点没有左子树，则以右子树的根 结点作为新的根结点； （3）如果根结点没有右子树，则以左子树的根 结点作为新的根结点
删除二叉排序树中一般结点的算法 (1)若被删除结点P有左、右子树,则按照中序遍历找其 左子树中的最大结点,以此最大结点的值代替P结点 的值,然后删除此最大结点(如同删除根结点) (2)若被删除结点P没有左子树,则把结点P的右子树的 全部挂接在P的双亲上,且位置是P在其双亲中原来 的位置 (3)若被删除结点P没有右子树,则把结点P的左子 树的全部挂接在P的双亲上,且位置是P在其双 亲中原来的位置 删除二叉排序树中叶子结点的算法 只需将其双亲结点指向它的指针清零,再释放它即可
（1） 若被删除结点P有左、右子树，则按照中序遍历找其 左子树中的最大结点，以此最大结点的值代替P结点 的值，然后删除此最大结点（如同删除根结点） （2）若被删除结点P没有左子树，则把结点P的右子树的 全部挂接在P的双亲上，且位置是P在其双亲中原来 的位置 （3）若被删除结点P没有右子树，则把结点P的左子 树的全部挂接在P的双亲上，且位置是P在其双 亲中原来的位置 只需将其双亲结点指向它的指针清零，再释放它即可
删除二叉排序树中结点的算法 —寻找被删除的结点 int Delete BsT( BiTree &T, int key) BiTree p, f; p=T; f-NULL; while(p) i if (p->data key = key)( delNode (t, p, f); return(1);] else if (p->data, key >key)( f-p; p=p->lchild; j else ( f-p; p=p->rchild; j return(0)
——寻找被删除的结点
删除二叉排序树中结点的算法——删除找到的结点 void delNode( bitree &T, BiTree p, BiTree f) I BiTree s,q; int tag tag=0; if(p->lchild) s=p->rchild; else if (p->rchild)s=p->lchild; else( q=p; s=p->lchild; while(s->rchild)( q=s; s=s->rchild; j p->data=s->data; if(q==p)q->lchild=s->lchild; else g->rchild=s->lchild; free(s); tag=1;}∥左右孩子中至少有一个不存在 if ( tag) if (!f)T=s;; else if(f->lchild==p)f->lchild=s else f->rchild=s free(p); return
{ } ——删除找到的结点