Albero di ricerca binario C ++

BST è una struttura di dati che mantiene i dati in un elenco ordinato. È noto come un albero di ricerca binaria perché, nell'albero, ogni nodo ha un massimo di due bambini che non può essere aumentato ulteriormente. Questo è noto come un albero di ricerca perché viene utilizzato per cercare o trovare qualsiasi articolo presente. Implementeremo questo fenomeno nel linguaggio C ++.

Implementazione

In un'implementazione, il primo passo è utilizzare una struttura per inizializzare il tasto tipo intero e i nodi del lato sinistro e destro. Questi nodi sono definiti utilizzando un puntatore variabile, poiché entrambi salvano gli indirizzi dei nodi alternativi. Successivamente, chiudiamo la struttura.

Creeremo di nuovo un nuovo nodo attraverso una struttura. Il parametro della funzione conterrà i dati che vogliamo inserire nel nodo.

Struct Node *newnode (It elemento)

Creerà una nuova temperatura nodo che memorizzerà i dati al suo interno e le dimensioni della memoria verranno allocate tramite Malloc (). Aggiungeremo il valore dell'elemento nella parte chiave del nodo. Mentre le parti sinistro e destro, che sono dichiarate precedentemente nella struttura, sono dichiarate nulle ora perché è il primo nodo. La temperatura verrà restituita.

Viene creata una funzione con il nome "InOrder" e accetterà il nodo radice nel parametro. Come sappiamo, l'albero contiene tre parti principali: i lati nodo, sinistra e destra dell'albero. Useremo una sezione if per verificare se la radice non è nulla. Quindi, chiama la funzione e invia la parte sinistra della radice. Questo mostrerà la radice stessa con una freccia che indicherà la direzione del percorso nell'albero. Successivamente, per attraversare il diritto, chiama la funzione InOrder con la destra della radice come parametro.

In ordine (root -> sinistra)

Ecco come viene fatto la attraversamento in ordine. Per inserire un nuovo nodo nell'albero, useremo una funzione che prenderà un nodo e la chiave come valori dei parametri. Se l'albero è già vuoto, il nuovo nodo verrà restituito. Nel secondo caso, se l'albero non è vuoto, quindi vai sul lato destro e inserisci un nuovo nodo qui. Per l'inserimento, useremo un'istruzione If-Else per verificare l'ordine per la chiave. La nuova chiave andrà sul lato sinistro per l'ordine ascendente. Se la parte che controllerà la nuova chiave è già inferiore al valore presente nel nodo, immettere la chiave sulla parte sinistra del nodo.

Nodo -> Left = Insert (nodo -> Left, Key)

Mentre se la chiave è maggiore, andrà nella parte giusta.

Dopo l'inserimento del nodo, controlleremo il nodo successivo o il nodo che è il successore. Viene creata una funzione del valore min che creerà un nuovo nodo con un nome *corrente. Questo nodo sarà assegnato da un valore passato come argomento alla funzione. Troverà prima il nodo angolare o la foglia di modalità sinistra sul lato sinistro dell'albero. Usiamo un ciclo while che iterate fino a quando il traversa del nodo è finito. In altre parole, la parte sinistra del nodo corrente non è nulla.

Corrente = corrente -> lasciato

Continua ad assegnare il nodo corrente il valore della corrente successiva all'interno del ciclo a sinistra.

Il nostro albero è attraversato e organizzato aggiungendo foglie su entrambi i lati. Ogni valore verrà inserito tramite la chiamata di funzione effettuata dal programma principale. Ora, dobbiamo cercare qualsiasi elemento e lo elimineremo una volta trovato.

L'albero in C ++ funziona sullo stesso fenomeno dell'elenco collegato. Applicheremo la ricerca binaria sull'albero ed eseguiremo un'operazione di eliminazione per eliminare un nodo o una foglia dall'albero. Viene creata una funzione del nodo Elimina; Conterrà l'albero e il valore come parametri. Verificheremo prima che gli alberi debbano avere valori al loro interno. Quindi, verrà utilizzato la dichiarazione if e se la radice è nulla, significa restituire solo la radice.

If (chiave chiave)

La chiave che si desidera eliminare è più piccola del nodo radice. Quindi spostati sul lato sinistro e chiama la funzione Elimina con la parte sinistra dell'albero e la chiave da eliminare.

Root -> left = deleteNode (root -> a sinistra, chiave);

E lo stesso vale per l'altro, se la parte. Se la chiave è maggiore della chiave del nodo, vai sulla strada giusta, chiama la funzione Elimina. Passa la parte giusta dell'albero e la chiave in modo che diventi facile trovare il nodo che si desidera eliminare.

Ora, arrivando verso la parte altro, ciò è applicabile se il nodo è solo, non ha ulteriori foglie o ha un solo figlio davanti. Di nuovo all'interno della parte altro, se verrà utilizzata un'istruzione che verificherà se non esiste un nodo sul lato destro, aggiungi il valore sul lato destro del nodo al nodo Nuovo Temp, in modo simile per il lato sinistro.

Nodo struct * temp = root -> sinistra;

In quella condizione, libera la radice. Questo rimuoverà il valore dalla radice.

Libero (radice);

Se un nodo contiene due foglie con esso, quindi per cercare il valore, useremo la funzione del valore min e la parte giusta verrà inviata alla funzione.

MinvalueNode (root -> a destra);

Quando viene rilevato il valore da eliminare, lo dichiareremo l'ultima parte dell'albero in modo che possa essere eliminato facilmente.

Root -> key = temp -> chiave;

Dopo averlo fatto, elimina il nodo,

Root -> destro = elimina nodo (nodo -> destro, temp -> chiave);

Dopo aver chiuso la funzione, dichiareremo il programma principale qui. Il nodo radice verrà impostato inizialmente come null. Utilizzando la chiamata di funzione insert (), utilizzeremo i dati root e numerici sul nodo.

Inserire (root, 5);

La funzione InOrder è chiamata per l'attraversamento dell'albero.

In ordine (radice);

Quindi, per eliminare il nodo, chiameremo la funzione Elimina.

Root = deleteNode (root, 10);

Dopo la cancellazione, i valori vengono nuovamente visualizzati.

Dopo aver scritto il codice, lo eseguiremo nel terminale di Ubuntu tramite il compilatore.

file file file $ g ++ -o.C
$ ./file

Come puoi vedere, i sette elementi vengono inseriti nel nodo. Uno viene eliminato e il resto verrà visualizzato nello stesso ordine di prima.

Conclusione

Un albero di ricerca binario viene utilizzato per archiviare i valori nella forma ordinata. Per cercare qualsiasi numero, tutti i numeri devono essere ordinati per primi in ordine. Successivamente, il numero specificato viene cercato dividendo l'albero in due parti, creando i sottotei. L'implementazione BST viene eseguita nel sistema Ubuntu spiegando un esempio in modo elaborato. Speriamo che tu abbia trovato questo articolo utile. Controlla gli altri articoli di suggerimento Linux per ulteriori suggerimenti e tutorial.