Albero rappresenta i nodi connessi da bordi. Discuteremo albero binario o albero di ricerca binario in particolare.
L’albero binario è una speciale struttura dati utilizzata per scopi di archiviazione dei dati. Un albero binario ha una condizione speciale che ogni nodo può avere un massimo di due figli., Un albero binario ha i vantaggi di un array ordinato e di un elenco collegato in quanto la ricerca è veloce come in un array ordinato e l’operazione di inserimento o eliminazione è veloce come nell’elenco collegato.
Termini importanti
Di seguito sono riportati i termini importanti rispetto all’albero.
-
Path − Percorso si riferisce alla sequenza di nodi lungo i bordi di un albero.
-
Root − Il nodo nella parte superiore dell’albero è chiamato root. C’è solo una radice per albero e un percorso dal nodo radice a qualsiasi nodo.,
-
Parent − Qualsiasi nodo tranne il nodo radice ha un bordo verso l’alto di un nodo chiamato parent.
-
Child − Il nodo sotto un dato nodo collegato dal suo bordo verso il basso è chiamato il suo nodo figlio.
-
Foglia − Il nodo che non ha alcun nodo figlio è chiamato nodo foglia.
-
Subtree − Sottoalbero rappresenta i discendenti di un nodo.
-
Visiting-Visita si riferisce al controllo del valore di un nodo quando il controllo è sul nodo.
-
Traversing − Attraversare significa passare attraverso i nodi in un ordine specifico.,
-
Livelli − Livello di un nodo rappresenta la generazione di un nodo. Se il nodo radice è al livello 0, il suo prossimo nodo figlio è al livello 1, il suo nipote è al livello 2 e così via.
-
keys-Key rappresenta un valore di un nodo in base al quale deve essere eseguita un’operazione di ricerca per un nodo.
Rappresentazione dell’albero di ricerca binario
L’albero di ricerca binario presenta un comportamento speciale. Il figlio sinistro di un nodo deve avere un valore inferiore al valore del genitore e il figlio destro del nodo deve avere un valore maggiore del suo valore padre.,
Implementeremo l’albero usando l’oggetto node e collegandoli tramite riferimenti.
Nodo albero
Il codice per scrivere un nodo albero sarebbe simile a quello indicato di seguito. Ha una parte di dati e riferimenti ai suoi nodi figlio sinistro e destro.
struct node { int data; struct node *leftChild; struct node *rightChild;};
In un albero, tutti i nodi condividono costrutto comune.
BST Operazioni di base
Le operazioni di base che possono essere eseguite su una struttura dati ad albero di ricerca binaria, sono le seguenti −
-
Insert − Inserisce un elemento in un albero/crea un albero.,
-
Search-Cerca un elemento in un albero.
-
Preorder Traversal − Attraversa un albero in modo preordine.
-
Inorder Traversal − Attraversa un albero in modo in ordine.
-
Postorder Traversal − Attraversa un albero in modo post-ordine.
Impareremo a creare (inserire) una struttura ad albero e cercare un elemento di dati in un albero in questo capitolo. Impareremo a conoscere i metodi di attraversamento degli alberi nel prossimo capitolo.
Operazione di inserimento
Il primo inserimento crea l’albero., Successivamente, ogni volta che un elemento deve essere inserito, individuare prima la sua posizione corretta. Inizia la ricerca dal nodo radice, quindi se i dati sono inferiori al valore della chiave, cerca la posizione vuota nella sottostruttura sinistra e inserisci i dati. In caso contrario, cercare la posizione vuota nella sottostruttura destra e inserire i dati.,
Algoritmo
If root is NULL then create root nodereturnIf root exists then compare the data with node.data while until insertion position is located If data is greater than node.data goto right subtree else goto left subtree endwhile insert dataend If
Implementazione
L’implementazione della funzione insert dovrebbe essere simile a questa −
Operazione di ricerca
Ogni volta che un elemento deve essere cercato, inizia la ricerca dal nodo radice, quindi se i dati sono inferiori al valore della chiave, cerca l’elemento nella sottostruttura sinistra. Altrimenti, cerca l’elemento nella sottoalbero destra. Seguire lo stesso algoritmo per ogni nodo.
Algoritmo
If root.data is equal to search.data return rootelse while data not found If data is greater than node.data goto right subtree else goto left subtree If data found return node endwhile return data not found end if
L’implementazione di questo algoritmo dovrebbe essere simile a questa.,
Per conoscere l’implementazione della struttura dati ad albero di ricerca binaria, fare clic qui.