recherche dans un arbre binaire

J'ai écrit la fonction suivante pour rechercher une valeur dans un arbre binaire de stocker des valeurs entières (la fonction est partie d'un programme plus large):

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: quand je fais une recherche pour une valeur présente dans l'arborescence, il fonctionne très bien. Mais si je rechercher une valeur n'est pas présent dans l'arbre, le programme se bloque, et je dois le fermer.
Une chose de plus - je sais que nous pouvons mettre en œuvre la fonction de recherche de manière récursive en passant nœud *temp comme argument, au lieu de le déclarer à l'intérieur, et j'ai fait qui a causé le programme s'exécute correctement, mais je veux savoir quel est le problème dans le code ci-dessus.

Je donne le programme complet ici, juste au cas où il fait faute de trouver plus facile( à 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;
}               

Note de côté : je suis sous Dev C++ compilateur et le système d'exploitation Windows 7.

  • Pouvez-vous format votre code source? C'est dur à lire.
  • Est-il une raison pour laquelle vous ne l'utilisez pas std::set?
  • Oui, la raison est que je ne sais pas ce que std::set est. Je suis un débutant en programmation.
  • L'autre dans l'acceptation de réponse sera de travailler, mais une meilleure façon de le faire est temp = (num > temp->data) ? temp->right : temp->left qui permet au compilateur d'utiliser le cmov instructions.
InformationsquelleAutor Parth | 2013-01-13