1. Definizione di Albero


Definizione di Sottoalbero



Scaricare 142.5 Kb.
Pagina3/11
21.12.2019
Dimensione del file142.5 Kb.
1   2   3   4   5   6   7   8   9   10   11

1.2.Definizione di Sottoalbero


Dato un albero T, un sottoalbero è costituito da un generico nodo n di T e da tutti i suoi discendenti. Il nodo n è la radice del sottoalbero.

1.3.Foglie e Nodi Interni


Dato un albero T, un suo nodo n si definisce foglia se non ha figli. Un nodo n si definisce interno se ha uno o più figli. La radice di un albero è un nodo interno se l'albero presenta altri nodi oltre alla radice. La radice è una foglia nel caso contrario, cioè se l'albero è costituito solo dalla radice.

1.4.Ordinamento dei Figli


Dato un albero T e dato un generico nodo n, è possibile individuare tra i suoi figli un ordinamento in base al quale è possibile distinguere i nodi figli. Nel seguito verranno considerati ordinamenti che permettono di individuare un figlio posto all'estrema sinistra, uno posto all'estrema destra e tutti i figli in posizione intermedia.

1.5.Contenuto di Ciascun Nodo


Gli alberi possono unicamente servire a definire relazioni tra nodi. In tal caso a ciascun nodo viene associata una etichetta in modo da poter essere distinto da qualunque altro nodo. L'etichetta assume valori appartenenti ad un determinato dominio. Ad esempio nelle figure precedenti è stata utilizzata come etichetta la sequenza nx, dove x è un numero naturale.

In altri casi ciascun nodo può contenere delle informazioni di un certo tipo. Ad esempio è possibile organizzare un archivio tramite particolari strutture arboree. In tal caso, ciascun nodo verrà sempre distinto da un altro attraverso una particolare etichetta, ma in più conterrà una o più informazioni, ciascuna appartenente ad un determinato dominio.



Nel seguito la trattazione sugli alberi verrà focalizzata sulle strutture arboree utilizzate per la memorizzazione di informazioni, tipicamente per la realizzazione e la gestione di archivi. In particolare, supporremo che il contenuto informativo di ciascun nodo dell'albero binario di ricerca appartenga al tipo generico denominato tipobaseABR.




Condividi con i tuoi amici:
1   2   3   4   5   6   7   8   9   10   11


©astratto.info 2019
invia messaggio

    Pagina principale