关于我使用C++编写二叉树时忘记给指针上引用而产生的空树这一档子事

  现在我欲意构造一颗二叉树，代码如下：

Insert(const elemType& ele, Node*& node)
{
    if (!node)
    {
        node = new Node(ele, nullptr, nullptr);
    }
    else if (ele < node->element)
    {
        this->Insert(ele, node->left);
    }
    else if (node->element < ele)
    {
        this->Insert(ele, node->right);
    }
}

  这里值得注意的是上面那个给节点指针加了个引用。按照我们一般的思路，指针指向一个地址，如果我们将其作为参数传入函数，也能用它来“提取”返回值：

int func(int* returnVal)；

int main()
{
    int a = 5;
    func(a);
}

  那么在构造二叉树时，传入指针本身为什么会导致空树？
  其实不难发现，我们传入的节点node，不仅被修改了值，还被new操作修改了地址。new先申请另一块地址空间，然后将地址交给当前的node。这样的行为就导致了空树。
  于是我们改用对指针引用的方式来构造，这种操作未出现空树得益于引用其本身是一个const pointer，它的地址无法被修改，申请空间也总是在当前位置申请。