Binärer Baum...???



  • Hallo,
    Habe folgenden Code:

    struct knoten{
       int wert;
       struct knoten *links;
       struct knoten *rechts;
    };
    typedef struct knoten KNOTEN;
    int zahl;
    KNOTEN *wurzel=NULL;
    

    Mit der funktion einordnen, die folgt, wird somit eine neue zahl in dem Baum geschrieben.

    KNOTEN *einordnen(KNOTEN *zeiger)  {
       if(zeiger == NULL) {
          zeiger = (KNOTEN *)malloc(sizeof(KNOTEN));
          if(zeiger==NULL) {
             printf("Konnte keinen Speicherplatz reservieren!\n");
             exit (EXIT_FAILURE);
          }
          zeiger->wert=zahl;
          zeiger->links=zeiger->rechts=NULL;
       }
       else if(zeiger->wert >= zahl)
          zeiger->links=einordnen(zeiger->links);
       else if(zeiger->wert < zahl)
          zeiger->rechts=einordnen(zeiger->rechts);
       return (zeiger);
    }
    

    Der Code ist nicht von mir, ist von einem Buch.
    Mein Problem ist jetzt, dass ich den Code nicht richtig verstehe (einordnen Funktion).
    Verstehe schon, dass am anfang der fucktion gecheckt wird, ob der zeiger gleich null ist, wenn ja dann wird platzt freigegeben und die zahl wird als wurzel im baum geschrieben. Ich verstehe auch was man mit den beiden else if erreichen will, also ob jetzt die zahl im linken oder rechten Unterbaum geschrieben werden soll. Aber ich verstehe nicht diese stelle:

    zeiger->links=einordnen(zeiger->links);
    

    Hier wird ja die funktion nochmal abgerufen, aber der Zeiger (zeiger->links) zeigt doch immer noch auf der selben adresse oder nicht..?
    Weil wenn ja dann bringt ja der wiederaufruf ja nix.
    Sinn macht es ja nur wenn der zeiger (zeiger->links) ja nicht auf den selben knoten zeigt, sondern einen knoten weiter, damit man ja dann wieder vergleiche kann ob jetzt die zu einfügende zahl ja grösser oder kleiner als der knoten ist, worauf ja der Zeiger(zeiger->links) zeigt.
    Wo ist mein Gedankenfehler..?



  • Hab jetzt grad gemerkt, dass ich im falschen forum bin...solte in dem 'ANSI C'-Forum...!

    Bitte verschieben wenn es geht...und sorry für das Versehen..!



  • Mal dir das ganze auf, dann wirds dir klar:
    Du bist am Anfang in der Wurzel des Baumes. Du schaust nun ob der neue Wert kleiner oder größer als der Wert in der Wurzel ist. Je nach dem willst du den neuen Knoten links oder rechts von der Wurzel erzeugen.
    Du rufst die Funktion in dem Fall mit dem linken Nachfolger der Wurzel erneut auf.
    Wenn du die Funktion aufrufst mit zeiger->links, bekommt die Funktion zeiger->links als die Variable zeiger übergeben.
    Ist kein linker Nachfolger vorhanden, so wird dieser neu erzeugt, und die Wurzel zeigt nun mit zeiger->links dorthin. Ist der linke Nachfolger allerdings bereits vorhanden, wird wieder geprüft wohin verzweigt werden soll, und das Spiel beginnt von vorne.

    Übrigens stimmt der Funktionskopf nicht, du musst natürlich auch die Variable zahl übergeben!



  • Erstmal DANKE ich dir für deine Antwort..!

    harry3 schrieb:

    Mal dir das ganze auf, dann wirds dir klar:
    Du bist am Anfang in der Wurzel des Baumes. Du schaust nun ob der neue Wert kleiner oder größer als der Wert in der Wurzel ist. Je nach dem willst du den neuen Knoten links oder rechts von der Wurzel erzeugen.
    Du rufst die Funktion in dem Fall mit dem linken Nachfolger der Wurzel erneut auf.
    Wenn du die Funktion aufrufst mit zeiger->links, bekommt die Funktion zeiger->links als die Variable zeiger übergeben.
    Ist kein linker Nachfolger vorhanden, so wird dieser neu erzeugt, und die Wurzel zeigt nun mit zeiger->links dorthin. Ist der linke Nachfolger allerdings bereits vorhanden, wird wieder geprüft wohin verzweigt werden soll, und das Spiel beginnt von vorne.

    Achso, also die Funktion wird so lange laufen bis sie in dem if(zeiger==NULL)-Block "reingehen" kann, oder..?
    Mit "Ist kein linker Nachfolger vorhanden" meinst du doch if(zeiger==NULL)..?

    harry3 schrieb:

    Übrigens stimmt der Funktionskopf nicht, du musst natürlich auch die Variable zahl übergeben!

    Die Variable zahl wird auch schon übergeben, zwar bischen umständlich, mit:

    int zahl;
    

    wird die Variable zahl als globale Variable deklariert, dann kann man mit

    printf("Bitte Zahl eingeben : ");
          scanf("%d",&zahl);
          wurzel=einordnen(wurzel);
          printf("\n");
    

    die Zahl einscannen..!

    Hätte aber noch ne Frage zum selben Thema:
    Mit der Funktion

    void zeige_baum(KNOTEN *zeiger) {
       if(zeiger != NULL) {
          printf("<-%d->",zeiger->wert);
          zeige_baum(zeiger->links);
          zeige_baum(zeiger->rechts);
       }
    }
    

    werden die werte des Baumes im Terminal ausgegeben.
    Wie könnte ich denn diese Werte (also die Knoten) in einem array speichern..?
    Z.B. könnte ich mit der folgenden Funktion:

    int anz_knoten(KNOTEN *zeiger)
    {
     if(zeiger==NULL)
      return 0;
     else
      return anz_knoten(zeiger->links)+anz_knoten(zeiger->rechts)+1;
    }
    

    rausfinden wie gross das array sein soll, also..:

    int K=anz_knoten(wurzel);
     int array[K];
    

    Aber wie kann ich dann vorgehen, also wie die Werte (Knoten) in dem array[K] speichern..?
    Mich verwirren immernoch diese rekursiven Funktionen, obwohl ich die mittlerweile schon ein wenig verstehe.



  • Dieser Thread wurde von Moderator/in estartu aus dem Forum MFC (Visual C++) in das Forum ANSI C verschoben.

    Im Zweifelsfall bitte auch folgende Hinweise beachten:
    C/C++ Forum :: FAQ - Sonstiges :: Wohin mit meiner Frage?

    Dieses Posting wurde automatisch erzeugt.



  • Hallo!

    Wie du richtig geschrieben hast musst du zuerst mal rausfinden wieviele Knoten der Baum hat.
    Dann erzeugst du dynamisch ein Feld:
    int *feld=0;
    feld=malloc( knoten_anzahl * sizeof(datentyp) ); //am programmende free(feld) nicht vergessen!!!

    Nun hast du ja die zeige_baum Funktion. Anstatt dem printf schreibst du dort die Zuweisungszeile hin.
    feld[index]=zeiger->wert;
    index++;

    Das primitivste wäre index global anzulegen und dann einfach jedes mal um 1 zu erhöhen. Natürlich kannst du es aber auch lokal lösen, aber bei kleinen Programmen darf man sich durchaus ein paar globale Variablen erlauben;-)

    Grüße,
    Harri



  • DANKESCHÖN...!
    Hat funktioniert..!
    Nur so als Frage, wieso kann ich so:

    // Globale Variable
    int K=anz_knoten(wurzel);
    int array[K];
    

    kein array mit soviele int-Werte, die ich brauche(anz_knoten-Funktoin) deklarieren..?
    Und kann es ohne Probleme mit deiner Version, also mit dem Zeiger und mit malloc.

    Weil wenn ich das so versuche, also mit int array[K] kommt immer der Compilerfehler "variable-size type declared outside of any funktion".
    Und wenn ich zum Beispiel global ein array deklariere, z.B. so:

    // global
    int array[100];
    

    wird kein fehler ausgegeben....wieso..?
    Nicht das ich es unbedingt so schreiben will, mit reicht deine lösung 100% und bedanke mich nochmal bei dir, bin nur neugierig wieso es so nicht geht, obwohl es für mich jedefalls logisch scheint.(also dass es gehen sollte..!)

    !..MFG Bonafide..!



  • Der Unterschied ist folgender:
    Wenn du schreibst:
    int array[100], so ist zur Compilezeit klar wie groß das Feld sein soll. Das passt.

    Wenn du allerdings folgendes schreibst, so ist erst zur Laufzeit klar, wie groß das Feld werden soll, und das geht nicht:
    int K=anz_knoten(wurzel);
    int array[K];
    Mit C kann man so einfach kein Feld erzeugen, wo erst zur Laufzeit klar ist, wie groß es sein wird.

    Man muss daher mit malloc Speicher vom Betriebssystem anfordern. Diesen Speicher kann man nun wie ein Feld betrachten, d.h. du kannst ganz normal mit dem Indexoperator [] drauf zugreifen wie auf ein normales Feld.
    Wenn man das Feld nimmer braucht, kann man es mittels free wieder freigeben.

    Bei großen Programmen ist das hilfreich denn sobald ein bestimmtes Feld nimmer gebraucht wird kann man es freigeben, und dieser Speicher steht dann wieder für andere Dinge zur Verfügung.



  • Aso, jetzt verstehe ich das..!
    Also immer mit malloc speicher anfordern..!

    THX nochmals..!

    !..MFG BFK..!


Log in to reply