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 lecmov
instructions.
Vous devez vous connecter pour publier un commentaire.
Mettre un
else
et votre problème disparaîtra.Car après
temp = temp->right;
vous devez vérifiertemp
de nouveau, mais dans votre code original vous tester immédiatementtemp->data
qui ne peut pas être un pointeur valide.std::set
Utiliser un
std::set
; il s'agit essentiellement du TSL arbre binaire. Si vous voulez la recherche de quelque chose, vous devez utilisercount
,trouver
oulower_bound
.La mise en œuvre de structures de données de base sont de bons exercices, mais dans la production, essayez d'utiliser la STL tout d'abord, comme ils sont mis en œuvre par des professionnels avec des connaissances spécifiques dans le compilateur/plate-forme en question. Boost est un autre grand ensemble de structures de données et des expressions communes.