Durchsuchen eines Binärbaums

Question

Ich schreibe eine iterative Funktion, um einen Binärbaum nach einem bestimmten Wert zu suchen. Dies wird auf signierte Ints lokalisiert, bis ich mich mit dem Generieren von Klassen befasse.

Angenommen, meine Klasse ist BinarySearchTree und hat einen Zeiger auf den Stammknoten des Baums. Nehmen Sie außerdem an, dass Knoten durch eine Insert-Funktion eingefügt werden und Zeiger auf zwei untergeordnete Elemente haben. Hier ist eine viel gekürzte Version der Knoten Struktur:

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

So können Sie sicher davon ausgehen, dass ein UNINIT Zeiger des Knotens NULL sein wird.

Hier ist mein 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; 
} 

Dieser Code aus zwei Gründen von einem Freund abgelehnt wird:

1) Wenn neben keine Kinder hat, die beide auf Null bewerten und ich werde vorzeitig beenden die Schleife (Ich werde nie das gesuchte Wert gegen den Wert von Next überprüfen).

2) Wenn nächste hat ein Kind, aber die Daten, die Sie suchen, sollte auf der leeren Seite des Baumes sein, wird als nächstes auf 0 gesetzt, und es wird wieder eine Schleife, Vergleich nächsten (das ist 0) zu die linken und rechten Bäume wie while(0->left()), was zu undefiniertem Verhalten führt.

Mir wurde gesagt, dass die Lösung für beide Probleme in der Schleifenbedingung liegt, aber ich kann nicht sehen, was ich tun kann, um die Situation leicht zu beheben. Kann die Community von Stack Overflow Einsichten bieten?

Answer 1

Ich denke, Sie sollten testen, wenn nächste wie so nicht NULL in der Schleife ist:

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

Versuchen Sie folgendes:

while (next != NULL)?

Answer 3

Zunächst einmal, ich bin nicht sicher, warum Sie einen int zurückkehren. Was ist, wenn Sie im Baum nach 0 suchen? Sie wollen wahrscheinlich etwas wie folgt aus:

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

Beachten Sie, dass die Schleifeninvariante: am Anfang jeder Schleife, Sie an einem nicht null Knoten sind, die Sie „Prozess“ benötigen. Überprüfen Sie zuerst, ob es der gewünschte Knoten ist. Wenn nicht, mache eine Verzweigung und lasse die Schleife entscheiden, ob die Verzweigung "gut" war (dh - nicht null). Dann lassen Sie die nächste Schleifeniteration für das Testen sorgen.