7

我正在尝试了解 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 的插入，但其中大多数展示了递归方法，而那些带有迭代示例的帖子不完整或过于具体。谢谢你。

4

8 回答 8

6

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

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

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

于 2013-11-13T19:00:32.807 回答
6

我想我会做一些不同的事情。首先，我将通过向 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;
}

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

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

于 2013-11-12T20:23:47.360 回答
1

您没有处理这种情况，ptr->data == value因此每当找到重复项时循环将是无限的，并且ptr = newNode不执行任何操作，它只是ptr指向newNode. 尝试这个

//ptr holds the address of pointers to nodes.
Node **ptr = &root;

while(*ptr != NULL){

  if((*ptr)->data > T)
    ptr = &(*ptr)->right;
  else
    ptr = &(*ptr)->left;
  //Not handling duplicates
}
//Change the value of the pointer to newNode
*ptr = newNode;
于 2013-11-12T19:39:27.280 回答
0

使用硬指针

Node **ptr = &root; //points to the current Node
Node **ptr_parent; //points to the parent Node

当您尝试执行此操作时

ptr = newNode; //insert the newNode at the spot

它没有做任何事情，因为您需要修改指向左侧或右侧子节点的指针

像这样的东西：

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;
}
于 2013-11-12T19:28:46.013 回答
0

据我了解，由于以下行而失败：

ptr = newNode; //insert the newNode at the spot

在 while 循环之后，您的 ptr 为 NULL，否则您无法退出 while 循环。您正在将一个结构分配给 NULL，这是不对的。

希望这会有所帮助。其他一切看起来都很正常。

于 2013-11-12T19:37:10.047 回答
0 
void insert(int val)
    {
        Node *newNode;
        newNode=new Node;
        newNode->data=val;
        Node *currentNode=root;
        Node *parentNode;
        
        if(root==NULL)
        {
            newNode->left=NULL;
            newNode->right=NULL;
        }
        
            
        else
        {
            
            
            while(currentNode!=NULL)
            {
                if((currentNode->data)>val)
                {
                    parentNode=currentNode;
                    currentNode=currentNode->left;
                }
                
                if((currentNode->data)<val)
                {
                    parentNode=currentNode;
                    currentNode=currentNode->right;
                }
            }
        
        }
        currentNode=newNode;
        if((parentNode->data)<val)
        {
            parentNode->right=newNode;
        }
        else
        {
        parentNode->right=newNode;
        }
        
    }
于 2020-07-20T11:54:05.233 回答
0 
void insert(node* root, int value)
{
    if (root == NULL)
    {
        root = new node;
        root->data = value;
        return;
    }
    while(!((root->data < value && root->right == NULL) || (root->data >= value && root->left == NULL)))
    {
        if (root->data < value)
            root = root->right;
        else
            root = root->left;
    }
    if (root->data < value)
    {
        root->right = new node;
        root->right->data = value;
    } else 
    {
        root->left = new node;
        root->left->data = value;
    }
}
于 2016-06-17T06:59:12.803 回答
0 
template <class T>
class TreeNode{
private:
    T data;
    TreeNode<T>* right,*left;
public:
void setData(T d){
    this->data =d;
}
T getData(){
    return this->data;
}
void setRight(TreeNode<T>* r){
    this->right =r;
}
TreeNode<T>* getRight(){
    return this->right;
}
void setLeft(TreeNode<T>* r){
    this->left =r;
}
TreeNode<T>* getLeft(){
    return this->left;
}
static TreeNode<T>* newNode(T data){
    TreeNode<T>* n = new TreeNode<T>();
    n->setData(data);
    n->setRight(NULL);
    n->setLeft(NULL);
    return n;
}
};



template <class T>
class BinaryTree{
private:
        TreeNode<T>* root;
public:
    void insert(T data){
        TreeNode<T>* n = TreeNode<T>::newNode(data);

        if(root==NULL)
            root = n;
        else{
        TreeNode<T>* t = root;
        while(t!=NULL){

            if(n->getData() >= t->getData()){
                if(t->getRight()==NULL){
                    t->setRight(n); //newnode attached as right child in tree
                    t = NULL;
                }
                else
                    t = t->getRight();
            }
            else{
                if(t->getLeft()==NULL){
                    t->setLeft(n); //newnode attached as left child in tree
                    t=NULL;
                }
                else
                    t = t->getLeft();
            }
        }

        }

    }

    void preorder(){
        TreeNode<T>* t = root;
        preorderUtil(t);
    }

    void preorderUtil(TreeNode<T>* node){
        if(node==NULL)
            return;
        preorderUtil(node->getLeft());
        cout<<node->getData()<<" ";
        preorderUtil(node->getRight());
    }
};

我在这里回答了一个案例二叉搜索树插入不起作用 看看它是否有帮助

于 2016-12-17T08:39:04.813 回答