学步园

// 在ptr为根的二叉搜索树中删除x的结点，若删除成功则新结点通过ptr返回
template<class E, class K>
bool BST<E, K>::Remove(const K x, BSTNode<E, K>*& ptr)
{
    BSTNode<E, K>* tmp;
    if(ptr != NULL)
    {
        if(x < ptr->data)          // 左子树中执行删除
            Remove(x, ptr->left);
        else if(x > ptr->data)     // 右子树中执行删除
            Remove(x, ptr->right);
        else if(x == ptr->data && ptr->left != NULL && ptr->right != NULL)
        {
            tmp = ptr->right;
            while(tmp->left != NULL)
                tmp = tmp->left;
            ptr->data = tmp->data;
            Remove(tmp->data, ptr->right); // 递归处理
        }
        else
        {
            tmp = ptr;
            if(ptr->left == NULL)
                ptr = ptr->right;
            ptr = ptr->left;
            delete tmp;
            return true;
        }
    }
    return false;
}