Albero binario in C
In C, a albero binario è un'istanza di una struttura dati ad albero con un nodo genitore che può possedere un numero massimo di due nodi figli; 0, 1 o 2 nodi discendenti. Ogni singolo nodo in a albero binario ha un proprio valore e due puntatori ai suoi figli, un puntatore per il figlio sinistro e l'altro per il figlio destro.
Dichiarazione di albero binario
UN albero binario può essere dichiarato in C usando un oggetto chiamato struct che raffigura uno dei nodi dell'albero.
struct nodo {
tipo di dati nome_var ;
struct nodo * Sinistra ;
struct nodo * Giusto ;
} ;
Sopra è una dichiarazione di uno albero binario nome del nodo come nodo. Contiene tre valori; uno è la variabile di memorizzazione dei dati e gli altri due sono i puntatori al figlio. (figlio sinistro e destro del nodo padre).
Fatti dell'albero binario
Anche per grandi insiemi di dati, utilizzando a albero binario rende la ricerca più facile e veloce. Il numero di rami degli alberi non è limitato. A differenza di un array, è possibile creare e aumentare alberi di qualsiasi tipo in base a ciò che è richiesto a un individuo.
Implementazione dell'albero binario in C
Quella che segue è una guida passo-passo all'implementazione di a Albero binario in c.
Passaggio 1: dichiarare un albero di ricerca binario
Creare un nodo struct con tre tipi di dati, ad esempio data, *left_child e *right_child, dove i dati possono essere di tipo intero e entrambi i nodi *left_child e *right_child possono essere dichiarati come NULL o meno.
struct nodo{
int dati ;
struct nodo * figlio_destro ;
struct nodo * figlio_sinistro ;
} ;
Passaggio 2: creare nuovi nodi nell'albero di ricerca binario
Crea un nuovo nodo creando una funzione che accetti un numero intero come argomento e fornisca il puntatore al nuovo nodo creato con quel valore. Utilizzare la funzione malloc() in C per l'allocazione dinamica della memoria per il nodo creato. Inizializza il figlio sinistro e destro su NULL e restituisci il nome del nodo.
struct nodo * creare ( dati del tipo di dati )
{
struct nodo * nomeNodo = malloc ( taglia di ( struct nodo ) ) ;
nomeNodo -> dati = valore ;
nomeNodo -> figlio_sinistro = nomeNodo -> figlio_destro = NULLO ;
ritorno nomeNodo ;
}
Passaggio 3: inserire i figli destro e sinistro nell'albero binario
Crea le funzioni insert_left e insert_right che accetteranno due input, che sono il valore da inserire e il puntatore al nodo a cui saranno collegati entrambi i figli. Chiama la funzione create per creare un nuovo nodo e assegna il puntatore restituito al puntatore sinistro del figlio sinistro o al puntatore destro del figlio destro del genitore radice.
struct nodo * insert_left ( struct nodo * radice , dati del tipo di dati ) {radice -> Sinistra = creare ( dati ) ;
ritorno radice -> Sinistra ;
}
struct nodo * insert_right ( struct nodo * radice , dati del tipo di dati ) {
radice -> Giusto = creare ( dati ) ;
ritorno radice -> Giusto ;
}
Passaggio 4: visualizzare i nodi dell'albero binario utilizzando i metodi di attraversamento
Possiamo visualizzare alberi utilizzando tre metodi di attraversamento in C. Questi metodi di attraversamento sono:
1: Pre-ordine attraversamento
In questo metodo di attraversamento, attraverseremo i nodi in una direzione da parent_node->left_child->right_child .
vuoto ordine prestabilito ( nodo * radice ) {Se ( radice ) {
printf ( '%D \N ' , radice -> dati ) ;
display_pre_ordine ( radice -> Sinistra ) ;
display_pre_ordine ( radice -> Giusto ) ;
}
}
2: Attraversamento post-ordine
In questo metodo di attraversamento, attraverseremo i nodi in una direzione da left_child->right_child->parent_node-> .
vuoto display_post_order ( nodo * radice ) {Se ( albero_binario ) {
display_post_order ( radice -> Sinistra ) ;
display_post_order ( radice -> Giusto ) ;
printf ( '%D \N ' , radice -> dati ) ;
}
}
3: Attraversamento in ordine
In questo metodo di attraversamento, attraverseremo i nodi in una direzione da left_node->root_child->right_child .
vuoto display_in_order ( nodo * radice ) {Se ( albero_binario ) {
display_in_order ( radice -> Sinistra ) ;
printf ( '%D \N ' , radice -> dati ) ;
display_in_order ( radice -> Giusto ) ;
}
}
Passaggio 5: eseguire l'eliminazione nell'albero binario
Possiamo eliminare il creato Albero binario eliminando entrambi i figli con la funzione del nodo genitore in C come segue.
vuoto cancella_t ( nodo * radice ) {Se ( radice ) {
cancella_t ( radice -> Sinistra ) ;
cancella_t ( radice -> Giusto ) ;
gratuito ( radice ) ;
}
}
C Programma dell'albero di ricerca binario
Quanto segue è l'implementazione completa dell'albero di ricerca binario nella programmazione C:
#include#include
struct nodo {
int valore ;
struct nodo * Sinistra , * Giusto ;
} ;
struct nodo * nodo1 ( int dati ) {
struct nodo * tmp = ( struct nodo * ) malloc ( taglia di ( struct nodo ) ) ;
tmp -> valore = dati ;
tmp -> Sinistra = tmp -> Giusto = NULLO ;
ritorno tmp ;
}
vuoto stampa ( struct nodo * root_node ) // visualizzando i nodi!
{
Se ( root_node != NULLO ) {
stampa ( root_node -> Sinistra ) ;
printf ( '%D \N ' , root_node -> valore ) ;
stampa ( root_node -> Giusto ) ;
}
}
struct nodo * insert_node ( struct nodo * nodo , int dati ) // inserimento nodi!
{
Se ( nodo == NULLO ) ritorno nodo1 ( dati ) ;
Se ( dati < nodo -> valore ) {
nodo -> Sinistra = insert_node ( nodo -> Sinistra , dati ) ;
} altro Se ( dati > nodo -> valore ) {
nodo -> Giusto = insert_node ( nodo -> Giusto , dati ) ;
}
ritorno nodo ;
}
int principale ( ) {
printf ( 'Implementazione C dell'albero di ricerca binario! \N \N ' ) ;
struct nodo * genitore = NULLO ;
genitore = insert_node ( genitore , 10 ) ;
insert_node ( genitore , 4 ) ;
insert_node ( genitore , 66 ) ;
insert_node ( genitore , Quattro cinque ) ;
insert_node ( genitore , 9 ) ;
insert_node ( genitore , 7 ) ;
stampa ( genitore ) ;
ritorno 0 ;
}
Nel codice sopra, dichiariamo prima a nodo utilizzando struct . Quindi inizializziamo un nuovo nodo come ' nodo1 ” e allocare la memoria in modo dinamico utilizzando malloc() in C con dati e due puntatori digita children usando il nodo dichiarato. Successivamente, visualizziamo il nodo by stampaf() funzione e chiamarla nel file principale() funzione. Poi il nodo_inserimento() viene creata la funzione, dove se i dati del nodo sono NULL allora nodo1 viene ritirato, altrimenti i dati vengono inseriti nel file nodo (genitore) del figlio sinistro e destro. Il programma inizia l'esecuzione dal file principale() funzione, che genera un nodo utilizzando alcuni nodi di esempio come figli e quindi utilizza metodi di attraversamento in ordine per stampare il contenuto del nodo.
Produzione
Conclusione
Gli alberi sono spesso utilizzati per mantenere i dati in una forma non lineare. Alberi binari sono tipi di alberi in cui ogni nodo (genitore) ha due figli il figlio sinistro e il figlio destro. UN albero binario è un metodo versatile di trasferimento e memorizzazione dei dati. È più efficiente rispetto a Linked-List in C. Nell'articolo precedente, abbiamo visto il concetto di a Albero binario con l'implementazione passo-passo di a Albero di ricerca binario in c.