二叉排序树上的删除,相当于删去 有序序列上的一个记录,应保证删 除结点后,二叉排序树的特性不变 删除结点可有三种情况: 1若被删除结点*为叶子结点,即其p和 p均为空树。由于叶子结点的存在若不 破坏整株树的结构,则只需修改其父结 点的指针即可。 2若*p结点只有左子树p或只有右子树p 此时只要令P或pR直接成为其父结点*f
二叉排序树上的删除，相当于删去 有序序列上的一个记录，应保证删 除结点后，二叉排序树的特性不变。 删除结点可有三种情况： 1.若被删除结点*p为叶子结点，即其pL和 pR均为空树。由于叶子结点的存在若不 破坏整株树的结构，则只需修改其父结 点的指针即可。 2.若*p结点只有左子树pL或只有右子树pR， 此时只要令pL或pR直接成为其父结点*f
的左子树即可。可见,也不破坏二叉排序 1树的特性 3若*结点的左、右子树均不空,不能简 单处理,可有两种情况。例 P PR
的左子树即可。可见，也不破坏二叉排序 树的特性。 3.若*p结点的左、右子树均不空，不能简 单处理，可有两种情况。例： F P f p pL pR (a)
F p P C Q Q C S (b)
f F P C p cCL Q P RqS Q L S L S F C cCL S S f S L P R (b) (c)
F C C q Q Q (d)
f F S C p c CL Q PR q QL SL (d)
叉排序树中删除一个 结点的算法 DeleteBST(T key) t if(!t return False else i if(EQ(key, T->data. key)) return Delete(D) if(LT( key T->data. key)) return DeleteBST(T->lchild, key) else return DeleteBST(T->rchild, keyi S//DeleteBST
二叉排序树中删除一个 结点的算法 DeleteBST(T , key) { if(!T) return False; else { if(EQ(key, T->data.key)) return Delete(T); if(LT(key,T->data.key)) return DeleteBST(T->lchild,key); else return DeleteBST(T->rchild,key);} }//DeleteBST