二叉树递归插入用指针指向指针

Question

void insert(node ** tree, int val)
{
    node *temp = NULL;
    if(!(*tree))
    {
        temp = (node *)malloc(sizeof(node));
        temp->left = temp->right = NULL;
        temp->data = val;
        *tree = temp;
        return;
    }
    if(val < (*tree)->data)
    {
        insert(&(*tree)->left, val);
    }
    else if(val > (*tree)->data)
    {
        insert(&(*tree)->right, val);
    }
}

这个函数使用指向指针node ** tree的指针来表示二叉树的头。我在许多教程和网站上遇到了同样的方法。我想知道为什么每个人都坚持使用指针指向指针，为什么不只是"节点*树"。我认为即使指向树头的指针也能很好地完成这项工作，并且只使用指向树头的指针，递归调用将如下所示(如果我错了，请纠正我):

insert(tree->left, val); // assuming definisiton as void insert(node *tree, int val);

或

insert(tree->right, val); // assuming definisiton as void insert(node *tree, int val);

如果我理解错了，请纠正我。我是一个新手。谢谢。

Answer 1

请记住，在C中参数是通过值传递的，这意味着您作为参数传递的表达式的值被复制到函数中。因此，如果你在一个函数中改变了一个参数，你只改变了副本，而这个改变对调用者来说是不可见的(也就是说，改变丢失了)。

要克服这个问题，可以通过传递指针来模拟通过引用传递。如果你想改变一个指针，你必须传递一个指针给这个指针。

如果您查看insert函数，您将看到它在*tree为NULL时(即没有节点)分配给指针。如果不将指针传递给指向节点的指针，这将无法工作。

---

愚蠢的例子:

#include <stdio.h>
void func1(const char *s)
{
    s = "hello from func1";
}
void func2(const char **s)
{
    *s = "hello from func2";
}
int main(void)
{
    const char *s1 = "foo";
    const char *s2 = "bar";
    func1(s1);   /* Passing pointer by value */
    func2(&s2);  /* Passing pointer by "reference" */
    printf("s1 = "%s"n", s1);
    printf("s2 = "%s"n", s2);
}

上面的小示例程序将输出

<>之前S1 = "foo"S2 = "hello from func2"

Answer 2

这是因为tree可以为空(NULL)。在这种情况下，您可以设置外部指针，使其指向新的根目录。

node *root = NULL;
insert(root, 10);

Answer 3

传递给函数的两种类型:

1。Pass by value =创建该值的副本。一旦函数终止，对该值的任何更改都将丢失。

2。通过引用传递=不创建副本，而是指向被传递的值。如果发生了更改，则值将更改。

双指针(**)指向单指针(*)的地址。因此，如果将单指针传递给函数，则需要使用双指针来更改单指针的值(地址)。