使用指向指针的指针

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; 是错误的。它 return 是垃圾。

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

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

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

编辑（由于您的评论）。在最后的 return 指令中，您需要 return 该指针的原始地址。如果不更改签名，您将 returning 指针副本的地址。随着签名的更改，函数的语法仍然将 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;
}

Answer 2

在findPosition、

return &node;

returns参数的地址。
在函数外取消引用它是未定义的。

不清楚为什么函数 returns 一个指针的地址。

您需要重新考虑您的删除策略；为了删除一个节点，您需要修改其父节点的子指针。

Answer 3

您的代码有未定义的行为：

return &node;

returns 函数参数的地址，这意味着对 findPosition 的 return 值的任何取消引用都会导致未定义的行为。

您可以通过确保 findPosition 引用指针而不是指针来避免此问题：

BSTNode **findPosition(BSTNode*& node, int value) {
    if (node == nullptr) {
        return &node;
    }
    ... // The rest of the code remains the same
}

请注意，尽管 return &node 的语法保持完全相同，但行为不同，因为引用指针的地址在函数退出后仍然有效。

注意：除非这是使用C++语法编写C代码的学习练习，否则请考虑重构代码以将BSTNode封装在BST中，并且将树功能公开为成员函数。

使用指向指针的指针

Working with pointer to pointer

c++

pointers

binary-search-tree