2

我正在学习 C++ 语言，并且正在尝试编写 BST，但出现了问题。我尝试将元素添加到空树，root 为 NULL，但在添加元素后，root 仍然为 NULL，尽管添加成功（我在调试模式下看到它，节点设置为 tmp）。我不知道为什么会这样。

struct Node
{
    int data;
    Node* left;
    Node* right;
};

struct Tree
{
    Node* root;
};

Tree createTree()
{
    Tree tmp;
    tmp.root = NULL;
    return tmp;
}

void addToNode(Node* node, int value)
{
    Node* tmp = new Node;
    tmp->data = value;
    tmp->left = NULL;
    tmp->right = NULL;
    if(node == NULL)
        node = tmp;
    else if(value >= node->data)
        addToNode(node->right, value);
    else
        addToNode(node->left, value);
}

void add(Tree* tree, int value)
{
    addToNode(tree->root, value);
}

int _tmain(int argc, _TCHAR* argv[])
{
    Tree tree = createTree();
    add(&tree, 10);
    printf("%d", tree.root->data);
    scanf("%*s");
    return 0;
}
4

3 回答 3

3

When you are passing your pointer into the function, you create a local version of the pointer. This local variable (node) does indeed point into the same memory that the outer pointer you were passing. However, any attempt to change this variable (not the memory it points to, but the pointer variable itself) will only change the local variable.

So your node points to the same memory location as your tree, but the node variable itself isn't equal to the tree variable, so your changes are not visible from the outer function.

It sounds complicated, sorry, but it's exacly the same thing as in this:

void foo( int a )
{
    a++;
}
int main()
{
    int var = 5;
    foo( var );
    std::cout << var;
}

Of course in this case the var will not change, it's the a that is being changed inside the function.

To fix the issue, pass a reference to the pointer instead of the pointer itself:

void addToNode(Node*& node, int value)
于 2012-11-08T12:04:14.207 回答
3

addToNode在您分配给的函数中node，该分配在函数调用中不可见，addToNode因为node它是一个局部变量。

您应该将其作为参考传递：

void addToNode(Node*& node, int value)
{
    ...
}
于 2012-11-08T11:58:27.957 回答
1

Joachim already beat me to the answer, but I'll add this observation in anyway.

Your code leaks memory.

void addToNode(Node* node, int value)
{
    Node* tmp = new Node;
    tmp->data = value;
    tmp->left = NULL;
    tmp->right = NULL;
    if(node == NULL)
        node = tmp;
    else if(value >= node->data)
        addToNode(node->right, value);
    else
        addToNode(node->left, value);
}

Every call to addToNode creates a new Node instance in tmp, but if the parameter Node* node is not NULL, this new Node is not deleted and does not become accessible by the rest of the application.

There are a number of ways to avoid this. The simplest would be to check if node is NULL before creating a new instance.

于 2012-11-08T12:04:00.613 回答