Rekursion Abbruchbedingung

kleo

Hallo,

ich bin gerade an einer Methode dran, die den Vorgaengerknoten eines TreeNodes zurueckgeben soll.
Die Parameter sind:
die Wurzel; es handelt sich um einen Binaerbaum und
der Knoten (node), dessen Vorgaenger ich suche.

Wie kann ich die Rekursion abbrechen, nachdem ich root returnt habe?
Gibt es so etwas wie "break" fuer Rekursionen? Ich braeuchte eine Abbruchbedingung und habe gedacht, dass wenn ich einen TreeNode* zurueckgebe, ich automatisch aus der Methode springen kann, da die if-Bedingung nur einmal zutrifft. Sieht jemand was ich falsch mache?

TreeNode* Tree::parentsearch(TreeNode* root, TreeNode* node){
    if(root != NULL){
        if(root->rechts == node || root->links == node){
            return root;
        }
        parentsearch(root->links, node);
        parentsearch(root->rechts, node);
    }
}

Lieben Gruss

Kleo

Schalte die Warnungen deines Compilers ein. Du hast kein Problem mit der Abbruchbedingung[*] sondern damit, in allen Pfaden ein Ergebnis zurückzuliefern.
Ich vermute, dass du Rekursion nicht richtig verstanden hast. Benutze einen Debugger und schau dir an, was passiert. Achte insbesondere auf den Stack.

[*] wenn ein (positives) Ergebnis aus einer tieferen Ebene geliefert wird, musst du die weitere Suche abbrechen und das Ergebnis weiterreichen.

kleo

TreeNode* Tree::parentsearch(TreeNode* root, TreeNode* node){
    if(root != NULL){
        if(root->rechts == node || root->links == node){
            return root;
        }
        else if(node->NodePosID < root->NodePosID){
            return parentsearch(root->links, node);
        }
        else if(node->NodePosID > root->NodePosID){
            return parentsearch(root->rechts, node);
        }
    }
}

Deine Funktion liefert immer noch nicht in alles Pfaden ein Ergebnis.

krümelkacker

Hallo Kleo

Ich schlage vor, den ersten NULL-Test umzudrehen und früh abzubrechen:

TreeNode* Tree::parentsearch(TreeNode* root, TreeNode* node) {
    if (root == nullptr || root == node) {
        return nullptr; // nicht gefunden bzw. hat kein parent
    }
    if (root->rechts == node || root->links == node) {
        return root;
    }
    else if (node->NodePosID < root->NodePosID) {
        return parentsearch(root->links, node);
    }
    else if (node->NodePosID > root->NodePosID) {
        return parentsearch(root->rechts, node);
    }

    // Und was soll hier passieren?
    // Hier fehlt noch ein return.
}

Wie manni66 schon sagte, schalte bei deinem Compiler besser die Warnungen ein. Der würde dich dann darauf hinweisen dass nicht alle Ausführungspfade mit einem return enden.

Andere Dinge, die mir aufgefallen sind: Du sagst, parentsearch sei eine "Methode". Ich nehme an, du meinst eine nicht-statische Elementfunktion. Du rufst diese Funktion also auf einem Objekt auf. Aber mit dem Objekt machst Du gar nichts. Nirgens wird der this-Zeiger benutzt, weder explizit noch implizit. Du kannst diese Funktion also in eine statische Elementfunktion verwandeln. Außerdem solltest Du nullptr statt NULL benutzen. Bei NULL kann es böse Überraschungen geben, wohingegen nullptr eine Nullpointer-Konstante ohne Verwechselungsgefahr ist.

kleo

Danke fuer die Hilfen manni66 & krümelkacker.

Ich habe aus dem letzten "else if" ein "else" und aus allen "NULL"en "nullptr" gemacht. Soweit klappt die Funktion.