二叉排序树的删除 要删除二叉排序树中的p结点,分三种情况: ●p为叶子结点,只需修改p双亲的指针f> child=NULL f->rchildENULL ●p只有左子树或右子树 ◆p只有左子树,用p的左孩子代替p(1)(2) ◆p只有右子树,用p的右孩子代替p(3)(4) ●p左、右子树均非空 ◆沿p左子树的根C的右子树分支找到S,S的右子树为空, 将S的左子树成为S的双亲Q的右子树,用S取代p(5) ◆若C无右子树,用C取代p (6)❖二叉排序树的删除 要删除二叉排序树中的p结点，分三种情况： ⚫p为叶子结点，只需修改p双亲f的指针f->lchild=NULL f->rchild=NULL ⚫p只有左子树或右子树 ◆p只有左子树，用p的左孩子代替p (1)(2) ◆p只有右子树，用p的右孩子代替p (3)(4) ⚫p左、右子树均非空 ◆沿p左子树的根C的右子树分支找到S，S的右子树为空， 将S的左子树成为S的双亲Q的右子树，用S取代p (5) ◆若C无右子树，用C取代p (6)