recherche dans un arbre binaire

Question

j'ai écrit la fonction suivante pour rechercher une valeur dans un arbre binaire à stocker des valeurs de nombre entier (la fonction fait partie d'un programme plus important):

bool tree::search(int num)  //the function belongs to class 'tree' 
{ 
    node *temp=head;  //'head' is pointer to root node 

    while(temp!=NULL) 
    { 
     if(temp->data==num) 
     break; 

     if(num>temp->data) 
     temp=temp->right; 

     if(num<temp->data) 
     temp=temp->left; 
    } 

    if(temp==NULL) 
     return false; 
    else if(temp->data==num) 
     return true; 
}  

Le problème est le suivant: lorsque je chercher une valeur présente dans l'arbre, ça marche bien. Mais si je recherche une valeur non présente dans l'arbre, le programme se bloque et je dois le fermer. Encore une chose - Je sais que nous pouvons implémenter la fonction de recherche récursivement en passant le noeud * temp comme argument, au lieu de le déclarer à l'intérieur, et c'est ce qui a fait fonctionner le programme correctement, mais je veux savoir quel est le problème dans le code ci-dessus.

Je donne ici le programme complet, juste au cas où il fait pannes trouver plus facile (s'il vous plaît noter que j'ai écrit que deux fonctions encore):

#include<iostream> 
using namespace std; 

struct node 
{ 
int data; 
node *left; 
node *right; 
}; 

class tree 
{ 
public: 
    node *head; //pointer to root 
    int count;  //stores number of elements in tree 
    tree(); 
    void addnode(int); 
    void deletenode(int); 
    bool search(int); 
    int minimum(); 
    int maximum(); 
    void inorder(); 
    void preorder(); 
    void postorder(); 
    void printtree(); 
    int mthlargest();  //finds 'm'th largest element 
    int mthsmallest(); //finds 'm'th smallest element 
    void convert();  //converts binary tree to linked list 
}; 

tree::tree() 
{ 
    head=NULL; 
    count =0; 
} 

void tree::addnode(int num) 
{ 
    node *temp= new node; 
    temp->data=num; 
    temp->left=NULL; 
    temp->right=NULL; 

    node **ptr=&head;   //double pointer 

    while(*ptr!=NULL) 
    { 
     if(num>(*ptr)->data) 
     ptr=&((*ptr)->right); 

     if(num<(*ptr)->data) 
     ptr=&((*ptr)->left); 
    } 

    *ptr=temp; 
} 


bool tree::search(int num) 
{ 
    node *temp=head; 

    while(temp!=NULL) 
    { 
     if(temp->data==num) 
     break; 

     if(num>temp->data) 
     temp=temp->right; 

     if(num<temp->data) 
     temp=temp->left; 
    } 

    if(temp==NULL) 
     return false; 
    else if(temp->data==num) 
     return true; 
}  




int main() 
{ 
    tree ob; 
    ob.addnode(2); 

    ob.search(2); 

    ob.search(3); 

    ob.search(-1); 
    ob.search(2); 
    cout<<endl<<endl; 

    system("pause"); 
    return 0; 
}    

Side note: J'utilise Dev compilateur C++ et Windows 7 OS.

Answer 1

Mettez un else et votre problème disparaîtra.

Parce qu'après temp = temp->right; vous devez vérifier temp à nouveau, mais dans votre code d'origine tester immédiatement temp->data qui ne peut être un pointeur valide.

bool tree::search(int num) 
{ 
    node *temp = head; 

    while (temp != NULL) 
    { 
     if (temp->data == num) 
      break; 

     if (num > temp->data) 
      temp = temp->right; 
     else     // <--- Put this 'else' here 
     if (num < temp->data) 
      temp = temp->left; 
    } 

    if (temp == NULL) 
     return false; 

    if (temp->data == num) 
     return true; 

    return false; 
} 

Answer 2

std::set

Utilisation d'un std::set; c'est essentiellement l'arbre binaire de STL. Si vous souhaitez rechercher quelque chose, vous utiliserez count, find ou lower_bound. L'implémentation de structures de données de base est un bon exercice, mais en production, essayez d'abord d'utiliser STL, car elles sont implémentées par des professionnels ayant une connaissance spécifique du compilateur/de la plate-forme en question. Boost est un autre grand ensemble de structures de données et d'idiomes communs.