c++ - C++ 中的迭代 BST 插入

Question

我正在尝试了解 BST 以及如何以迭代方式将元素插入其中。我的节点结构实现如下所示:

struct Node{
    Node *left;
    Node *right;
    T data; //template class   
};

我的插入实现如下所示:

template<typename T>
bool BST<T>::Insert(const T value)
{
   Node *newNode = new Node;

   newNode -> data = value;
   newNode -> left = NULL; 
   newNode -> right = NULL;

   if(root == NULL) {root = newNode;} //If the BST is empty
   else 
   {//The BST is not empty 
      Node *ptr = root; //points to the current Node
      Node *ptr_parent; //points to the parent Node

      while(ptr != NULL)
      {
         if((ptr -> data) > value)
         {   
            ptr_parent = ptr;    
            ptr = ptr -> left;
         }

         if((ptr -> data) < value)
         {
            ptr_parent = ptr;
            ptr = ptr -> right;
         }
      }
    }

      ptr = newNode; //insert the newNode at the spot
      if((ptr_parent -> data) < value)
         ptr_parent -> right = newNode;
      else
         ptr_parent -> left = newNode; 

   return true;
}

将第一个节点添加到空树时插入有效，但每当我尝试添加更多节点时，我都会遇到段错误。我知道有些帖子展示了如何在 BST 中实现插入，但大多数展示的是递归方法，而那些带有迭代示例的帖子不完整或过于具体。谢谢。

Answer 1

我想我会做一些不同的事情。首先，我通过向 Node 类添加一个构造函数来稍微简化其他代码:

struct Node{
    Node *left;
    Node *right;
    T data; 

    Node(T const &data) : left(nullptr), right(nullptr), data(data) {}
};

然后就可以使用指向指针的指针遍历树，插入item了:

bool insert(const T value) {
    Node **pos;
    for (pos = &root; *pos != nullptr;) {
        if (value < (*pos)->value) 
            pos = &(*pos)->left;
        else if ((*pos)->value < value ) 
            pos = &(*pos)->right;
        else 
            return false;
    }
    *pos = new Node(value);
    return true;
}

请注意，我已将创建新节点的时间推迟到我们退出循环之后。这样，如果我们有重复元素，我们可以直接返回(不会泄漏节点，因为我们还没有分配新节点)。

就其值(value)而言，如果您要以递归方式执行此操作，使用对指针的引用而不是指向指针的指针可能会更容易。