c++ - 二叉搜索树删除

Question

我目前正在用 C++ 编写二叉搜索树，我已经到了必须编写删除/删除函数的阶段(使用递归方法，x = change(x) ).我有两个选择:

• 停在待删除节点的父节点；

• 到达要删除的节点，然后调用将
  返回父级

Approach 1: less expensive, more code

Approach 2: less code, more expensive

您认为哪种方法更好，为什么？

Answer 1

我不同意这是你仅有的两个选择。

我认为一个更简单的解决方案是询问每个节点是否应该删除它。如果它决定是，那么它将被删除并返回应该替换它的新节点。如果它决定否，则它会自行返回。

// pseudo code.
deleteNode(Node* node, int value)
{
    if (node == NULL) return node;

    if (node->value == value)
    {
        // This is the node I want to delete.
        // So delete it and return the value of the node I want to replace it with.
        // Which may involve some shifting of things around.
        return doDelete(node);
    }
    else if (value < node->value)
    {
        // Not node. But try deleting the node on the left.
        // whatever happens a value will be returned that
        // is assigned to left and the tree will be correct.
        node->left = deleteNode(node->left, value);
    }
    else
    {
        // Not node. But try deleting the node on the right.
        // whatever happens a value will be returned that
        // is assigned to right and the tree will be correct.
        node->right = deleteNode(node->right, value);
    }
    // since this node is not being deleted return it.
    // so it can be assigned back into the correct place.
    return node;
}