Un'altra struttura di dati non lineare comune � l'albero.
In questo schema qui sopra, possiamo vedere che il punto di partenza, o il nodo della radice, � circondato nel colore blu. Un nodo � una struttura semplice che tiene i dati ed i collegamenti ad altri nodi. In questo caso, il nostro nodo della radice contiene la stringa �John� di dati e tre collegamenti agli altri nodi. Notare che il gruppo dei nodi circondati nel colore rosso non ha alcuni collegamenti (childs). Questi nodi sono all'estremit� dei rami e sono denominati giustamente come i fogli o nodi del foglio. Nel nostro schema, i nodi sono collegati con le strisce nere continue denominate archi o bordi. Questi bordi mostrano i rapporti fra i nodi nell'albero.
Un rapporto importante nell'albero binario � il rapporto del genitore-bambino. I nodi del genitore hanno almeno un bordo al nodo si abbassano nell'albero. Questo nodo pi� basso � denominato il nodo del bambino. I nodi possono avere pi� di un bambino, ma i bambini possono soltanto avere un singolo genitore. Notare che il nodo della radice non ha genitore ed i nodi del foglio non ha bambini. La caratteristica finale alla nota nel nostro schema � il sotto-albero. Ad ogni livello dell'albero, possiamo vedere che la struttura arborescente � ripetuta. Per esempio, i due nodi che rappresentano �Charles� e �Rick� compongono un albero molto semplice con �Charles� come il nodo della radice ed e �Rick� come singolo nodo del foglio.
Gli Trees sono effettuati nella memoria del calcolatore. Cominceremo introducendo la struttura arborescente semplice denominata l'albero binario. Gli Trees binari hanno la limitazione che i nodi non possono avere pi� di due bambini. Con questa limitazione, possiamo determinare facilmente come rappresentare un singolo nodo binario nella memoria. Il nostro nodo dovr� riservare la memoria ai dati ed a due indicatori (per indicare due childs di quel nodo).
|
