c++ - 使用指向指针的指针

Question

我有一个 BinarySearchTree 结构:

struct BSTNode {
    int value;
    BSTNode *left = nullptr;
    BSTNode *right = nullptr;
};
struct BST {
    BSTNode *root = nullptr;
};

以及一些与这棵树一起工作的函数:

BSTNode **findPosition(BSTNode *node, int value) {
    if (value < node->value) {
        if (node->left) {
            return findPosition(node->left, value);
        } else {
            return &node->left;
        }
    }
    if (value > node->value) {
        if (node->right) {
            return findPosition(node->right, value);
        } else {
            return &node->right;
        }
    }
    return &node;
}
void remove(BSTNode** position, int value) {
    if ((*position)->left == nullptr && (*position)->right == nullptr) {
        delete (*position);
        *position= nullptr;
    }
}
void remove(BST &bst, int value) {
    BSTNode **position = findPosition(bst.root, value);
    if (*position != nullptr) {
        remove(position,value);
    }
}

void add(BSTNode *node, int value) {
    BSTNode **position = findPosition(node, value);

    BSTNode *newNode = new BSTNode;
    newNode->value = value;

    *position = newNode;
}

void add(BST &bst, int value) {
    if (!bst.root) {
        BSTNode *root = new BSTNode;
        root->value = value;
        bst.root = root;
    } else {
        add(bst.root, value);
    }
}

添加工作正常，但删除元素的工作很奇怪(现在它应该只对叶节点有效)。它只是将节点的值设置为零。我认为问题出在我对指针的使用上。

我做错了什么？

Answer 1

FindPosition 中的最后一个案例 return &node; 是错误的。它返回垃圾。

如果您将签名更改为 BSTNode **findPosition(BSTNode *&node, int value)

然后在许多用途中将修复最终返回。我没有(或者取决于您拥有什么与您发布的不能)检查所有用途以查看是否涵盖您使用 findPosition 的所有方式。

在不更改签名的情况下，您将返回调用参数的地址，该地址在可以使用返回值时无效。通过更改签名，相同的返回指令将返回正确的地址。 但是 签名更改表示 findPosition 与其调用者之间的契约(Contract)发生了重大变化，因此只有当所有调用者都接受该更改时，它才会起作用。否则，您将需要更大的改变。如果不更改其与调用者的契约(Contract)，仅对 findPosition 的任何更改都无法工作。

编辑(因为你的评论)。在最后的返回指令中，您需要返回该指针的原始地址。如果不更改签名，您将返回指针拷贝的地址。随着签名的更改，函数的语法仍然将 node 视为指针，但在其语义中隐藏了额外的间接级别。通过这种额外的间接级别，该指针的原始地址可用(并由 &node 计算)而不是拷贝地址。

此外(基于 dasblinkenlight 的回答)在您的版本的许多地方都需要对 NULL 指针进行测试，这很容易出错。如果将该测试推到 findPosition 的顶部，则需要它的地方更少，而且更健壮:

BSTNode **findPosition(BSTNode *&node, int value) {
    if ( node )
    {    
        if (value < node->value) {
            return findPosition(node->left, value);
        } 
        if (value > node->value) {
            return findPosition(node->right, value);
        }
    }
    return &node;
}