C++

Question

我有一个看起来像这样的二叉树

struct Node 
{
  int key;
  double data;
  Node* right;
  Node* left;
};

我有这个 "insert" 函数用于插入新节点和构建树

void insert(Node*& p, int key, double to_be_inserted) 
{
  if (p == nullptr) 
  {
    p = new Node;
    p->key = key;
    p->data = to_be_inserted;
    p->left = nullptr;
    p->right = nullptr;
  }
  else 
  {
    if (p->key == key) 
    {
      p->data = to_be_inserted;
    }
    else 
    {
      Node*& child = (p->key > key) ? p->left : p->right;
      insert(child, key, to_be_inserted);
    }
  }
}

和一个看起来像这样的主函数

int main(int argc, char ** argv) 
{
  Node* root = nullptr;
  insert(root, 11, 11);
  insert(root, 6, 6);
  insert(root, 4, 4);
  insert(root, 5, 5);
  insert(root, 8, 8);
  insert(root, 10, 10);
  insert(root, 19, 19);
  insert(root, 17, 17);
  insert(root, 43, 43);
  insert(root, 31, 31);
  insert(root, 49, 49);

  printTree(root, 0);
  return 0;
}

最终的 "printed-out" 树看起来像这样

（这个 "print-out" 应该是从左到右而不是从上到下阅读）

我的问题是：

insert 函数如何知道树在第二次（或更多次）调用时当前的样子？ main 中的 root 只是一个不变的节点（有两个子节点）（根据我的调试器），并且您多次使用相同的 root 作为参数。当再次调用 insert 时，它如何知道它在何处停止？ p = new Node 行实际上在做什么（在 insert 中）。在我看来，它只是一遍又一遍地覆盖根目录？基本上，它在哪里存储（当前）完整树的记忆？
1. 如果 insert 函数声明为 Node * insert(Node * p, int key, double value);?
2. p是指针引用而不是普通指针有什么具体原因吗？有什么区别？

抱歉，问题很长（而且可能很愚蠢）。我是 C++ 的新手。我了解指针和引用的基础知识，但显然我似乎无法弄清楚 insert 函数中实际发生了什么（以及在主函数中，当 insert 被多次调用时相同的 root 参数）。

谢谢！

Answer 1

How does the insert function know what the tree currently looks like when it's being called a second (or more) time?

因为根节点保留了它的两个子节点的内存，而它的子节点保留了它们每个子节点的内存，并且...

插入函数从一个节点开始，在这个块中

    else 
    {
      Node*& child = (p->key > key) ? p->left : p->right;
      insert(child, key, to_be_inserted);
    }

确定哪个分支应该"drilled down into"找到一个空节点插入。在节点处每次插入值都会遍历树，直到找到正确的插入位置。

Would the insert function behave differently if it was declared as Node * insert(Node * p, int key, double value);?

是的，如果它在您的问题中如上声明，Node * 类型的 p 的值会从 main 复制到函数 [=15] =] 作为局部变量。 insert 中 p 的任何更改都是局部的，不会影响 main 中 root 的值。当您通过引用传递时，对 insert 中的 p 所做的任何更改都将影响 main 中的 root。如果不传引用，root永远是一个nullptr，而insert只会执行这个分支：

  if (p == nullptr) 
  {
    p = new Node;
    p->key = key;
    p->data = to_be_inserted;
    p->left = nullptr;
    p->right = nullptr;
  }

这会泄漏内存。

Is there a specific reason why p is a pointer reference instead of a normal pointer? What's the difference?

见上文

C++ - 无法理解指针 modification/assignment 和指针引用

C++ - Having trouble understanding pointer modification/assignment and pointer references

tree

pointers

reference

pass-by-reference