Binärer Baum mit bestimmter höhe erstellen



  • Ich möchte einen Binären Baum mit einer variablen Höhe erstellen und
    mit Zufallswerten von 0 bis 3 initialisieren. Diese Zufallswerte dürfen überall im Baum stehen. Dieser Baum muss also nicht geordnet sein.

    // structure representing a branch
    typedef struct Branch{	
    	bool dry;               
    	int a; //a ist hier die Variable in der die Zahl zwischen 0 und 3 gespeichert wird
    	struct Branch* left;
    	struct Branch* right;
    } Branch;
    
    typedef struct{
    	int height;
    	Branch* branch;
    } Tree;
    

    Ich brauche dann zum Beispiel folgende Funktion Tree* make_tree(int height) die mir einen Baum bestimmter höhe erstellt. Ich kann das selber implementieren nur fehlt mir der algorithmus dazu einen Baum beliebiger höhe zu erstellen.

    Gruß Die Cannabiene



  • sowas in der Art?

    Branch* make_random_tree(int height) {
      Branch* result = malloc(sizeof Branch);
      result->a = rand() % 4;
      if (height == 0) {
        result->left = result->right = 0;
      } else {
        result->left = make_random_tree(height - 1);
        result->right = make_random_tree(height - 1);
      }
      return result;
    }
    


  • Bashar schrieb:

    sowas in der Art?

    Branch* make_random_tree(int height) {
      Branch* result = malloc(sizeof Branch);
      result->a = rand() % 4;
      if (height == 0) {
        result->left = result->right = 0;
      } else {
        result->left = make_random_tree(height - 1);
        result->right = make_random_tree(height - 1);
      }
      return result;
    }
    

    Ja das passt schon recht genau. Danke.
    Hier mal das was ich bis dahin geschrieben habe:

    Branch* make_random_branch(int height){
        Branch* result = xmalloc(sizeof(Branch));
        result->a = i_rnd(4);
        if (height == 0) {
            result->left = NULL;
            result->right = NULL;
        }
        else{
            result->left = make_random_branch(height - 1);
            result->right = make_random_branch(height - 1);
        }
        return result;
    }
    
    Tree* make_tree(int height){
        Tree* mytree = xmalloc(sizeof(Tree));
        mytree->height = height;
        mytree->branch = make_random_branch(height);
        return mytree;
    }
    
    void free_tree(Tree *mytree){
        if(mytree == NULL){
            free(mytree);
            return;
        }
        else if(mytree->height > 0){
    
        }
    
    }
    

    Die Funktion free_tree soll den gesamten Speicherplatz wieder freigeben. Diese muss ich auch noch implementieren und da komme ich momentan auch nicht weiter. Ich muss xmalloc und xcalloc sind Funktionen in einer externen Library die das Programm terminieren sobald kein Speicherplatz angefordert werden kann. Außerdem geben sie mir nach der Ausführung des Programms, eine Übersicht wo noch Speicherlecks existieren. Diese möchte ich mit der Funktion free_tree beheben. Ich muss also auch wieder rekursiv durch den tree gehen um den vorher allozierten Speicher frei zu geben. Ich weiß aber auch hier leider nicht wie ich das anstellen soll.


  • Mod

    Die Idee ist doch genau die gleiche: Um einen Knoten freizugeben, muss er erst seine beiden Unterknoten freigeben (sofern vorhanden), dann sich selber. Wo ist das Problem? Meine deutsche Beschreibung ist fast 1:1 in C übersetzbar.



  • Hallo,

    das machst du durch Rekursion über die Branch -Struktur. Wenn es einen linken Nachfolger gibt, lösche diesen (rekursiv). Wenn es einen rechte Nachfolger gibt, lösche diesen. Dann gib den aktuellen Knoten frei.

    Du musst dich dabei zwischen zwei Varianten entscheiden:

    // 1
    void free_node(Branch* b) {
      if (b != 0) {
        // ...
        // freigeben
        // ...
      }
    }
    
    // 2
    void free_node(Branch* b) {
      // ...
      if (b->left != 0) free_node(b->left);
      // ...
    }
    

    Welche du wählst, hängt von free_tree ab, oder ob du die Funktion auch anderweitig aufrufen willst, und ob Bäume leer sein können.



  • Bashar schrieb:

    Hallo,

    das machst du durch Rekursion über die Branch -Struktur. Wenn es einen linken Nachfolger gibt, lösche diesen (rekursiv). Wenn es einen rechte Nachfolger gibt, lösche diesen. Dann gib den aktuellen Knoten frei.

    Du musst dich dabei zwischen zwei Varianten entscheiden:

    // 1
    void free_node(Branch* b) {
      if (b != 0) {
        // ...
        // freigeben
        // ...
      }
    }
    
    // 2
    void free_node(Branch* b) {
      // ...
      if (b->left != 0) free_node(b->left);
      // ...
    }
    

    Welche du wählst, hängt von free_tree ab, oder ob du die Funktion auch anderweitig aufrufen willst, und ob Bäume leer sein können.

    Habs jetzt so implementiert und es funktioniert nicht. Kann mir das nicht erklären. Bin den Programmablauf auf einem Blatt Papier nachgegangen. Hier mein Code mit der free funktion.

    #include "base.h"
    // structure representing a branch
    typedef struct Branch{
        int a; //a ist hier die Variable in der die Zahl zwischen 0 und 3 gespeichert wird
        struct Branch* left;
        struct Branch* right;
    } Branch;
    
    typedef struct{
        int height;
        Branch* branch;
    } Tree;
    
    Branch* make_random_branch(int height){
        Branch* result = xmalloc(sizeof(Branch));
        result->a = i_rnd(4);
        if (height == 0) {
            result->left = NULL;
            result->right = NULL;
        }
        else{
            result->left = make_random_branch(height - 1);
            result->right = make_random_branch(height - 1);
        }
        return result;
    }
    
    Tree* make_tree(int height){
        Tree* mytree = xmalloc(sizeof(Tree));
        mytree->height = height;
        mytree->branch = make_random_branch(height);
        return mytree;
    }
    
    void free_node(Branch *b){
        while (b->left != NULL){
            free_node(b->left);
        }
    
        while (b->right != NULL){
            free_node(b->right);
        }
    
        free(b);
        b = NULL;
    }
    
    int main (void) {
        base_init();          
        base_set_memory_check(true); //hier nur Funktionen die am ende des Programs anzeigt ob der Speicher gefreed wurde oder nicht.
    
        Branch *mybranch = make_random_branch(1);
        printf("%i\n", mybranch->a);
        //printf("%i\n", mybranch->left->right->a);
    
        free_node(mybranch);
        return 0;
    }
    

    Das Program hat folgenden output:

    $ ./total
    3
    base_free: trying to free unknown pointer 0x7f98e7500000
    total(5291,0x7fffb0b5f340) malloc: *** error for object 0x7f98e7500000: pointer being freed was not allocated
    *** set a breakpoint in malloc_error_break to debug
    Abort trap: 6
    

    Das Program heißt total
    Ich weiß nicht warum das passiert.



  • Warum die while -Schleifen in free_node?

    Das b = NULL; hat keine Auswirkung auf irgendetwas außerhalb der Funktion, da b ein lokaler Zeiger ist.
    Danach ist die Funktion vorbei und b existiert nicht mehr.



  • Mein erster Ansatz war auch folgender:

    void free_node(Branch* b) {
         if (b->left != NULL){
             free_node(b->left);
         }
         else{
             if(b->right != NULL){
                free_node(b->right);
             }
             else{
                 free(b);
                 b = NULL;
             }
         }
    }
    

    Es wird geguckt ob der linke Zweig = NULL ist und wenn das der Fall ist dann wird geguckt ob der rechte Zweig = NULL ist. Dann kann b doch freigegeben werden und die funktion endet. Wenn ich b = NULL schreibe, dann ist b das doch auch ausserhalb der Funktion, da b doch ein Zeiger ist?

    B0
        / \
       B1  B2
      / \ / \
     0  0 0  0
    

    Mein Baum sieht z.B. wie oben aus. Dann geht die Funktion ja erst in den B1 Ast und sieht dann das B1->left und B1->right == NULL sind. Deshalb darf man ja free(B1) machen. Danach überprüft die Funktion ob B0->left == NULL ist . Hier soll das dann der Fall sein. und dann geht die Funktion in den rechten zweig und macht da das gleiche so das im zweiten Schritt der Baum dann wie folgt aussehen soll:

    B0
          /  \
         0    0
    

    In dem Fall darf man ja auch free(B0) machen.

    Bei mir hapert es an der implementierung.



  • Cannabiene schrieb:

    Es wird geguckt ob der linke Zweig = NULL ist und wenn das der Fall ist dann wird geguckt ob der rechte Zweig = NULL ist.

    Das steht da nicht. Aber auch diese Beschreibung ist falsch.
    DAs hast du gerade beschrieben:

    if (b->left != NULL){
             free_node(b->left);
             if(b->right != NULL){
                free_node(b->right);
             }
      }
    

    Das ist die Beschreibung deiner Funktion:
    Es wird geguckt ob der linke Zweig ungleich NULL ist und wenn das nicht der Fall ist dann wird geguckt ob der rechte Zweig ungleich NULL ist.

    Wenn der linke  Zweig ungleich 0 ist, gib ihn frei, 
    wenn der rechte Zweig ungleich 0 ist, gib ihn frei.
    // Jetzt sind alle Zweige frei.
    Gib den Knoten frei.
    

    Da gibt es keine Verschachtelung und kein else.

    Nochmal

    DirkB schrieb:

    Warum die while-Schleifen in free_node?



  • DirkB schrieb:

    Cannabiene schrieb:

    Es wird geguckt ob der linke Zweig = NULL ist und wenn das der Fall ist dann wird geguckt ob der rechte Zweig = NULL ist.

    Das steht da nicht. Aber auch diese Beschreibung ist falsch.
    DAs hast du gerade beschrieben:

    if (b->left != NULL){
             free_node(b->left);
             if(b->right != NULL){
                free_node(b->right);
             }
      }
    

    Das ist die Beschreibung deiner Funktion:
    Es wird geguckt ob der linke Zweig ungleich NULL ist und wenn das nicht der Fall ist dann wird geguckt ob der rechte Zweig ungleich NULL ist.

    Wenn der linke  Zweig ungleich 0 ist, gib ihn frei, 
    wenn der rechte Zweig ungleich 0 ist, gib ihn frei.
    // Jetzt sind alle Zweige frei.
    Gib den Knoten frei.
    

    Da gibt es keine Verschachtelung und kein else.

    Nochmal

    DirkB schrieb:

    Warum die while-Schleifen in free_node?

    Hier meine free_node funktion. Funktioniert immer noch nicht. Ich habs jetzt so implementiert wie du es mir gesagt hast:

    Wenn der linke  Zweig ungleich 0 ist, gib ihn frei, 
    wenn der rechte Zweig ungleich 0 ist, gib ihn frei.
    // Jetzt sind alle Zweige frei.
    Gib den Knoten frei.
    
    void free_node(Branch* b) {
        if (b->left == NULL){
            free(b->left);
        }
        else{
            free_node(b->left);
        }
    
        if (b->right == NULL){
            free(b->right);
        }
        else{
            free_node(b->right);
        }
    
        free(b);
    
    }
    

    Ausgabe des Programms:

    3
    base_free: trying to free unknown pointer 0x0
    base_free: trying to free unknown pointer 0x0
    base_free: trying to free unknown pointer 0x0
    base_free: trying to free unknown pointer 0x0
    

    Wenn ich das "free(b)" in der Funktion auskommentiere dann ist der output:

    0
    base_free: trying to free unknown pointer 0x0
    base_free: trying to free unknown pointer 0x0
    base_free: trying to free unknown pointer 0x0
    base_free: trying to free unknown pointer 0x0
       24 bytes allocated in make_random_branch (total.c at line 27) not freed
       24 bytes allocated in make_random_branch (total.c at line 27) not freed
       24 bytes allocated in make_random_branch (total.c at line 27) not freed
    3 memory leaks, 72 bytes total
    


  • Cannabiene schrieb:

    Hier meine free_node funktion. Funktioniert immer noch nicht. Ich habs jetzt so implementiert wie du es mir gesagt hast:

    Sorry, das war nicht ganz korrekt formuliert.

    Wenn der linke  Zweig ungleich 0 ist, rufe free_node(links) auf
    wenn der rechte Zweig ungleich 0 ist, rufe free_node(rechts) auf
    // Jetzt sind alle Zweige frei.
    Gib den Knoten frei.
    
    void free_node(Branch* b) {
        if (b->left != NULL){       
            free_node(b->left);
        }
    
        if (b->right != NULL){
            free_node(b->right);
        }
    
        free(b);
    
    }
    

    Wärst du vielleicht auch selber drauf gekommen, hättest du mal über

    DirkB schrieb:

    Warum die while-Schleifen in free_node?

    nachgedacht.



  • DirkB schrieb:

    Cannabiene schrieb:

    Hier meine free_node funktion. Funktioniert immer noch nicht. Ich habs jetzt so implementiert wie du es mir gesagt hast:

    Sorry, das war nicht ganz korrekt formuliert.

    Wenn der linke  Zweig ungleich 0 ist, rufe free_node(links) auf
    wenn der rechte Zweig ungleich 0 ist, rufe free_node(rechts) auf
    // Jetzt sind alle Zweige frei.
    Gib den Knoten frei.
    
    void free_node(Branch* b) {
        if (b->left != NULL){       
            free_node(b->left);
        }
       
        if (b->right != NULL){
            free_node(b->right);
        }
          
        free(b);
       
    }
    

    Wärst du vielleicht auch selber drauf gekommen, hättest du mal über

    DirkB schrieb:

    Warum die while-Schleifen in free_node?

    nachgedacht.

    Danke das funktioniert so. Hier noch mal mein kompletter Code:

    #include "base.h"
    // structure representing a branch
    typedef struct Branch{
        int a; //a ist hier die Variable in der die Zahl zwischen 0 und 3 gespeichert wird
        struct Branch* left;
        struct Branch* right;
    } Branch;
    
    typedef struct{
        int height;
        Branch* branch;
    } Tree;
    
    Branch* make_random_branch(int height){
        Branch* result = xmalloc(sizeof(Branch));
        result->a = i_rnd(4);
        if (height == 0) {
            result->left = NULL;
            result->right = NULL;
        }
        else{
            result->left = make_random_branch(height - 1);
            result->right = make_random_branch(height - 1);
        }
        return result;
    }
    
    Tree* make_tree(int height){
        Tree* mytree = xmalloc(sizeof(Tree));
        mytree->height = height;
        mytree->branch = make_random_branch(height);
        return mytree;
    }
    
    void free_node(Branch* b) {
        if (b->left != NULL){
            free_node(b->left);
        }
        if (b->right != NULL){
            free_node(b->right);
        }
        free(b);
    }
    
    int main (void) {
        base_init();
        base_set_memory_check(true);
    
        Branch *mybranch = make_random_branch(15);
        printf("%i\n", mybranch->a);
    
        free_node(mybranch);
        return 0;
    }
    

    Mir fällt auf das die free_node Funktion sehr lange braucht um den Speicher wieder frei zu geben. Bei make_random_branch(10) vergeht fast keine Zeit bei make_random_branch(15) dauert es schon ein paar Sekunden und bei make_random_branch(20) dauert es so lange sodass ich das Programm vorher abgebrochen habe. Gibt es eine Methode den Speicher schneller frei zu geben?



  • Hast du dir mal überlegt, wieviele Knoten bei einem Baum der Tiefe 15 oder 20 erzeugt werden?

    Du kannst dir auch mal die verschiedenen Heap-Datenstrukturen anschauen.



  • Th69 schrieb:

    Hast du dir mal überlegt, wieviele Knoten bei einem Baum der Tiefe 15 oder 20 erzeugt werden?

    Du kannst dir auch mal die verschiedenen Heap-Datenstrukturen anschauen.

    Bei einer tiefe von 15 sind das 65535 Knoten. man rechnet 2^0 +2^1+ 2^2 +...+ 2^15

    Den Baum zu initialisieren geht aber viel schneller als den Speicher wieder frei zu geben. Warum ist das so und warum dauert das nicht gleich lange?

    Bei einer Tiefe von 25 zeigt mein Taskmanager an das ca 5Gb belegt werden. Die free Funktion braucht deshalb ewig. Wenn ich das Programm aber mit Control C abbreche, dann gibt OSX den Speicher sofort wieder frei. Also irgendwie kann jedenfalls OSX das deutlich schneller freigeben.


  • Mod

    Cannabiene schrieb:

    Bei einer Tiefe von 25 zeigt mein Taskmanager an das ca 5Gb belegt werden. Die free Funktion braucht deshalb ewig. Wenn ich das Programm aber mit Control C abbreche, dann gibt OSX den Speicher sofort wieder frei. Also irgendwie kann jedenfalls OSX das deutlich schneller freigeben.

    Der große Unterschied ist halt, dass bei der einen Variante genau Buch geführt werden muss, wo nun Speicher frei verfügbar ist. Schließlich kann der Speichermanager nicht wissen, dass du dein Programm danach beenden willst. Wenn es weiter läuft und mehr Speicheranforderungen macht, muss schließlich bekannt sein, wo was liegt. Bei der anderen Variante kann hingegen pauschal einfach alles abgerissen werden, was irgendwie zu deinem Programm gehört.



  • Da passt trotzdem was nicht. free kann durchaus langsamer sein als malloc, aber normalerweise sollte sich der Unterschied in Grenzen halten.

    Startest du aus dem Debugger heraus, debug heap?
    Könnte auch mit dem base_set_memory_check zusammenhängen.



  • Das ist doch gar nicht malloc/free, sondern so ein gechecktes xmalloc/xfree. Wer kann da schon sagen, wie schnell die Operationen sind?

    xmalloc und xcalloc sind Funktionen in einer externen Library die das Programm terminieren sobald kein Speicherplatz angefordert werden kann. Außerdem geben sie mir nach der Ausführung des Programms, eine Übersicht wo noch Speicherlecks existieren.


Log in to reply