不同的输出取决于我是否打印 return 值

Question

所以我有一个简单的 C++ 代码片段，它应该将一个节点插入到二叉搜索树中。如果值已成功插入，则 return 为真；如果值已在树中，则为假。

struct Node {
  int data;
  Node* parent = nullptr;
  Node* left = nullptr;
  Node* right = nullptr;
};

bool insert(Node& root, int data) {
  if (data > (root.data)) {
    if ((root.right) == nullptr) {
      Node newNode = {data, &root};
      root.right = &newNode;
      return true;
    } else {
      return insert(*root.right, data);
    }
  }
  else if (data < (root.data)) {
    if ((root.left) == nullptr) {
      Node newNode = {data, &root};
      root.left = &newNode;
      return true;
    } else {
      return insert(*root.left, data);
    }
  }
  else {
    return false; // if both values are equal 
  }
}

在测试我的函数时，我发现了一些奇怪的东西。当我不打印函数的 return 值时，它给出正确答案 (20):

  Node root = {50};
  insert(root, 20);
  cout << (root.left->data) << endl;

然而，当我 do 打印 return 值时，它给出了不正确的结果 (0):

  Node root = {50};
  cout << insert(root, 20) << endl;
  cout << (root.left->data) << endl;

我无法理解为什么会发生这种情况，但我最好的选择是因为一些奇怪的内存 hijinks，也许没有为结构分配新内存？我来自 Python，那里的内存管理是自动处理的，所以我仍然习惯这种情况。

Answer 1

你在那里调用了未定义的行为：

  Node newNode = {data, &root};
  root.right = &newNode;

这在您的树中存储了堆栈变量的地址。一旦函数 returns，解引用这个 Node 的 children 就不再合法了。从那里开始，任何事情都有可能发生。

你可能想要这样的东西：

  Node* newNode = new Node;
  newNode.data = data;
  newNode.root = root;
  ...
  root.right = newNode;

编辑：请记住，无论何时在代码中放置 new，都需要一个匹配的 delete。为避免这种麻烦，现代方法是使用 unique_ptr。你应该调查一下。在您的情况下，由于您保留指向根的指针，因此您需要 shared_ptr and/or weak_ptr.

不同的输出取决于我是否打印 return 值

Different output depending on whether or not I print the return value

c++

memory-management

binary-search-tree

nodes