Come implementare l'albero binario in c?

Un albero è un formato di dati comune per la memorizzazione di informazioni contenute gerarchicamente. Un albero è costituito da nodi collegati dai bordi, con ciascun nodo che ha il suo nodo genitore e uno o più nodi figlio. Questo articolo studia e analisi alberi binari e vede l'implementazione di alberi binari Nella programmazione C.

Albero binario in c

In c, a albero binario è un'istanza di una struttura dei dati ad albero con un nodo genitore che può possedere un numero massimo di due nodi figlio; 0, 1 o 2 nodi di prole. Ogni singolo nodo in a albero binario ha un valore proprio e due puntatori per i suoi figli, un puntatore per il bambino sinistro e l'altro per il bambino destro.

Dichiarazione dell'albero binario

UN albero binario può essere dichiarato in c usando un oggetto chiamato strumento che raffigura uno dei nodi nell'albero.

nodo struct
DataType var_name;
nodo struct* a sinistra;
nodo struct* a destra;
;

Sopra è una dichiarazione di uno albero binario Nome nodo come nodo. Contiene tre valori; Uno è la variabile di archiviazione dati e gli altri due sono i puntatori del bambino. (figlio sinistro e destro del nodo genitore).

Fatti di albero binario

Anche per grandi serie di dati, utilizzando un albero binario Rende la ricerca più semplice e veloce. Il numero di rami ad albero non è limitato. Contrariamente a un array, gli alberi di qualsiasi tipo possono essere fatti e aumentati in base a ciò che è richiesto da un individuo.

Implementazione binaria dell'albero in c

Quella che segue è una guida passo-passo per l'implementazione di Albero binario in c.

Passaggio 1: dichiarare un albero di ricerca binaria

Crea un nodo struct che abbia tre tipi di dati, come dati, *Left_Child e *Right_Child, dove i dati possono essere di tipo intero, ed entrambi i nodi *Left_Child e *destro_Child possono essere dichiarati null o no.

nodo struct

Int Data;
nodo struct *destro_child;
nodo struct *left_child;
;

Passaggio 2: creare nuovi nodi nell'albero di ricerca binaria

Crea un nuovo nodo creando una funzione che accetta un numero intero come argomento e fornisce il puntatore al nuovo nodo creato con quel valore. Utilizzare la funzione Malloc () in C per l'allocazione di memoria dinamica per il nodo creato. Inizializza il bambino sinistro e destro su NULL e restituisce il NODENAME.

Struct Node* create (dati del tipo di dati)

nodo struct* noDename = malloc (sizeof (nodo struct));
nodename-> data = value;
nodename-> left_child = nodename-> destro_child = null;
restituire NODENAME;

Passaggio 3: inserire i bambini a destra e sinistra nell'albero binario

Crea funzioni insert_left e insert_right che accettano due input, che sono il valore da inserire e il puntatore al nodo a cui entrambi i bambini saranno collegati. Chiama la funzione Crea per creare un nuovo nodo e assegnare il puntatore restituito al puntatore sinistro del figlio sinistro o il puntatore destro del figlio destro del genitore radice.

Struct Node* Insert_left (root struct* root, dati dati)
root-> left = create (dati);
restituire root-> sinistra;

Struct Node* insert_right (struct nodo* root, dati dati)
root-> diritto = create (dati);
restituire root-> giusto;

Passaggio 4: visualizzare i nodi di albero binario usando i metodi di attraversamento

Possiamo visualizzare alberi usando tre metodi di attraversamento in C. Questi metodi di attraversamento sono:

1: attraversamento del pre-ordine

In questo metodo di attraversamento, passeremo attraverso i nodi in una direzione da parent_node-> left_child-> destro_child.

void pre_order (nodo * root)
if (root)
printf ("%d \ n", root-> dati);
display_pre_order (root-> sinistra);
display_pre_order (root-> a destra);

2: attraversamento post-ordine

In questo metodo di attraversamento, attraverseremo i nodi in una direzione dal Left_Child-> Right_Child-> Parent_node->.

void display_post_order (nodo * root)
if (binary_tree)
display_post_order (root-> sinistra);
display_post_order (root-> a destra);
printf ("%d \ n", root-> dati);

3: attraversamento in ordine

In questo metodo di attraversamento, passeremo attraverso i nodi in una direzione da left_node-> root_child-> destro_child.

void display_in_order (nodo * root)
if (binary_tree)
display_in_order (root-> sinistra);
printf ("%d \ n", root-> dati);
display_in_order (root-> a destra);

Passaggio 5: eseguire la cancellazione nell'albero binario

Possiamo eliminare il creato Albero binario Eliminando entrambi i bambini con la funzione del nodo genitore in C come segue.

void delete_t (nodo * root)
if (root)
delete_t (root-> a sinistra);
delete_t (root-> a destra);
libero (radice);

Programma C di albero di ricerca binaria

Di seguito è la completa implementazione dell'albero di ricerca binaria nella programmazione C:

#includere
#includere
nodo struct
valore int;
nodo struct * a sinistra, * a destra;
;
Struct Node * node1 (int data)
nodo struct * tmp = (nodo struct *) malloc (sizeof (nodo struct));
tmp -> value = data;
tmp -> left = tmp -> destro = null;
restituire tmp;

void print (nodo struct * root_node) // Visualizzazione dei nodi!

if (root_node != Null)
print (root_node -> a sinistra);
printf ("%d \ n", root_node -> valore);
print (root_node -> a destra);


nodo struct * insert_node (nodo struct *, dati int) // inserzione di nodi!

if (node ​​== null) return node1 (dati);
if (dati < node -> valore)
nodo -> left = insert_node (nodo -> a sinistra, dati);
else if (data> nodo -> valore)
nodo -> diritto = insert_node (nodo -> giusto, dati);

nodo di ritorno;

int main ()
Printf ("C Implementazione dell'albero di ricerca binaria!\ n \ n ");
nodo struct * genitore = null;
genitore = insert_node (genitore, 10);
insert_node (genitore, 4);
insert_node (genitore, 66);
insert_node (genitore, 45);
insert_node (genitore, 9);
insert_node (genitore, 7);
stampa (genitore);
restituzione 0;

Nel codice sopra, dichiariamo prima a nodo usando strumento. Quindi inizializziamo un nuovo nodo come "nodo1"E allocare la memoria in modo dinamico usando Malloc () In C con dati e due puntatori digitano i bambini usando il nodo dichiarato. Dopo questo, visualizziamo il nodo di printf () funzione e chiamalo in principale() funzione. Poi il insertion_node () viene creata la funzione, dove se i dati del nodo sono nulli nodo1 è in pensione, altrimenti i dati sono inseriti in nodo(genitore) del bambino sinistro e destro. Il programma inizia l'esecuzione da principale() funzione, che genera un nodo utilizzando alcuni nodi campione come bambini e quindi utilizza metodi di attraversamento in ordine per stampare il contenuto del nodo.

Produzione

Conclusione

Gli alberi sono spesso impiegati per mantenere i dati in una forma non lineare. Alberi binari sono tipi di alberi in cui ciascun nodo (genitore) ha due progressi del bambino sinistro e il figlio destro. UN albero binario è un metodo versatile per trasferire e archiviare i dati. È più efficiente rispetto alla lista collegata in c. Nell'articolo di cui sopra, abbiamo visto il concetto di a Albero binario con l'implementazione passo-passo di a Albero di ricerca binaria in c.