c++ - 将节点添加到二叉搜索树c ++

Question

我正在构建一个二叉搜索树。现在我在向树中添加节点时遇到问题。

void BinaryTree::add(int value, Node* node) {
    if(!node)
        node = new Node(value);
    else if(node->key < value)
        this->add(value, node->rightNode);
    else if(node->key > value)
        this->add(value, node->leftNode);
}

当我打电话时，这段代码似乎不起作用：

BinaryTree test;
test.add(4, test.root);
test.add(1, test.root);
test.add(5, test.root);
test.add(2, test.root);
test.add(3, test.root);
test.add(7, test.root);
test.add(6, test.root);

在第一次 add 调用之后，树“test”的根仍然是空的。我该如何更改代码，以便在我调用 add 并且节点转到树的正确位置时更新它？非常感谢你！

Answer 1

您在Node *此处传递按值：

void BinaryTree::add(int value, Node* node) {

一种解决方案是通过引用传递：

void BinaryTree::add(int value, Node *& node) {
                                      ^

如果您按值传递，该函数只是接收到的副本，Node *因此对它的任何修改都不会反映在调用代码中。

此外，您可能想考虑当value等于时会发生什么key。

Answer 2

您递归地调用 add 函数，但我没有看到您实际上将 leftNode 或 rightNode 分配给传入的节点。