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).
|
