二进制搜索树插入带参数参考

Question

我写了以下功能来练习二进制搜索树插入：

void RecursiveInsert(struct Node* &root, int key) {
    if (root == nullptr) {
        root = new Node(key);
        return;
    } else if (root->key > key) {
        RecursiveInsert(root->left, key);
    } else {
        RecursiveInsert(root->right, key);
    }
}

它有效，但我不明白为什么要通过引用根。有人知道为什么吗？

Answer 1

您希望该功能能够更改您要插入的节点的父节点中存储的指针，以便指向新节点而不是nullptr。如果您不使用通过传递，那么所有功能都可以做的就是修改指针的本地副本，而实际树中的指针将不会更改。

例如，假设您正在查看一个节点，并且您想将新节点插入该节点的合适孩子。

someNode[key: 123, left: nullptr, right: nullptr]

该函数将以right指针作为参数来调用。您希望该功能能够更改节点，因此看起来像这样：

someNode[key: 123, left: nullptr, right: newNode]

如果您不通过引用传递，则该函数将无法更改节点的right指针，因为它仅给出了副本。使用引用允许该函数实际修改存储在被用作参数的节点中的指针。