递归中的指针未按预期工作

Question

我正在尝试插入 BST；

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

    Node(int d)
        :left(nullptr), right(nullptr), data(d)
    {
    }
};


void Insertion(Node* head, int value)
{
    if (!head)
    {
        head = new Node(value);
        return;
    }

    if (head->data > value)
        Insertion(head->left, value);
    else
        Insertion(head->right, value);
}

void printTree(Node* root)
{
    if (!root)
    {
        return;
    }

    cout << root->data << " "; //20 15 10 18 30 35 34 38
    printTree(root->left);
    printTree(root->right);

}

int main()
{
    Node *root = new Node(20);
    Insertion(root, 15);
    Insertion(root, 30);
    Insertion(root, 10);
    Insertion(root, 18);
    Insertion(root, 35);
    Insertion(root, 34);
    Insertion(root, 38);

    printTree(root);

}

我的 Insertion 方法无法正确插入。但是，如果我像下面这样使用它，它就会起作用；

Node* Insertion(Node* head, int value)
{
    if (!head)
    {
        return (new Node(value));   
    }

    if (head->data > value)
        head->left = Insertion(head->left, value);
    else
        head->right = Insertion(head->right, value);

    return head;
}

我不确定 Node* head 是否是我发送的副本，如果是，是否可以在不使用 Node return 类型的情况下创建相同的函数，但是通过通过引用传递 head?

Answer 1

您可以像评论中提到的那样使用对指针的引用，或者您也可以像下面这样使用指向指针的指针：

void Insertion(Node** head, int value)
{
    if (!(*head))
    {
        *head = new Node(value);
        return;
    }

    if ((*head)->data > value)
        Insertion(&(*head)->left, value);
    else
        Insertion(&(*head)->right, value);
}

并像这样调用函数：

Node *root = new Node(20);
Insertion(&root, 15);

在您的代码中，您只是将地址复制到函数参数（指针变量）。在函数内部，您正在为其分配另一个地址。但在这种情况下，这不是您想要的。您需要更改您传递的地址的内容。

递归中的指针未按预期工作

Pointers in recursion not working as expected

c++

recursion

pointers

reference

pass-by-reference