C++：指针与指针的指针在二叉树中插入节点

Question

我正在创建一个函数来在二叉树中插入一个元素，首先，我在 Visual Studio 2012 年做了以下操作：

void Insert(Nodo *root, int x){
   if(root == NULL){
      Nodo *n = new Nodo();
      n->value = x
      root = n;
      return;
   }
   else{
      if(root->value > x)
         Insert(&(root)->left, x);
      else
         Insert(&(root)->right, x);
   }
}

但同样的代码在 Dev-C++ 中不起作用，我需要使用 Pointer of Pointer 来使其工作，如下所示：

void Insert(Nodo **root, int x){
   if(*root == NULL){
      Nodo *n = new Nodo();
      n->value = x
      *root = n;
      return;
   }
   else{
      if((*root)->value > x)
         Insert(&(*root)->left, x);
      else
         Insert(&(*root)->right, x);
   }
}

有人知道为什么会这样吗？

Answer 1

第一个代码不应该编译。事实上，它不能在 MSVC 2013 下编译。

为什么？

你的节点结构应该是这样的：

struct Nodo {
    int value; 
    Nodo*left, *right;  // pointer to the children nodes
};

这意味着 (root)->left 是 Nodo* 类型。因此 &(root)->left 是 Nodo** 类型，它与 Nodo* 参数不兼容。

无论如何，在你的插入函数中，你肯定想改变树。但是，如果您执行以下操作： root = n; 您将只更新根参数（指针）。一旦您离开该功能，此更新就会丢失。在这里，您当然想要更改根节点的内容或者更可能是指向根节点的指针。

在第二个版本中，您将指向节点的指针地址作为参数传递，然后在必要时更新该指针（预期行为）。

备注

第一个版本可能是 "saved"，如果你想通过参考：

void Insert(Nodo * &root, int x){  // root then refers to the original pointer 
   if(root == NULL){   // if the original poitner is null... 
      Nodo *n = new Nodo();
      n->value = x
      root = n;        // the orginal pointer would be changed via the reference    
      return;
   }
   else{
      if(root->value > x)
         Insert(root->left, x);   // argument is the pointer that could be updated
      else
         Insert(root->right, x);
   }
}

C++：指针与指针的指针在二叉树中插入节点

C++: Pointer vs Pointer of Pointer to insert a node in a Binary Tree

c++

pointers

visual-studio-2012

pass-by-reference

dev-c++