Alberi binari
Definizione
Sottoalberi
Padre, figli
Foglie, nodi interni e percorsi
Profondità e altezza
Albero binario pieno e completo
Albero binario
• Un albero binario è un albero dove ogni nodo ha al massimo due figli.
• Tutti i nodi tranne la radice ha un nodo padre.
• Le foglie dell’albero non hanno figli.
Sottoalberi
radice
Sottoalbero sinistro Sottoalbero destro
Sottoalberi
radice
Sottoalbero sinistro
Sottoalbero destro
Sottoalbero sinistro
Sottoalbero destro Radice del
sottoalbero sinistro
Radice del sottoalbero
destro
Padre e figli
radice
i
k j
Arco tra i e j
• i è padre di k e j
• j e k sono i due figli di i
• (i,j) è l’arco che unisce i e j
Figli di i
Foglie, nodi interni e percorsi
• In nodo di un albero binario si dice nodo foglia (o solo foglia) se non ha figli (cioè se entrambi i
sottoalberi di cui è radice sono vuoti).
• Un nodo si dice nodo interno se ha almeno un figlio.
• Un percorso dal nodo i al nodo j è la sequenza di archi che devono essere attraversati per
raggiungere il nodo j dal nodo i.
Foglie, nodi interni e percorsi
radice
i
j Percorso tra i e j
Nodi interni
Foglie
Profondità e altezza
• In un albero binario la profondità di un nodo è la lunghezza del percorso dalla radice al nodo (cioè il numero di archi tra la radice e il nodo).
• L’altezza dell’albero è la profondità massima che può avere un nodo
dell’albero.
Profondità e altezza
radice
profondità 1
profondità 0
profondità 2
profondità 3
altezza 3
Albero binaro pieno
• Un albero binario si dice pieno se:
1. tutte le foglie hanno la stessa profondità h 2. tutti i nodi interni hanno grado 2
• Un albero pieno di n nodi ha altezza esattamente .
• Un albero pieno di altezza h ha esattamente 2
h+1-1 nodi (2
h-1 nodi interni + 2
hfoglie).
log2n
1 1 2
2 2 1
1
h i h hn
Albero binaro pieno
radice
2
4 5
• Nodi totali n = 2h+1-1
=
24-1 = 15• Nodi interni 2h-1 = 7
• Foglie 2h = 8
altezza h=3 3
6 7
1
8 9 10 11 12 13 14 15
log n
Albero binaro completo
• Un albero binario si dice completo se
1. tutte le foglie hanno profondità h o h-1, dove h è l’altezza dell’albero
2. tutti i nodi interni hanno 2 figli, eccetto al più
uno.
Albero binaro completo
radice
2
4 5
altezza h=3 3
6 7
1
8 9 10 11 12
Unico nodo interno con profondità h
profondità h-1