Come eliminare elementi in un albero binario in C?

Question

Sto cercando di capire la cancellazione dei nodi in un albero binario. Questo è lo snippet di codice che ho trovato dal tutorial che spiega lo stesso.

Il nodo si presenta così:

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

Fonte: 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); 
     } 
    } 

Il mio dubbio è per quanto riguarda la parte free(leaf). Voglio dire, l'autore sostiene che questo cancellerà in modo ricorsivo tutti i nodi a partire da quello in basso a sinistra. Ma non è free(leaf) solo liberando la memoria del puntatore foglia? Non tutti i nodi sono ancora connessi? Come si svolge la compensazione?

Answer 1

Sei corretto. Recupera la memoria dalla "Memoria allocata" di C, che è molto probabilmente l'heap. Dato che stai cancellando l'albero INTERO non importa che tu non stia ricostruendo correttamente i nodi mentre ricorre all'albero perché stanno per essere distrutti anch'essi.

Questo codice non sta eliminando o piuttosto "rimuovendo" un elemento dall'albero, sta distruggendo l'intero albero dato un nodo foglia.

Dal sito

Il destroy_tree Di seguito riportiamo che sarà in realtà gratuito tutti i nodi del nell'albero immagazzinato sotto la foglia del nodo: albero.

Answer 2

Nel link che hai postato l'autore ha un albero che assomiglia a questo:

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

La funzione di eliminazione ricorsiva funziona andando fino in fondo il lato sinistro, poi il lato destro quindi eliminando il nodo. Così in quanto sopra si verifica quanto segue (iniziando con il nodo contenente 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) 

Quanto sopra dimostra come la funzione Recurse alla destra dal nodo 10. Poiché i nodi sono free d genitore punterà memoria che è stata rilasciata, ma va bene dato che alla fine scartare il nodo genitore quando la ricorsione si svolge e libera il genitore.

Answer 3

Ma non è libero (foglia) solo restituendo la memoria del puntatore foglia?

Sì. Ma non è tutta la storia. Guarda appena sopra la chiamata a free, cosa vedi essere chiamato?

Non tutti i nodi sono ancora connessi?

Non importa perché ...

Come si fa la radura si svolgono?

le chiamate ricorsive di destroy_tree discendente verso il basso a destra ea sinistra, che a sua volta fare la distruzione ricorsiva, e alla fine si libera, torna al chiamante, che libera e così via. Alla fine l'intero albero è stato liberato.

Answer 4

sto mostrando graficamente come sarebbe il cambiamento albero:

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 

Naturalmente, alla fine, nodi non sono collegati, non esistono più. Ho appena mostrato in figura come cambierebbero durante il corso di questo algoritmo. Se hai ulteriori domande, non esitare a chiedere.

Ti consiglio caldamente, quando non riesci a capire come funziona la ricorsione dell'albero, su un foglio di carta scrivi una foto e poi passa all'algoritmo come ho scritto sopra.

Answer 5

Si sta eliminando la foglia e le sue diramazioni in modo ricorsivo. Disegno un campione per te. I numeri nel cerchio mostrano l'ordine di foglie che vengono liberate. Le linee indicano l'ordine di esecuzione codice

Answer 6

La chiamata free(leaf) libera la memoria che è stata allocata per la variabile che viene puntato dal puntatore leaf. Qui, libera tutti i 12 byte che una variabile di tipo struct node occupa, ovvero i 4 byte per il int value, i 4 byte per il puntatore node *left ei 4 byte per il puntatore node *right.

Chiamando destroy_tree(left), si sta eliminando il sottostruttura puntato da left. Puoi pensare ad esso come dare fuoco alla cima dell'albero e vederlo bruciare dalle foglie, prima il ramo sinistro, poi il ramo destro.

Answer 7

Proviamo a capirlo da questo codice:

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

In questo controllo del codice andrà al più foglia di sinistra prima e inizierà a cancellare da lì (come prima di eliminare un genitore dovremo eliminare i suoi figli) consente di dare un albero, ad esempio:

 1 
    /\ 
    2 3 
/\ 
4 5 

quindi prima la memoria per il nodo 4 verrà liberata e poi per il nodo 5, come libero non restituisce alcun valore di riferimento (la memoria viene eliminato) in modo che il genitore il nodo punta anche a NULL, s o dopo il 5 2 verrà cancellato. Spero che questo aiuti.