Ich versuche, eine Funktion zum Durchsuchen eines binären Suchbaums für einen Wert zu schreiben und den TreeNode mit dem Wert zurückzugeben.Binary Search Tree Fragen
struct TreeNode
{
int value;
struct TreeNode *pLeft, *pRight;
};
TreeNode* SearchTree(int query);
(Für jeden Knoten: this->pLeft enthält Knoten weniger die this->value enthält this->pRight Knoten größer als this->value)
es etwas entlang der Linien wäre:
treenode* SearchTree(int query, treenode* node)
{
if(node == NULL)
return NULL;
else if(query == node->value)
return node;
else if(query < node->value)
return SearchTree(query, node->pLeft);
else if(query > node->value)
return SearchTree(query, node->pRight);
else
return NULL;
}
, wenn der Knoten, Sie sind bei, hat den Wert von dem, was Sie suchen, geben Sie die Knotenadresse zurück. Wenn der aktuelle Knotenwert kleiner ist als das, nach dem Sie suchen, gehen Sie das rechte Blatt nach unten, wenn der aktuelle Knotenwert mehr als das hat, nach dem Sie suchen, gehen Sie das linke Blatt nach unten. Wiederhole so lange, bis du ein leeres Blatt triffst, abhängig davon, wie du am Ende des Baumes implementiert hast. Aber das ist die allgemeine Idee.
Zwei elementare Fehler hier: 1. Ihre Funktion hat kein Abbruchkriterium, falls die Abfrage nicht im Baum ist. (Ich weiß, dass Sie das in Ihrem Kommentar erwähnen, aber es ist wichtiger als das - es sollte auf dem Code stehen.) 2. Sie geben keinen Wert zurück. – TonyK
TonyK, ok Ich habe den Code geändert, um die Abbruchkriterien zu überprüfen, er könnte irgendwie seine eigene Kündigung haben, ich nehme jetzt an, dass alle seine Blattknoten dann NULL sein werden. Frage gefragt, um den TreeNode mit dem Wert, nicht den Wert selbst zurückzugeben. – han
Ich habe diesen Code ein wenig vereinfacht. Es fehlten einige 'return'-Anweisungen und es wurde auf' this' an Stellen verwiesen, an denen es 'node' hätte sein sollen. – asveikau
Sie lösen dies durch Rekursion.
Sie benötigen einen Abschlussschritt.
Sie benötigen auch den rekursiven Schritt, der einen Baumknoten prüft und sich selbst aufruft.
Ich würde vorschlagen, Sie NULL als Rückgabewert verwenden, wenn es nicht gefunden wird.
In Ordnung. Was hast du bisher? –
Der Code was ich bisher habe ist bereits aufgelistet. –
Bitte erwarte nicht, dass andere deine Hausaufgaben für dich machen. Wenn Sie mit etwas festgefahren sind, könnten die Leute hier einige Hinweise geben, damit Sie mit Ihrer Arbeit fortfahren können. Aber vorher müssen Sie zeigen, dass Sie wissen, was Sie tun und wo Ihr Problem ist. – Pirooz