c++ - C++ 中的二叉搜索树

Question

我正在学习 C++ 语言，并且正在尝试编写 BST，但是出了点问题。 我尝试将元素添加到空树中，root 为 NULL，但添加元素后 root 仍然是 NULL，尽管添加成功(我在 Debug模式下看到它，节点设置为 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;
}

Answer 1

当您将指针传递给函数时，您创建了指针的本地版本。这个局部变量 (node) 确实指向与您传递的外部指针相同的内存。但是，任何更改此变量(不是它指向的内存，而是指针变量本身)的尝试都只会更改局部变量。

所以你的 node 指向与你的 tree 相同的内存位置，但是 node 变量本身不等于 tree 变量，因此您的更改在外部函数中是不可见的。

这听起来很复杂，对不起，但它和下面的完全一样:

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

当然在这种情况下 var 不会改变，在函数内部改变的是 a。

要解决此问题，请传递对指针的引用而不是指针本身:

void addToNode(Node*& node, int value)