Itératif BST insertion en C++

J'essaie de comprendre techniciennes se chargent et comment faire pour insérer des éléments dans il de manière itérative. Mon nœud de la structure de mise en œuvre ressemble à ceci:

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

Et mon insertion de la mise en œuvre ressemble à ceci:

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

L'insertion des œuvres lors de l'ajout du premier Nœud dans un arbre vide, mais j'obtiens une erreur de segmentation à chaque fois que j'ai essayer d'ajouter plus de Nœuds. Je comprends qu'il y a des messages qui montrent comment mettre en œuvre les insertions dans les techniciennes se chargent, mais la plupart d'entre eux montrent la méthode récursive, et ceux avec itératif exemples sont incomplètes ou trop spécifiques. Merci.

Quel est votre débogueur vous montrer?
De regarder, je suis presque certain que quelque chose de mal avec la façon dont je traverse l'arbre pour trouver le point d'insertion...
StarPilot: il ne dit Seg fault. Core dump j'utilise Vim pour compiler mon code
En regardant le code, je vois que sur la première insertion, vous définissez root à newNode. Ensuite, vous laissez le code de tomber. Donc, ptr = newNode; ptr_parent -> left = newNode; return true; sur la première passe. Si votre nœud racine a maintenant un left = itself. Ce n'est pas la mise en page que vous voulez. Comme traversant root -> left sera toujours revenir à lui-même et le résultat dans une boucle jusqu'à ce que le programme de coups. Lorsque vous définissez la racine, avoir juste return true; à partir de là et de voir ce qui se passe.

OriginalL'auteur Samuel | 2013-11-12

binary-search-tree c++

J'ai pu faire mon premier code du travail la nuit dernière, je partage la réponse ici:

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

Pour l'amour de moi que je voulais résoudre ce sans l'aide de double pointeurs.

A la racine déclaré globale ou locale?
bien sûr, il est mondial. Le code jeter erreur de compilation autrement.

OriginalL'auteur Samuel

4

Je pense que je ferais les choses un peu différemment. Tout d'abord, je voudrais simplifier le code des autres un peu en ajoutant un ctor à la classe de Nœud:
```
struct Node{
    Node *left;
    Node *right;
    T data; 

    Node(T const &data) : left(nullptr), right(nullptr), data(data) {}
};
```
Ensuite, vous pouvez utiliser un pointeur vers un pointeur pour parcourir l'arbre et insérer l'élément:
```
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;
}
```
Notez que j'ai retardé la création de la nouvelle nœud jusqu'à ce qu'après que nous avons laissé tomber hors de la boucle. De cette façon, si nous avons un double élément, on peut juste retour (sans fuite d'un nœud, puisque nous n'avons alloué un nouveau nœud encore).

Pour ce que ça vaut, si vous alliez faire cela de façon récursive, il serait probablement plus facile d'utiliser une référence à un pointeur au lieu d'un pointeur vers un pointeur.

Merci il accualy fonctionne!

OriginalL'auteur Jerry Coffin
1

Vous n'avez pas gérer le cas lorsque ptr->data == value donc la boucle est infinie à chaque fois qu'un doublon est trouvé, et ptr = newNode ne fait rien, il fait juste ptr point de newNode. Essayez cette
```
//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;
```
Est-il un moyen pour éviter les doubles pointeurs lorsque vous l'insérez dans un BST? le post ci-dessus suggère double pointeurs, donc j'essaie de voir quels sont les changements nécessaires pour rendre mon code compile.
PS: merci pour le tuyau sur le double de cas. J'ai oublié à ce sujet
Vous pouvez éviter la double pointeur à l'aide de 2 pointeurs que ce que vous avez fait.

OriginalL'auteur Shubham

L'utilisation de pointeurs

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

Lorsque vous essayez de faire de cette

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

il ne fait pas de anyithing car vous avez besoin de modifier le pointeur qui pointe vers la gauche ou la droite sous-nœud

quelque chose comme ceci:

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

J'ai été à essayer de comprendre comment la mise en œuvre serait de travailler avec double pointeurs. Mais par le simple copier/coller de cette mise en œuvre, je reçois quelques erreurs de compilation, j'ai besoin de déboguer. Je vais revenir à vous une fois que j'comprendre quels sont les changements nécessaires.
bst.h:103:21: erreur: demande de membre de la "gauche" en* ptr, qui est de la non-type de classe ‘INTENS<int>::Node*’ bst.h:109:21: erreur: demande de membre de la ‘droite’ in ‘* ptr, qui est de la non-type de classe ‘INTENS<int>::Node*’

OriginalL'auteur DalekSupreme

0

Que je comprends, c'est un échec à cause de la ligne suivante:
```
ptr = newNode; //insert the newNode at the spot
```
après la boucle while votre pointeur est NULL sinon vous ne pouvez pas sortir de la boucle while. L'affectation d'une structure à NULL, ce qui n'est pas droit.

J'espère que cela aide. Tout le reste semble normal.

Qui fait sens. Je suppose que je pensais à cela aussi bien en tant que "liste" plutôt que de sa propre ADT...
N'est-ce pas juste faire ptr à point à newNode? Comment est-il de l'erreur?

OriginalL'auteur printfmyname

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

OriginalL'auteur Hrachya_h

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

J'ai répondu à un cas ici Un Arbre de Recherche binaire d'insertion ne fonctionne pas voir si elle aide les

OriginalL'auteur Jegan Babu

Vous devez vous connecter pour publier un commentaire.