Lokalisieren von Vorgänger- und Nachfolgerknoten

Question

Ich habe eine Methode, um die Nachfolger- und Vorgängerknoten in einer binären Suchstruktur abzurufen, aber ich habe einige Probleme, den Fehler in meinem Code zu finden. Angenommen, ich füge Knoten mit den folgenden Schlüsseln hinzu: "C", "B" und "K". Wenn ich den Inhalt meiner binären Suchbaum zu drucken, erhalte ich die folgende Ausgabe:

"C" "some data 1" 
"B" "some data 2" 
"K" "some data 3" 

Als ich hinzufügen "B" es offensichtlich keinen Vorgänger oder Nachfolger hat, so dass ich nur diejenigen zu leeren Saiten gesetzt:

root = root->insert(root, key, data); 
    root->getNextAndPrev(root, prev, next, key); 
    string p; 
    string n; 
    if (!prev) { 
     pred = ""; 
    } 
    else { 
     pred = prev->getKey(); 
    } 
    if (!next) { 
     succ = ""; 
    } 
    else { 
     succ = next->getKey(); 
    } 

    return new Entry(data, succ, pred); 

Wenn ich "B" hinzufügen, bekomme ich die Ausgabe, die "B" s Nachfolger ist "C" und der Vorgänger ist "" wie erwartet. Wenn ich jedoch "K" zum Baum hinzufüge, bekomme ich die Ausgabe, dass "K" s Vorgänger ist "C" und der Nachfolger ist auch "C". Ich bin mir nicht sicher, warum ich diesen Fehler bekomme, da ich überprüfe, ob es keinen Nachfolger gibt (nichts kommt nach "K") setze es auf eine leere Zeichenfolge.

Meine Node Klasse behandelt die insert() und getNextAndPrev() Methoden, und hier ist, wie ich sie implementiert haben:

void Node::getNextAndPrev(Node* root, string key) { 
if (!root) return; 

if (root->key == key){ 

    if (root->left != NULL){ 

     Node* tempNode = root->left; 

     while (tempNode->right != NULL) { 
      tempNode = tempNode->right; 
     } 
     prev= tempNode; 
    } 

    if (root->right != NULL){ 

     Node* tempNode = root->right; 

     while (tempNode->left != NULL) { 
      tempNode = tempNode->left; 
     } 
     next = tempNode; 
    } 

} 
if (root->key > key) { 
    next = root; 
    getNextAndPrev(root->left, key); 
} 
else { 
    prev = root; 
    getNextAndPrev(root->right, key); 
} 

}

Warum ist es, dass durch einige Schlüssel aus, um das Hinzufügen meines getNextAndPrev verursacht falsche Werte abrufen?

Vielleicht hat es etwas damit zu tun, wie ich Einträge in meinem main einfüge. Ich habe eine Schleife wie folgt festgelegt:

string command = ""; 
Entry* entry = new Entry("","",""); 
string def = ""; 
while (true) { 
    cout << "Enter command: "; 
    getline(cin, command); 
    if (parseCommand(command, "ADD") == 0) { 
     string tempCmd = processCommand(command, 3); 
     string key = tempCmd.substr(0, tempCmd.length() - 4); 
     string data = tempCmd.substr(tempCmd.length() - 4); 
     trim(key); 
     trim(data); 
     def = data; 
     entry = dict->modify(key, data); 
     cout << "added: " << key << " with definition of : " << def << " to the dictionary " << endl; 
    } 

modify() wird wie so in meiner Dictionary Klasse genannt:

Entry * Dictionary::modify(string key, string data) { 
    Entry * entry = new Entry("","",""); 
    if (root) entry = search(key); 
    //inserting something into the dictionary 
    if (data != "" && !this->root->doesContain(this->root, key)) { 
    root = root->insert(root, key, data); 
    return entry; 
    } 
} 

Und schließlich meine search() Methode, die in modify() aufgerufen wird:

Entry * Dictionary::search(string key) { 
     if (key == "") { 
     return new Entry("", getSmallestKey(), getLargestKey()); 
     } 

     if (!this->root->doesContain(root, key)) { 
     root->getNextAndPrev(root, key); 
     string prev; 
     string next; 
     if (root->getPrevNode() != NULL) { 
      prev = root->getPrevious(); 
      cout << "Predecessor is " << prev << " root is: " << root->getKey() << endl; 
     } 
     else { 
      prev = ""; 
      cout << "No Predecessor" << endl; 
     } 

     if (root->getNextNode() != NULL) { 
      next = root->getNext(); 
      cout << "Successor is " << next << " root is: " << root->getKey() << endl; 
     } 
     else { 
      next = ""; 
      cout << "No Successor" << endl; 
     } 
     if (next == prev) { 
      if (next < key) { 
      next = ""; 
      } 
      if (prev > key) { 
      prev = ""; 
      } 
     } 
    return new Entry("", next, prev); 
} 

Um das Problem im Detail zu veranschaulichen, hier ist die Ausgabe von oben ausgeführt:

Enter command: ADD "FOO" "D" lookup stuff: root: prev: next: // gets logged out when I insert into dictionary added: "FOO" with a definition of: "D" to the dictionary Enter command: ADD "BIN" "C" No Predecessor Successor is "FOO" root is: "FOO" lookup stuff: root: prev: next: "FOO" added: "BIN" with a definition of: "C" to the dictionary Enter command: ADD "QUUX" "D" Predecessor is "FOO" root is: "FOO" Successor is "FOO" root is: "FOO" lookup stuff: root: prev: "FOO" next: added: "QUUX" with a definition of: "D" to the dictionary Enter command: ADD "BAZ" "N" Predecessor is "FOO" root is: "FOO" Successor is "BIN" root is: "FOO" lookup stuff: root: prev: "FOO" next: "BIN" added: "BAZ" with a definition of: "N" to the dictionary

ich kann nicht herausfinden, warum, wenn BAZ dem Wörterbuch hinzugefügt, der Vorgänger und Nachfolger jetzt fehl am Platz ist:

Enter command: ADD "BAZ" "N" Predecessor is "FOO" root is: "FOO" Successor is "BIN" root is: "FOO"

Answer 1

Ich hoffe, Ihr Knoten Konstruktor

new Node(key, d) 

setzt die Felder left und right auf NULL.

Von successor und predecessor Ich denke, du meinst inorder traversal Nachfolger und Vorgänger.Nun, Ihr Code scheint mir absolut in Ordnung zu sein

Die einzige Möglichkeit ist, dass ich denke, Sie verwenden gemeinsame Variablen prev und nächste, um den Vorgänger und Nachfolger zu bekommen. Versuchen Sie also verschiedene Variablen für verschiedene Knoten zu verwenden.

Nach Nachfolger und predecssor für den Knoten B durchgeführt werden immer, definieren neue Variablen:

Node *prevK,*nextK; 

und rufen Sie die Funktion getNextAndPrev() mit diesen Variablen.