第19讲 动态查找表(10)

3. 二叉排序树的删除要删除二叉排序树中的p结点，分三种情况： p为叶子结点，只需修改p双亲f的指针 S f->lchild=NULL P Q 或 f->rchild=NULL p只有左子树或右子树 p只有左子树，用p的左孩子代替p; p只有右子树，用p的右孩子代替p; (1)(2) (3)(4)

p左、右子树均非空 沿p左子树的根C的右子树分支找到S,S的右子

树为空， 将S的左子树成为S的双亲Q的右子树，用S取代p; (5) 若C无右子树，用C取代p。 (6)