recherche d'un arbre binaire

Question

J'écris une fonction itérative pour rechercher un arbre binaire pour une certaine valeur. Ceci est localisé pour les ints signés jusqu'à ce que je commence à générer des classes génériques.

Supposons que ma classe est BinarySearchTree et qu'elle a un pointeur vers le nœud racine de l'arborescence. Supposons également que les nœuds sont insérés à travers une fonction d'insertion et ont des pointeurs vers deux enfants. Voici une version très abrégée du struct Node:

struct Node 
{ 
    public: 
     Node *left_, *right_; 
     int value_ 

     Node(int val) : value_(val), left_(0), right_(0) { } 
     //done in this manner to always make sure blank children are 
     //init to zero, or null 
     Node(int val, Node *left, Node *right) : value_(val), left_(0), right_(0) 
      { left_ = left; right_ = right; } 
} 

Ainsi, vous pouvez supposer que les pointeurs NULL seront Uninit d'un nœud.

Voici mon code:

int BinarySearchTree::search(int val) 
{ 
    Node* next = this->root(); 

    while (next->left() != 0 || next->right() != 0) 
    { 
     if (val == next->value()) 
     { 
      return next->value(); 
     }  
     else if (val < next->value()) 
     { 
      next = next->left(); 
     } 
     else if (val > next->value()) 
     { 
      next = next->right(); 
     } 
    } 

    //not found 
    return 0; 
} 

Ce code est rejeté par un ami pour deux raisons:

1) Si a ensuite pas d'enfants, à la fois évaluerons à zéro et je quitter prématurément la boucle (je ne vérifierai jamais le val recherché par rapport à la valeur de next).

2) Si la prochaine personne a un enfant, mais que les données que vous recherchez doivent être sur le côté vide de l'arbre, la prochaine sera mise à 0, et elle boucle à nouveau, comparant next (qui est 0) à les arbres de gauche et de droite comme while(0->left()), ce qui entraîne un comportement indéfini.

On me dit que la solution aux deux problèmes réside dans la condition de la boucle, mais je ne vois pas ce que je peux faire pour remédier facilement à la situation. Est-ce que la communauté de Stack Overflow peut offrir des informations?

Answer 1

Je pense que vous devriez tester si la prochaine n'est pas NULL dans votre boucle comme ceci:

int BinarySearchTree::search(int val) 
{ 
    Node* next = this->root(); 

    while (next) 
    { 
     if (val == next->value()) 
     { 
      return next->value(); 
     }  
     else if (val < next->value()) 
     { 
      next = next->left(); 
     } 
     else if (val > next->value()) 
     { 
      next = next->right(); 
     } 
    } 

    //not found 
    return 0; 
} 

Answer 2

Essayez ceci:

while (next != NULL)?

Answer 3

Tout d'abord, je ne sais pas pourquoi vous retournez un int. Que faire si vous recherchez 0 dans l'arbre. Vous voulez probablement quelque chose comme ceci:

bool BinarySearchTree::Search(int val) { 
    Node* current = root(); 
    while (current != NULL) { 
    // Check if it's here 
    if (val == current->value()) { 
     return true; 
    } 
    if (val < current->value()) { 
     current = current->left(); 
    } else { 
     current = current->right(); 
    } 
    } 
    // Not found 
    return false; 
} 

Notez que l'invariant de boucle: au début de chaque boucle, vous êtes à un noeud non nul que vous devez « processus ». Vérifiez d'abord si c'est le noeud que vous voulez. Si ce n'est pas le cas, faites une branche, et laissez la boucle décider si la branche était "bonne" (c'est-à-dire non nulle). Ensuite, vous laisserez l'itération de la boucle suivante s'occuper des tests.