数据结构题目58：在二叉排序树中删除结点

题目：在二叉排序树中删除由p所指结点。

解题思路：这里讨论的在二叉排序树中删除一个结构是指仅删除指定结点，而不是把以结点为根结点的子树删掉。显然，删除指定结点以后的二叉树仍然要保持二叉排序树的性质。
删除二叉排序树的规则：
若要删除的结点由变量p指出，其双亲结点由变量q指出，则删除p所指的结点应该从下面4中情况分别考虑。

1. 若被删除结点为叶结点，则删除比较简单，可以直接进行删除（还要将其双亲结点相应的指针域置为null）。
2. 若被删除结点没有左子树（右子树存在），则可以用其右子树的根结点取代被删除结点的位置。
3. 若被删除结点没有右子树（左子树存在），则可以用其左子树的根结点取代被删除结点的位置。
4. 若被删除结点的左右子树均存在，则要找到被删除结点右子树中值最小的结点（不妨假设r指出该结点的位置），并用该结点取代被删除结点的位置。因为由r指出的结点一定没有左子树，所以用其右孩子来取代r所指结点的位置。

根据上述规则给出具体算法如下：

function deleteBST(T, p, q) {
    //这里q指p的父结点
    let r, s, flag=0
    if ( p.lchild==null ) {
        if ( p==T ) {
            T = p.rchild
        } else {
            r = p.rchild
            flag = 1
        }
    } else if ( p.rchild==null ) {
        if ( p==T ) {
            T = P.lchild
        } else {
            r = p.lchild
            flag = 1
        }
    } else {
        s = p
        r = s.rchild
        while ( r.lchild!=null ) {
            s = r
            r = r.lchild
        }
        r.lchild = p.lchild
        if ( s!=p ) {
            s.lchild = r.rchild
            r.rchild = p.rchild
        }
        if ( p==T ) {
            T = r
        } else {
            flag = 1
        }
    }
    if ( flag = 1 ) {
        if ( p==q.lchild ) {
            q.lchild = r
        } else {
            q.rchild = r
        }
    }
    p = null
}

测试：
这里用到创建二叉排序树sortTree(K)、中序遍历二叉树inOrder(BST)、查找二叉树某数据结点searchBST(BST, 20)。

let K = [5, 10, 5, 20, 17, 12, 19, 2]
var BST = sortTree(K)
inOrder(BST)
var p = searchBST(BST, 17)
var q = searchBST(BST, 20)
deleteBST(BST, p, q)
inOrder(BST)