C++-数据结构：关于二叉查找树(BinarySearchTree)的删除算法的疑问？

Question

Mark Allen Weiss的《数据结构与算法分析》第4章中讲到二叉查找树这种数据结构，关于删除的代码是这样的：

// 删除以t为根的BST中值为x的节点
void remove(int x, BinaryNode*& t)
{
    if ( t == NULL)
    {
        return ;
    }
    if (x < t->data)
    {
        remove(x, t->left);
    }
    else if (x > t->data)
    {
        remove(x, t->right);
    }
    // 左右都有节点的情况
    else if (t->left != NULL && t->right != NULL)
    {
        t->data = findMin(t->right)->data; // 右子树最小的节点
        remove(t->data, t->right);
    }
    else
    {
        BinaryNode* oldNode = t;
        t = (t->left != NULL) ? t->left : t->right);
        delete oldNode;
    }
}

Answer 1

http://zh.wikipedia.org/wiki/%E4%BA%8C%E5%85%83%E6%90%9C%E5%B0%8B%E6%A8%B9#.E5.9C.A8.E4.BA.8C.E5.8F.89.E6.9F.A5.E6.89.BE.E6.A0.91.E5.88.A0.E9.99.A4.E7.BB.93.E7.82.B9.E7.9A.84.E7.AE.97.E6.B3.95

若*p结点的左子树和右子树均不空。在删去*p之后，为保持其它元素之间的相对位置不变，可按中序遍历保持有序进行调整，可以有两种做法：其一是...；其二是令*p的直接前驱（in-order predecessor）或直接后继（in-order successor）替代*p，然后再从二叉查找树中删去它的直接前驱（或直接后继）。