1

这是我的节点类。

class Node
{
private:
public:
  T data;
  Node<T>* left;
  Node<T>* right;
  Node(T dat) : data(dat), left(NULL), right(NULL)
  {}
};

这是我的插入函数，在我的 Btree 类中定义：

public:
  Node<T>* root;
  Btree() : root(NULL){}
  void insert(T data, Node<T>* parent)
  {   
      if( !parent  )
      {   
        parent = new Node<T>(data);
        return;
      }   
      else if(data < parent->data)
      {   
        insert(data, parent->left);
      }   
      else if(data > parent->data)
      {   
        insert(data, parent->right);
      }   
  }

};

这是我的主要功能：

int main()
{
  Btree<int> tree;

  tree.insert(5, tree.root);

  cout << tree.root->data << endl;

  tree.insert(6, tree.root);

  cout << tree.root->right->data << endl;

}

当我运行时，我得到一个段错误。

我认为是因为指针变量 parent 是按值传递的，所以当我创建一个由 parent 指向的新节点时，一旦我退出插入函数，我就会丢失它？这是否意味着我必须在这里使用双指针？

有人可以给我一个彻底的解释，说明内存中发生的事情导致这不能按计划进行。我的诊断在这里是正确的还是有其他问题？

当我将 tree.root 作为要插入的第二个参数传递时，我传递的是一个 Node*，我知道很多。现在，即使它是按值传递的，它与我从调用主函数传递的地址是否不同。因此，当我说父级（这是我从 main,tree.root 传递的地址）=新节点时，是否不应该在父级地址的堆上创建一个新节点，也就是 tree.root 的地址？为什么按价值传递会掩盖这一点？

4

3 回答 3

2

在这种情况下，按值传递的问题在于，对函数内部的形式参数所做的所有分配对调用者都是不可见的。因此，这个任务

if( !parent  )
{   
    parent = new Node<T>(data); // <<== HERE
    return;
}

tree.root对调用者没有影响：

tree.insert(5, tree.root);

函数中指针的值parent发生变化，然后及时丢弃；树的root遗骸NULL。

解决此问题的方法是将指针传递给指针，如下所示：

void insert(T data, Node<T>** parent) {
    if( !*parent  )
    {
        *parent = new Node<T>(data);
        return;
    }
    else if(data < (*parent)->data)
    {
        insert(data, &((*parent)->left));
    }
    else if(data > (*parent)->data)
    {
        insert(data, &((*parent)->right));
    }
}
于 2012-07-14T23:26:37.150 回答
2

C++ 按值传递，因此这parent是传入指针的副本。因此，分配给它没有持久的影响。解决此问题的最简单方法是更改​​方法的签名，以便它接受对指针的引用。这将自动使编译器更新原始指针，同时避免更改程序的其余部分。

于 2012-07-14T23:27:09.080 回答
1

dasblinkenlight回答得最好。但是，有一个更简洁的解决方案：

获取指针的引用（称为对指针的引用）：

void insert(T data, Node<T>*& parent)
  {   
      if( !parent  )
      {   
        parent = new Node<T>(data);
        return;
      }   
      else if(data < parent->data)
      {   
        insert(data, parent->left);
      }   
      else if(data > parent->data)
      {   
        insert(data, parent->right);
      }   
  }

在此处查看更多信息：http: //www.codeproject.com/Articles/4894/Pointer-to-Pointer-and-Reference-to-Pointer

于 2012-07-14T23:39:32.220 回答