C++，BTree 插入

嗨，这是我的 SearchTree 类的代码。
Node* 是一个 m_info 类型为 int 的结构体，m_left(信息较小的节点)和 m_right(信息较大的节点)

void SearchTree::insert(const int &x) {
  Node* tempo = m_root;
  while (tempo != nullptr) {
    if (tempo->m_info >= x) {
      tempo = tempo->m_left;
    } else {
      tempo = tempo->m_right;
    }
  }
  tempo = new Node(x);
}

我正在尝试向树中插入一个新节点。
但看起来我在内存管理中遗漏了一些东西。
tempo 是一个指向新节点的指针，但它与 m_root 无关。
我在这里很困惑。我真的很喜欢 c++ 的力量，但它扭曲了我的逻辑。

我在这里缺少什么？

最佳答案

您不能仅以速度保存指针。速度是您在树中当前位置的拷贝。您必须将其分配给实际变量。

我对这个问题的解决方案是在迭代之前检查 child 是否为 nullptr

void SearchTree::insert(const int &x) {
  if (!m_root) {
      m_root = new Node(x);
      return;
  }
  Node* tempo = m_root;
  while (true) {
    if (tempo->m_info >= x) {
      if (!tempo->m_left) {
        tempo->m_left = new Node(x);
        return;
      }
      tempo = tempo->m_left;
    } else {
      if (!tempo->m_right) {
        tempo->m_right = new Node(x);
        return;
      }
      tempo = tempo->m_right;
    }
  }
}

此外，您应该使用智能指针而不是原始指针。

另一种解决方案是指向指针的指针。我没有测试过，但你可以试试

void SearchTree::insert(const int &x) {
  Node** tempo = &m_root;
  while (*tempo) {
    if ((*tempo)->m_info >= x) {
      tempo = &(*tempo)->m_left;
    } else {
      tempo = &(*tempo)->m_right;
    }
  }
  *tempo = new Node(x);
}

在这张图片中你可以看到。如果您使用 Node* tempo = m_root 则 tempo 包含 m_root 中值的拷贝。如果您更改 tempo，则 m_root 保持不变。

如果您使用 Node** tempo = &m_root 则 tempo 是指向 m_root 的指针。您可以通过 m_root 更改 tempo 。

关于C++，BTree 插入，我们在Stack Overflow上找到一个类似的问题：https://stackoverflow.com/questions/53670321/