Baunstruktur/Weg finden



  • Hallo!
    Ich habe folgende Aufgabe gegeben:
    Implementieren Sie eine Funktion int searchExit(node_t *T, int node_no); die den Wert 0 zurückliefert, falls kein Ausgang gefunden wurde und ansonsten den Wert 1
    zurückliefert.
    Mit meinem Code bin ich an sich zufrieden (falls er falsch sein sollte, bitte ich um Anregungen). Mein Problem besteht eher darin, dass ich nicht darauf komme, welchen Wert ich der Funktion für "node_no" mitgeben soll, sodass ich durch die Baumstruktur laufe?

    Danke schon mal! 🙂

    #include<stdio.h>
    #include<math.h>
    typedef struct{
    int lnode, rnode ;
    } node_t;
    
    node_t tree [] = {
    {1, 2}, {3, 4}, {5, 6}, {-1, 7}, {8, 9}, {10, 11}, {12, -1},
    {-1, -1}, {13, 14}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1},
    {15, 16}, {-1, -1}, {-1, -1}, {-2, -2}
    };
    
    int searchExit(node_t *T, int node_no);
    
    int main(void){
    
    if(searchExit(tree, 0) == 1){
        printf("Ausgang gefunden !\n");
    } else{
        printf("\n  Kein Ausgang gefunden.\n");
    }
    return 0;
    }
    
    int searchExit(node_t *T, int node_no){
        printf("-------------------\nKnoten: %d\n\nWerte: %d und %d\n\n", node_no, T[node_no].lnode, T[node_no].rnode);
    
    if(T[node_no].lnode == (-1)){
        return 0;
    } else{
        if(T[node_no].lnode == (-2)){       
            return 1;
        } else{
            searchExit(tree, ???);
        }
    }
    
    if(T[node_no].rnode == (-1)){
        return 0;
    } else{
        if(T[node_no].rnode == (-2)){       
            return 1;
        } else{
            searchExit(tree, ???);
        }
    }
    
    }
    


  • Du hast jetzt festgestellt, dass vom aktuellen Knotenein (zumindest) ein Weg zu einem anderen Knoten führt.

    Und du sollst solange die Knoten folgen, bis du einen Ausgang oder Ende hast.

    Welchen Knoten kannst du da angeben?

    Das Ergebnis von searchExit musst du bei jedem Aufruf auswerten.



  • ... und was passiert, wenn links kein Ausgang ist, aber rechts?



  • Man startet am Index 0 also (1,2) und als Zielknoten dient der letzte Index, demnach (-2,-2).
    Folgen soll man solange, bis man bei left = -2 oder right = -2 angekommen ist.
    Dementsprechend wird dann 1 zurückgegeben und die Funktion beendet.
    Ansonsten wird bei 0 zurückgegeben und ,,zurückgesprungen''.
    (Eben rekursives backtracking).

    WENN mein code so stimmt, fehlt mir nur der Index, für node_no, auf den ich aber bisher noch nicht gekommen bin?



  • DirkB:

    Also müsste ich links ( rechts) noch eine Überprüfung auf (-2) für die jeweils andere Seite einfügen, sodass nicht zurückgesprungen wird, wenn links ( rechts) gleich -1 ist?



  • Globe schrieb:

    WENN mein code so stimmt, fehlt mir nur der Index, für node_no, auf den ich aber bisher noch nicht gekommen bin?

    Auf wie viele Knoten hast du denn an der Stelle Zugriff?
    Das eine wäre node_no vom Aufruf. Das wäre aber Blödsinn.

    Welche anderen Knoten kennst du ganz sicher noch in der Funktion?
    (es können zwei sein)



  • Zugriff habe ich pro Aufruf doch immer nur auf einen Knoten, der der mir durch den Funktionsaufruf mitgegeben wird.

    lnode und rnode sind doch die WERTE in dem mitgegebenen Knoten, oder?



  • Globe schrieb:

    Zugriff habe ich pro Aufruf doch immer nur auf einen Knoten, der der mir durch den Funktionsaufruf mitgegeben wird.

    lnode und rnode sind doch die WERTE in dem mitgegebenen Knoten, oder?

    Wenn in lnode oder rnode positive Werte drin stehen, sind das doch andere Knoten (Da du den Aufbau deiner Struktur /Baum nicht erklärt hast, rate ich das mal).

    Also weißt du doch, dass es sie gibt.



  • Das liegt daran, dass ich es recht schwer finde, eine Baumstruktur mittels Text zu erklären. Aber ich will es versuchen:

    Ich habe meine Baum so aufgebaut, dass ein Feldindex einen Knoten darstellt.
    Jeder dieser Knoten beinhaltet 2 Werte. So beinhaltet z.B. die Wurzel
    (Feldindex 0) die Werte (1,2) und das Ziel, der letzte Feldindex, die Werte (-2,-2). Bei (-1) folgt kein weiterer Kindknoten mehr.

    Von der Struktur:
    --------------------0---------------------
    ------------1--------------2--------------
    -----3----------4-------5-----6----------- usw.



  • Ja, so habe ich mir das gedacht.

    Nochmal: im Knoten 0 hast du kentniss von zwei anderen Knoten: 1 und 2.
    Wäre es evtl. möglicherweise unter Umständen sinnvoll, in diesen Knoten nachzusehen, ob dort der Asugang ist?



  • Evtl. möglicherweise unter Umständen wäre das eigentlich sinnvoll, jap.
    Also Gebe ich immer einen Indext mit - Am Anfang 0, dann 1, 2, 3, usw - und gucke, ob in dessen Kindern die -2 enthalten ist?

    Ich versuch's mal, und mede mich na^chher noch einmal. ^^
    Danke dir.



  • Aber mein Code an sich stimmt soweit?
    Nicht, dass ich jetzt ewig nach dem Wert für node-no suche aber mein Code Schwachsinn ist?



  • Also, ich habe jetzt sehr sehr viele Möglichkeiten ausprobiert..
    Aber mein Problem bleibt immer noch das selbe.
    WELCHE WERTE soll ich meiner Funktion für node_no mitgeben, sodass ich den Baum entlang laufen kann???
    Ich habe ja lediglich Indizes??



  • Mittlerweile sieht mein Code folgendermaßen aus:
    (DIe Werte für node_no fehlen leider immer noch. 😕

    #include<stdio.h>
    #include<math.h>
    typedef struct{
    int lnode, rnode ;
    } node_t;
    
    node_t tree [] = {
    {1, 2}, {3, 4}, {5, 6}, {-1, 7}, {8, 9}, {10, 11}, {12, -1},
    {-1, -1}, {13, 14}, {-1, -1}, {-1, -1}, {-1, -1}, {-1, -1},
    {15, 16}, {-1, -1}, {-1, -1}, {-2, -2}
    };
    
    int n = -1;
    
    int searchExit(node_t *T, int node_no);
    
    int main(void){
    
    if(searchExit(tree, 0) == 1){
        printf("Ausgang gefunden !\n");
    } else{
        printf("\n  Kein Ausgang gefunden.\n");
    }
    return 0;
    }
    
    int searchExit(node_t *T, int node_no){
    if(T[node_no].lnode == (-2) || T[node_no].rnode == (-2)){
    
        printf("Ausgang bei %d", node_no);
        return 1;
    
    } else {
        if(T[node_no].lnode == (-1)){
            /*keinen linken nachfolger*/
            printf("keinen links bei %d\n", node_no);
            searchExit(tree, node_no+pow(2, n-1)-1);
        }
        else if(T[node_no].rnode != (-1)){
            printf("Gehe weiter bei: %d\n", node_no);
            searchExit(tree, node_no+pow(2, n+1));
        }
        if(T[node_no].rnode == (-1)){
            printf("keinen rechts bei %d\n", node_no);
            /*keinen rechten Nachfolger*/
            searchExit(tree, node_no+pow(2, n-1)-1);
        }
    }
    }
    


  • Globe schrieb:

    Ich habe ja lediglich Indizes??

    Reichen die nicht?
    Oder was ist das für ein Wert, den du in main an die Funktion übergibst?

    Und schalte mal die Compilerwarnungen auf Maximum.
    Da muss (im jetzigen Zustand) eine Warnung kommen, dass die Funktion nicht in jedem Zweig ein return hat.



  • Hallo Globe,

    dein letzter Code ist aber schlechter als dein zu erst gezeigter Code.

    Der Algorithmus ist doch:
    - suche zuerst im linken Teilbaum
    - suche danach im rechten Teilbaum

    Und wenn du den Ausgang gefunden hast, dann gebe 1 zurück.
    Und genau dies mußt du eben auch rekursiv ausprogrammieren, d.h. du mußt den Rückgabewert deines rekursiven searchExit(...)-Aufrufs auswerten.
    Und als jeweiligen Unterbaum mußt du eben den Index übergeben (T[node_no].lnode bzw .rnode).



  • Also gebe ich als node_no die Werte lnode oder rnode mit und nicht den jeweiligen Index des Feldes, oder habe ich da etwas falsch verstanden?

    Aber in meinem ersten Code bin ich doch gar nicht darauf eingegangen, was passiert, wenn ich bei einer (-1) angekommen bin?
    Ich kann dann doch nicht einfach 0 zurückgeben, sondern muss darauf reagieren, indem ich zurückspringe?

    Danke!



  • Also wenn ich die Werte von lnode bzw rnode mitgebe, ist die Ausgabe schon mal wesentlich sinnvoller!
    Ich werde mich der Aufgabe wieder am Montag widmen, danke erstmal!!



  • lnode bzw. rnode stellen doch die Indizes der Felder dar.

    Und bei deinem ersten Code machst du doch bei -1 alles richtig, nämlich 0 zurückgeben (also "kein Ausgang gefunden"). Das Entscheidende ist dann wie du auf die Rückgabe von dem rekursiven searchExit()-Aufruf reagierst.

    Als Tipp:
    In deinem ersten Code mußt du noch jeweils für node und rnode 2 Zeilen ändern (bzw. 1 hinzufügen).
    Und dann mußt du noch den Fall betrachten, wenn deine Funktion bei der letzten Zeile angekommen ist -> was soll dann zurückgegeben werden?

    Und wenn du diesen Code dann lauffähig hast, dann wirst du sehen, daß der Code für rnode und lnode (fast) identisch ist, so daß du diesen in eine eigene Funktion auslagern kannst.
    Deine Hauptfunktion könnte dann einfach so aussehen:

    int searchExit(node_t *T, int node_no)
    {
      return searchExitNode(T, T[node_no].lnode) > 0 ||
             searchExitNode(T, T[node_no].rnode) > 0;
    }
    

    PS: Du solltest natürlich generell in dieser Funktion den Parameter T benutzen und nicht die globale Variable tree (auch wenn die jetzt für dieses Programm gleich ist).



  • Ich habe es jetzt erst mal so geändert:

    if(T[node_no].lnode == (-1)){
        return 0;
    } else{
        if(T[node_no].lnode == (-2)){
            return 1;
        } else{
            searchExit(T, T[node_no].lnode);   //Also hier
        }
    }
    
    if(T[node_no].rnode == (-1)){
        return 0;
    } else{
        if(T[node_no].rnode == (-2)){
            return 1;
        } else{
            searchExit(T, T[node_no].rnode);  //Und hier
        }
    }
    

    Was ich nicht ganz verstehe ist, wie er auf das "return 1" reagiert?
    Die Ausgabe ergibt, dass er dort ankommt, und anschließend durch alle weiteren Knoten läuft...?
    Wie sorge ich denn dafür, dass er am "Ausgang" abbricht und nach Main zurückkehrt? (bitte nur Tipps und keine Lösung)

    Danke!


Log in to reply