这里的函数参数为何使用引用的指针？

Question

该函数是关于二叉查找树的，代码片段如下：

void insert(const Comparable & x, TreeNode<Comparable> *&r)
    {
        if (r == NULL)
        {
            r = new TreeNode<Comparable>(x, NULL, NULL);
        }
        else if (x < r->element)
        {
            insert(x, r->leftChild);
        }
        else if (x > r->element)
        {
            insert(x, r->rightChild);
        }
        else
            ;
    }
    

该函数主要负责二叉树节点的插入。

我的问题是这里的函数参数为什么使用TreeNode<Comparable> *&r的形式，即引用的指针？而我经过测试如果直接使用指针作为参数的话，插入操作是无法正常运行的。

Answer 1

一般传入引用是为了返回修改后的值，你看看r在函数里有没有被修改，明显修改了，给了一个地址嘛，你再去看看是哪个地方用的这个函数，看看传入的r接下来做的什么就知道了。

Answer 2

由于我已经自己找到了问题的答案，所以我就自问自答了，如有错误欢迎盖楼补充！

大家都知道，引用是c++中的概念，它是已定义的变量的别名，相当于直接使用该变量。另外还需要知道的是，函数在传递参数的时候，会创建实参的副本，而不是直接使用实参本身。

知道这些之后，就很好理解为什么这里的形参使用引用的指针了。

如果这里形参改为指针变量的话，由于函数传参，所以最后在函数中得到的是个指针副本，函数中操作的并不是真正的父亲节点，函数结束之后，指针就被回收了，最终实参没有发生任何变化；而使用引用就不同了，它使得函数内得到的是实参本身，因此函数直接操作的就是实参本身，即父亲节点。

另外，这里换成指针的指针也可以达到同样的效果。

Answer 3

首先，引用其实可以理解为指针，比如下面等价的代码

int a;
void set(int &a){ a = 10;}
set(a);
//===============
void set(int *a){ &a = 10;}
set(&a);

只是用引用代码上更简单一些。

在 C 语言中，链表，树等，经常用指向指针的指针也就是二级制作来表示，这样可以带来一些便利。
于是，root指向树根节点，&root表示这棵树，p->left指向左子树，&(p->left)表示左子树，这样root和p->left的"地位"是一样的。

这样会带来递归上的一些方便，比如你的代码insert(x, &(r->leftChild))(写成上述的第二种形式)，如果r->leftChild==NULL那么就新创建一个节点，在函数内赋值给r->leftChild。如果不用二级指针，就要：

if(r->leftChild==NULL){
  r->leftChild = new Node(x);
}else{
  insert(x,r->leftChild)
}

https://github.com/zonxin/exp...