C++, BTree 插入

Question

您好，这是来自我的 SearchTree class 的代码。 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++ 的强大功能，但它扭曲了我的逻辑。

我在这里错过了什么？

Answer 1

你一直前进tempo直到等于nullptr。此时你已经离开了树，你手头上只有一个指向虚无的指针。请注意，特别是该程序无法确定您上次访问哪个节点导致 tempo 变为 null。

你需要做的是停止一步更早：虽然tempo仍然指向一个节点，但下一步会使它指向null。现在你手里还有一个树的有效节点，可以把新分配的节点附加到它上面。

Answer 2

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

我对这个问题的解决方案是在迭代之前检查 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 插入

C++, BTree Insert

c++

algorithm

binary-tree

c++17