C ++:指针与指针的指针在二叉树中插入节点 [英] C++: Pointer vs Pointer of Pointer to insert a node in a Binary Tree

问题描述

我正在创建一个在二进制树中插入元素的函数，首先，我在Visual Studio 2012上执行了以下操作:

I was creating a function to insert a element in a binary tree and, first, i did the following on 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使其工作，就像这样:

But this same code doesn't work at Dev-C++, I need to use Pointer of Pointer to make it work, like this:

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);
   }
}

有人知道为什么会发生吗?

Does anybody knows why it happens?

推荐答案

第一个代码不应编译.实际上，它不能在MSVC 2013下进行编译.

The first code should not compile. In fact it doesn't compile under MSVC 2013.

为什么?

您的节点结构应如下所示:

Your node structure should be something like this:

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

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

This means that (root)->left is of type Nodo*. Hence &(root)->left is of type Nodo** which is incompatible with a Nodo* argument.

无论如何，在插入函数中，您当然想更改树.但是，例如，如果要执行:root = n;，则只需更新根参数(指针).离开该功能后，此更新将丢失.在这里，您当然想更改根节点的内容，或者更可能是更改指向根节点的指针.

Anyway, in your insert function, you certainly want to change the tree. But if you'd for example do: root = n; you would just update the root argument (pointer). This update is lost as soon as you leave the function. Here, you certainly want to change either the content of the root node or more probably the pointer to a root node.

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

In the second version, you pass as argument the address of a pointer to a node, and then update this pointer when necessary (expected behaviour).

备注

如果要通过引用传递第一个版本，则可以将其保存":

The first version could be "saved", if you would go for a pass by reference:

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 ++:指针与指针的指针在二叉树中插入节点的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！