在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 类添加一个ctor来稍微简化其他代码：

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

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

然后你可以使用指向指针的指针来遍历树并插入项目：

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;
}

请注意，我已延迟创建新节点，直到我们退出循环。这样，如果我们有一个重复的元素，我们可以直接返回（不会泄漏节点，因为我们还没有分配一个新节点）。

对于它的价值，如果您打算递归地执行此操作，则使用对指针的引用而不是指向指针的指针可能会更容易。

Answer 2

我昨晚能够使我的原始代码工作,我在这里分享答案:

template<typename T>
bool BST<T>::Insert(const T value)
{
   Node *ptr;
   Node *ptr_parent;

   if(root == NULL)
   {//The BST is Empty...
      Node *newNode = new Node;
      newNode -> data = value;
      newNode -> left = NULL;
      newNode -> right = NULL;

      root = newNode;
      ptr = root;
   } else { //traversing the tree to find the insertion point
      ptr = root;
      while(ptr != NULL)
      {
         if((ptr -> data) == value) {return false;} //to check for duplicates

         if(value < (ptr -> data))
         {
            ptr_parent = ptr;
            ptr = ptr -> left;
         } else {
            ptr_parent = ptr;
            ptr = ptr -> right;
         }
      }
      Node *newNode = new Node;

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

      //checking for parent value to determine if
      //the Node is a left or right child  
      if(value < (ptr_parent -> data))
         ptr_parent -> left = newNode;
      else
         ptr_parent -> right = newNode;
   }

   ++count;//to keep track of the Node count
   return true;      
}

为了我自己,我想在不使用双指针的情况下解决这个问题.