C++| BST 对节点指针的引用与节点指针

Question

假设我有这个 BST 模板：

template <typename T> class Node {
private:
public:
  T data;
  Node *left;
  Node *right;

  Node(T dt) : data{dt}, left{nullptr}, right{nullptr} {}
  ~Node() {
    this->data = 0;
    this->left = nullptr;
    this->right = nullptr;
  }
};

template <typename T> class BST {
private:
  Node<T> *_root;

  _insert();
  _add();
  _printOrder_In(Node<T> *parent, std::ostream& os) {
    if (!parent) return;
    _printOrder_In(parent->left, os);
    os << parent->data << ' ';
    _printOrder_In(parent->right, os);
  }

public:
  BST() : _root{nullptr} {}
  ~BST();
  
  insert();
  add();
  std::ostream& print(std::ostream& os = std::cout) {
    _printOder_In(this->_root, os);
    return os;
  }
};

为什么以下代码在我传递对节点指针的引用时有效，而在我传递节点指针时无效？

// BST MEMBER FUNCTIONS:
private:
  void _insert(Node<T>* &parent, const T &val) { // works
//void _insert(Node<T>*  parent, const T &val) { // doesn't work, apparently generates nodes indefinitely
    if (!parent)
      parent = new Node<T>{val};
    else {
      if (val < parent->data)
        _insert(parent->left, val);
      else if (val > parent->data)
        _insert(parent->right, val);
      else
        return;
    }
  }

public:
  void insert(const T &val) {
    _insert(this->_root, val);
  }
};

与此替代方法相反，它只对传递的指针起作用：

// BST MEMBER FUNCTIONS:
private:
  void _add(Node<T>* parent, T val) {
    if (parent->data > val) {
      if (!parent->left) {
        parent->left = new Node<T>{val};
      } else {
        _add(parent->left, val);
      }
    } else {
      if (!parent->right) {
        parent->right = new Node<T>{val};
      } else {
        _add(parent->right, val);
      }
    }
  }

public:
  void add(T val) {
    if (this->_root) {
      this->_add(this->_root, val);
    } else {
      this->_root = new Node<T>(val);
    }
  }

我知道指向点的引用可以让我直接访问传递的指针。但是，我对这两种方法之间的区别感到困惑。在第二种方法中，尽管指针本身没有作为引用传递，但控制流中使用的本地副本仍然有效。

Answer 1

OP 问题是关于 call-by-value vs. call-by-reference。

C 语言（C++ 的“祖先”）专门提供 call-by-value。缺少的 call-by-reference 可以通过使用变量的地址而不是变量本身来模仿。（当然，resp. 函数的参数必须变成 pointer-to-type 而不是类型本身。）

因此，指针是 passed-by-value，但它的值可用于访问函数范围之外的内容，并且修改（在其原始存储中完成）将在 return 之后继续存在那个功能。

当C++从C演化出来的时候，这个原则就被继承了。但是，C++ 添加了 call-by-reference，就像其他类似语言（例如 Pascal）所知道的那样。

call-by-value 与 call-by-reference 的简单演示：

#include <iostream>

void callByValue(int a)
{
  std::cout
    << "callByValue():\n"
    << "  a: " << a << '\n'
    << "  a = 123;\n";
  a = 123;
  std::cout
    << "  a: " << a << '\n';
}

void callByRef(int &a)
{
  std::cout
    << "callByRef():\n"
    << "  a: " << a << '\n'
    << "  a = 123;\n";
  a = 123;
  std::cout
    << "  a: " << a << '\n';
}

int main()
{
  int b = 0;
  std::cout << "b: " << b << '\n';
  callByValue(b);
  std::cout << "b: " << b << '\n';
  callByRef(b);
  std::cout << "b: " << b << '\n';
}

输出：

b: 0
callByValue():
  a: 0
  a = 123;
  a: 123
b: 0
callByRef():
  a: 0
  a = 123;
  a: 123
b: 123

解释：

a 的更改仅在 callByValue() 中有局部影响，因为 a 是按值传递的。（即将参数的副本传递给函数。）
a 的更改修改了 callByRef() 中传递的参数，因为 a 是通过引用传递的。

Easy-peasy？当然。但是，如果 a 的参数类型 int 被任何其他类型替换，则情况完全相同——例如Node* 甚至 Node<T>*.

我从OPs代码中取出相关行：

  void _insert(Node<T>* &parent, const T &val) { // works
    if (!parent)
      parent = new Node<T>{val};

如果参数 parent 的值是 nullptr，则 parent 被分配新创建的 Node<T> 的地址。因此，通过引用传递的指针（变量）被修改。因此，修改在离开函数 _insert().

后仍然存在

另一种选择：

  void _insert(Node<T>*  parent, const T &val) { // doesn't work, apparently generates nodes indefinitely
    if (!parent)
      parent = new Node<T>{val};

如果参数 parent 的值是 nullptr，则 parent 被分配新创建的 Node<T> 的地址。因此，指针按值传递。因此，（原始）变量（在调用中使用）没有改变——并且在函数离开时仍然包含 nullptr。

顺便说一句。据此，创建的 Node<T> 的地址丢失了。（它不再存储在任何地方。）然而，Node<T> 实例仍然驻留在它们分配的内存中——在进程结束之前无法访问——退化为一块浪费的内存。这是 memory-leaks 可能发生的示例。

请不要将这个事实与指针本身“模仿”pass-by-reference 的另一个事实混淆。指针指向（如果不是 nullptr）的对象（Node<T> 类型）的修改将变得持久。

仔细查看 _add()，似乎只有指向的对象（Node<T> 类型）被修改，但指针本身没有被修改。因此，按值传递它就完全足够了。

但是为了 _insert() 的正确工作，parent 本身的修改也必须变得持久。因此，只有第一个选项可以正常工作。

C++| BST 对节点指针的引用与节点指针

C++| BST reference-to-node-pointer vs. a node-pointer

c++

pointers

reference

binary-search-tree