C++、二叉树、指针引用

发布于 17 天前  3 次阅读


关于我使用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,它的地址无法被修改,申请空间也总是在当前位置申请。