Baunstruktur/Weg finden



  • 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!



  • Globe schrieb:

    Was ich nicht ganz verstehe ist, wie er auf das "return 1" reagiert?

    Wie in main auch.
    Du weist den Rückgabewert einer Variablen zu und reagierst entsprechend.

    Globe schrieb:

    (bitte nur Tipps und keine Lösung)

    Reicht das denn?



  • Also ich hoffe, dass es reicht. 😉
    Aber auf einen Weg zum Abbrechen komme ich leider einfach nicht...



  • Folgende Idee liefert mir ein wunderbares Ergebnis:

    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{
            if(searchExit(T, T[node_no].lnode) == 1){
                return 1;
            }
        }
    }
    
    if(T[node_no].rnode == (-1)){
        return 0;
    } else{
        if(T[node_no].rnode == (-2)){
            return 1;
        } else{
             if(searchExit(T, T[node_no].rnode) == 1){
                return 1;
            }
        }
    }
    }
    


  • DirkB schrieb:

    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.

    Deine Funktion hat nicht in jedem Zweig ein return!

    Was ist z.B. wenn searchExit(T, T[node_no].rnode) eine 0 zurück gibt?

    Du kannst das ganze viel einfacher machen, indem du nur schaust, ob der aktuelle Knoten gültig ist.

    int searchExit(node_t *T, int node_no){
    
        if ( node_no == -1)
        { puts("Sackgasse");
          return 0;
        }
        if ( node_no == -2)
        { puts("Ausgang");
          return 1;
        }
    
        printf ("Knoten %d\n", node_no);
    
    // Weder Ausgang noch Sackgasse, dann hat das Teil einen lnode und rnode.
    // und die werden jetzt überprüft.
    // und wenn einer einen Ausgang (1) hat, dann macht das die Oder-Verknüpfung
    
        return  searchExit(T, T[node_no].lnode) || searchExit(T, T[node_no].rnode);
    
    }
    

    ⚠ Wenn bei lnode schon ein Ausgang gefunden wird, dann wird rnode nicht mehr überprüft.



  • Okay, danke. Ich schaus mir noch mal an.
    Wobei heute ohnehin die Übung ist, in der unser Prof das genauer erklärt.

    Aber danke für eure Hilfe! 🙂



  • Für interessierte und Leute mit ähnlichem Problem, die finale Lösung:

    int searchExit(node_t *T, int node_no){
    
    if(T[node_no].lnode == (-2) && T[node_no].rnode == (-2)){
        return 1;
    }
    
    if(T[node_no].lnode != (-1)){
            if(searchExit(T, T[node_no].lnode) == 1){
                printf("Knoten %d\n", node_no);
                return 1;
            }
    }
    
    if(T[node_no].rnode != (-1)){
             if(searchExit(T, T[node_no].rnode) == 1){
                printf("Knoten %d\n", node_no);
                return 1;
            }
    }
    
    }
    


  • Globe schrieb:

    Für interessierte und Leute mit ähnlichem Problem, die finale Lösung:

    int searchExit(node_t *T, int node_no){
    
      if(T[node_no].lnode == (-2) && T[node_no].rnode == (-2)){
        return 1;
      }
    
      if(T[node_no].lnode != (-1)){
            if(searchExit(T, T[node_no].lnode) == 1){
                printf("Knoten %d\n", node_no);
                return 1;
            }
      }
    
      if(T[node_no].rnode != (-1)){
             if(searchExit(T, T[node_no].rnode) == 1){
                printf("Knoten %d\n", node_no);
                return 1;
            }
      }
    
      Was passiert, wenn die Funktion hier angekommen ist?
    }
    

    Das ist nicht vollständig und daher (wenn es von einem Lehrer kommt) Müll!

    Ich hab es ja schon mehrfach geschrieben:
    Welchen Wert gibt die Funktion zurück, wenn sowohl lnode als auch rnode -1 sind?
    Oder wenn der jeweilige Aufruf von searchExit eine 0 zurück gibt?

    Ein passendes T kann so aussehen:

    node_t tree1 [] = { {-1, -1}, {-1, -1}, {-1, -1}, {-2,-2} };
    node_t tree2 [] = { { 1,  2}, {-1, -1}, {-1, -1}, {-2,-2} };
    

Anmelden zum Antworten