C++，BTree插入

Question

嗨，这是我的SearchTree类的代码。节点*是一种结构，具有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);
}

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

我在这里错过了什么？

Answer 1

不能只以速度保存指针。节奏是树中当前位置的副本。你必须把它赋值给实际的变量。

对于这个问题，我的解决方案是在迭代之前检查子节点是否为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。

Answer 2

您一直推进tempo，直到它等于nullptr为止。在这一点上，你已经离开了树，而你手中的只有一个指向虚无的指针。特别要注意的是，该程序无法确定上次访问哪个节点导致tempo成为null。

您需要做的是提前一步停止:虽然tempo仍然指向一个节点，但下一步将使其指向null。现在，您仍然拥有树的一个有效节点，并且可以将新分配的节点附加到它。