1. Definizione di Albero


Cammino, Altezza e Profondità di un Albero



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

1.1. Cammino, Altezza e Profondità di un Albero


Sia data una sequenza m1, m2, m3, .., mk di nodi dell'albero. Se m1 è il genitore di m2, m2 è il genitore di m3 e così via, allora tale sequenza è detta cammino. La lunghezza del cammino è pari al numero di nodi che lo compongono meno 1, ossia k-1. Un cammino costituito da un solo nodo (k=1) ha dunque lunghezza 0.

Il nodo m1 è detto antenato di mk e mk è detto discendente di m1. Se la lunghezza del cammino è maggiore o uguale a 1, allora m1 è detto antenato proprio di mk e mk è detto discendente proprio di m1.

Dato un albero e un suo nodo n, si definisce altezza del nodo n il più lungo cammino che va dal nodo n ad una foglia. Se il nodo n coincide con la radice allora l'altezza è quella dell'albero.

La profondità o livello di un nodo è la lunghezza del cammino che va dalla radice al nodo n.






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


©astratto.info 2019
invia messaggio

    Pagina principale