Struttura dei dati e algoritmi - Albero
L'albero rappresenta i nodi collegati dai bordi. Discuteremo specificamente l'albero binario o l'albero di ricerca binario.
L'albero binario è una struttura dati speciale 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 sia di un array ordinato che di un elenco collegato poiché la ricerca è veloce come in un array ordinato e le operazioni di inserimento o eliminazione sono veloci come in un elenco collegato.
Termini importanti
Di seguito sono riportati i termini importanti rispetto all'albero.
Path - Il 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 a un nodo chiamato genitore.
Child - Il nodo sotto un dato nodo connesso dal suo bordo verso il basso è chiamato il suo nodo figlio.
Leaf - Il nodo che non ha alcun nodo figlio è chiamato nodo foglia.
Subtree - Il sottoalbero rappresenta i discendenti di un nodo.
Visiting - La 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.
Levels- Il livello di un nodo rappresenta la generazione di un nodo. Se il nodo radice è al livello 0, il suo successivo nodo figlio è al livello 1, il suo nipote è al livello 2 e così via.
keys - La chiave 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 binaria
L'albero di ricerca binario mostra un comportamento speciale. Il figlio sinistro di un nodo deve avere un valore inferiore al valore del suo genitore e il figlio destro del nodo deve avere un valore maggiore del suo valore genitore.
Implementeremo l'albero utilizzando l'oggetto nodo e collegandoli tramite riferimenti.
Nodo dell'albero
Il codice per scrivere un nodo della struttura ad albero sarebbe simile a quanto riportato di seguito. Ha una parte 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 un costrutto comune.
BST Operazioni di base
Le operazioni di base che possono essere eseguite su una struttura dati ad albero di ricerca binario, 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 modalità pre-ordine.
Inorder Traversal - Attraversa un albero in modo ordinato.
Postorder Traversal - Attraversa un albero in modo post-ordine.
In questo capitolo impareremo a creare (inserire in) una struttura ad albero e cercare un elemento di dati in un albero. Impareremo i metodi di attraversamento degli alberi nel prossimo capitolo.
Inserisci operazione
Il primo vero inserimento crea l'albero. Successivamente, ogni volta che deve essere inserito un elemento, 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. Altrimenti, cerca la posizione vuota nella sottostruttura destra e inserisci i dati.
Algoritmo
If root is NULL
then create root node
return
If 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 data
end If
Implementazione
L'implementazione della funzione di inserimento dovrebbe essere simile a questa:
void insert(int data) {
struct node *tempNode = (struct node*) malloc(sizeof(struct node));
struct node *current;
struct node *parent;
tempNode->data = data;
tempNode->leftChild = NULL;
tempNode->rightChild = NULL;
//if tree is empty, create root node
if(root == NULL) {
root = tempNode;
} else {
current = root;
parent = NULL;
while(1) {
parent = current;
//go to left of the tree
if(data < parent->data) {
current = current->leftChild;
//insert to the left
if(current == NULL) {
parent->leftChild = tempNode;
return;
}
}
//go to right of the tree
else {
current = current->rightChild;
//insert to the right
if(current == NULL) {
parent->rightChild = tempNode;
return;
}
}
}
}
}
Operazione di ricerca
Ogni volta che si deve cercare un elemento, avviare la ricerca dal nodo radice, quindi se i dati sono inferiori al valore della chiave, cercare l'elemento nella sottostruttura sinistra. Altrimenti, cerca l'elemento nella sottostruttura a destra. Segui lo stesso algoritmo per ogni nodo.
Algoritmo
If root.data is equal to search.data
return root
else
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.
struct node* search(int data) {
struct node *current = root;
printf("Visiting elements: ");
while(current->data != data) {
if(current != NULL)
printf("%d ",current->data);
//go to left tree
if(current->data > data) {
current = current->leftChild;
}
//else go to right tree
else {
current = current->rightChild;
}
//not found
if(current == NULL) {
return NULL;
}
return current;
}
}
Per conoscere l'implementazione della struttura dei dati dell'albero di ricerca binario, fare clic qui .