Wie lösche ich Elemente in einem Binärbaum in C?

Question

Ich versuche, das Löschen von Knoten in einem Binärbaum zu verstehen. Dies ist das Code-Snippet, das ich im Tutorial gefunden habe, das dasselbe erklärt.

Der Knoten sieht wie folgt aus:

struct node 
{ 
    int key_value; 
    struct node *left; 
    struct node *right; 
}; 

Quelle: http://www.cprogramming.com/tutorial/c/lesson18.html

void destroy_tree(struct node *leaf) 
    { 
     if(leaf != 0) 
     { 
      destroy_tree(leaf->left); 
      destroy_tree(leaf->right); 
      free(leaf); 
     } 
    } 

Mein Zweifel ist in Bezug auf die free(leaf) Teil. Ich meine, der Autor behauptet, dass dies rekursiv alle Knoten löschen wird, die von der unteren linken beginnen. Aber ist nicht free(leaf) nur den Speicher des Blattzeigers frei? Sind nicht alle Knoten noch verbunden? Wie erfolgt die Räumung?

Answer 1

Sie haben Recht. Es beansprucht den Speicher von Cs "Allocated Memory", was höchstwahrscheinlich der Heap ist. Da Sie den Baum WHOLE löschen, spielt es keine Rolle, dass Sie die Knoten nicht richtig rekonstruieren, da sie den Baum rekurieren, weil sie ebenfalls zerstört werden.

Dieser Code löscht kein Element aus dem Baum, sondern zerstört den gesamten Baum bei einem Blattknoten. Baum:

Von der Website

Die destroy_tree unter der tatsächlich frei alle Knoten des in dem Baum unter dem Knoten Blatt gespeichert gezeigt.

Answer 2

In den Link Sie den Autor geschrieben habe hat einen Baum, der wie folgt aussieht:

      10 
        / \ 
         6  14 
        /\ /\ 
        5 8 11 18 

Die rekursive Löschfunktion funktioniert, indem Sie den ganzen Weg auf der linken Seite, dann die rechte Seite dann den Knoten löschen. So in den über der folgenden passieren wird (beginnend mit dem Knoten, enthaltend 10)

Node 10 -> leaf!=null -> destroy_leaf(leaf->left) 
    Node 6 -> leaf!=null -> destroy_leaf(leaf->left) 
    Node 5 -> leaf!=null -> destroy_leaf(leaf->left) 
     null -> do nothing and return back to Node 5 
    Node 5 - destroy_leaf(leaf->right) 
     null -> do nothing and return back to Node 5 
    free(Node 5) and return back to Node 6 
    Node 6 -> destroy->leaf(leaf->right) 
    Node 8 -> leaf!=null -> destroy_leaf(leaf->left) 
     null -> do nothing and return back to Node 8 
    Node 8 -> destroy_leaf(leaf->right) 
     null -> do nothing and return back to Node 8 
    free(node 8) and return back to Node 6 
    free(node 6) and return back to Node 10 
Node 10 -> destroy_left(leaf->right) 

Die oben zeigt, wie die Funktion rekursiv die linke Seite von dem Knoten 10. Da die Knoten free d der Eltern sind, weisen auf Speicher, der freigegeben wurde, aber das ist in Ordnung, da Sie den Elternknoten schließlich verwerfen, wenn die Rekursion den Elternknoten abwickelt und freigibt.

Answer 3

Aber ist nicht frei (Blatt) nur die Erinnerung an den Blattzeiger zurück?

Ja. Aber das ist nicht die ganze Geschichte. Schauen Sie kurz über dem Anruf an free, wie sehen Sie genannt werden?

Sind nicht alle Knoten noch verbunden?

Hat da keine Rolle ...

Wie erfolgt die Clearing Stelle?

die rekursive Aufrufe von destroy_tree absteigend nach unten links und rechts, was wiederum zu tun rekursive Zerstörung wird, und am Ende es befreit, kehrt an den Anrufer, die und so weiter befreit. Am Ende wurde der ganze Baum befreit.

Answer 4

Ich zeige Ihnen grafisch wie würde Baum ändern:

START:

    10 
      / \ 
       6  14 
      /\  /\ 
      free 8 11 18 

        10 
      / \ 
       6   14 
      / \  /\ 
      free free 11 18 


        10 
      /  \ 
       free  14 
      / \  /\ 
      free free 11 18 


        10 
       /  \ 
       free   14 
      / \  / \ 
      free free free 18 

        10 
       /  \ 
       free   14 
      / \  / \ 
      free free free free 

        10 
       /  \ 
       free   free 
      / \  / \ 
      free free free free 

        free 
       /  \ 
       free   free 
      / \  / \ 
      free free free free 

Natürlich am Ende sind Knoten nicht verbunden, sie existieren nicht mehr. Ich habe nur im Bild gezeigt, wie sie sich im Laufe dieses Algorithmus verändern würden. Wenn Sie weitere Fragen haben, zögern Sie nicht zu fragen.

Ich empfehle Ihnen, dass, wann immer Sie nicht verstehen, wie Baumrekursion Arbeit, auf Blatt Papier ein Bild schreiben und dann gehen Algorithmus, wie ich oben schrieb.

Answer 5

Es löscht das Blatt und seine Zweige rekursiv. Ich zeichne eine Probe für Sie. Die Zahlen im Kreis zeigen die Reihenfolge der Blätter, die freigegeben werden. Die Linien zeigen die Reihenfolge der Ausführung von Code

Answer 6

free(leaf) Der Aufruf des Speichers freigibt, die für die variable zugewiesen wurde, die an leaf durch den Zeiger gezeigt wird. Hier werden alle 12 Bytes freigegeben, die eine Variable vom Typ struct node belegt - d. H. Die 4 Bytes für den int value, die 4 Bytes für den Zeiger node *left und die 4 Bytes für den Zeiger node *right.

Mit dem Aufruf destroy_tree(left) löschen Sie den Teilbaum, auf den left zeigt. Sie können sich vorstellen, dass es die Spitze des Baumes in Brand setzt und es von den Blättern abbrennen sieht. Zuerst der linke Zweig, dann der rechte Zweig.

Answer 7

Lets versuchen, es aus diesem Code zu verstehen:

void delete(struct node* node) 
{ 
if(node==NULL) 
return; 
delete(node->left); 
delete(node->right); 
free(node) 
} 

In diesem Code der Steuerung an das am weitesten links stehenden Blatt geht zuerst und es beginnt von dort zu löschen (wie vor einem Elternteil zu löschen wir löschen müssen werden seine Kinder) lassen einen Baum zum Beispiel nehmen:

 1 
    /\ 
    2 3 
/\ 
4 5 

so erster der Speicher für Knoten 4 wird für den Knoten 5 befreit und dann wird, als freies gelöscht keine Wert (Speicherreferenz zurückkehren wird), so dass die Mutter Knoten zeigt auch auf NULL, s o nach 5 2 werden gelöscht. Ich hoffe, das hilft.