Alberi binari
Corso di Informatica 2
a.a. 2003/04
Lezione 6
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Cosa sono gli alberi?
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Strutture gerarchiche di ogni tipo
Generale
Colonnello1
Maggiore1,1
Maggiore1,m
Colonnellok
Maggiorek,1
Maggiorek,n
Capitano
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Strutture gerarchiche di ogni tipo
Strutture dati
1. Tipi di dato e strutture dati
1.
2.
Specifica e realizzazione
Rappresentazione in memoria
2. Liste
1.
2.
3.
L’ADT delle liste
Realizzazione con vettori
Realizzazione con puntatori
3. Pile e code
1.
L’ADT delle pile …
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Definizioni
Un albero èun grafo connesso aciclico; nel caso finito può
essere definito induttivamente come un insieme tale che:
•  è un albero;
• se k  0, T1, …, Tk sono alberi, v un vertice, allora
{v, T1, …, Tk } è un albero
Un insieme di alberi è una foresta.
albero
foresta
grafo ciclico
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Struttura induttiva degli alberi
nodo
albero
albero
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi con radice e foglie
•
•
•
•
La radice è un nodo privilegiato di un albero;
se l’albero è un grafo non orientato qualunque
nodo può considerarsi radice;
se l’albero è orientato allora due casi:
1. la radice ha solo archi in uscita (albero
sorgente)
2. la radice ha solo archi in entrata (albero
pozzo)
Una foglia è un nodo da cui non esce alcun arco
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi sorgente, alberi pozzo
sorgente
pozzo
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Parentele
a è padre
di b e c
a
b è figlio di
a
c
b
d
e
f
f è un discendente
di a; a è un avo di
f
d è fratello
di e
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Cammini
Cammino: sequenza di archi ciascuno
incidente sul vertice di quello successivo
Un cammino
dalla radice ad
una foglia si dice
ramo
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Livelli
Livello: insieme di vertici equidistanti
dalla radice
L’altezza è la
massima
distanza dalla
radice di un
livello non
vuoto
Livello 0
Livello 1
Livello 2
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi ordinati
Un albero è ordinato quando lo sono
(linearmente) i suoi livelli

a
b
a
c
c
d
Come
alberi
ordinati
siamo
diversi
b
d
=
Conta solo l’ordine, non sinistra e destra
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi k-ari
Arietà = massimo num. dei figli di
qualche nodo
Io sono un
albero
ternario
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi posizionali
Un albero ordinato è posizionale quando nell’ordine dei
livelli si tiene conto di  (si deve quindi fissare l’arietà)

a
b
c
d
a
b
c
d
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Una specifica
Sintassi
• Tipi: Tree, Node
• Operatori:
NewTree: void  Tree
IsEmptyTree: Tree  boolean
InsAsRoot: Node, Tree  Tree
Root: Tree  Node
Parent: Node, Tree  Node
Leaf: Node, Tree  boolean …
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Una specifica
Sintassi
• Tipi: Tree, Node
• Operatori:
…
Child: Node, Tree  Node
HasSibling: Node, Tree  Boolean
Sibling: Node, Tree  Node
InsTree: Node, Node, Tree, Tree  Tree
DelTree: Node, Tree  Tree
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Semantica degli operatori
Con qualcosa
si deve pur
cominciare
r
InsAsRoot(r,  )
A cosa servono
queste
banalità?
InsAsRoot(n, T ) = T
Pre: T = 
Post: T è l’albero il cui unico nodo è n
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Semantica degli operatori
r
r
a
c
b
b
d
T
DelTree(a, T )
DelTree(n, T ) = T
Pre: n è un nodo di T
Post: T risulta da T eliminando il sottoalbero con radice in n
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Semantica degli operatori
r
a
c
b
d
r
z
T
x
a
v
c
U
d
z
x
InsTree(n, m, T, U ) = T
b
v
InsTree(c, a, T, U )
Pre: m, n sono nodi di T, U  
Post: T risulta da T inserendo U come figlio di m e
1. fratello successivo di n se n  m
2. primo figlio di m se n = m
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Semantica degli operatori
r
a
c
b
d
r
z
x
a
v
z
T
U
x
c
b
d
v
InsTree(a, a, T, U )
InsTree(n, m, T, U ) = T
Pre: m, n sono nodi di T, U  
Post: T risulta da T inserendo U come figlio di m e
1. fratello successivo di n se n  m
2. primo figlio di m se n = m
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Semantica degli operatori
Semantica
NewTree () =  (albero vuoto)
Root(T) = la radice di T
Parent (n, T) = m Pre: n  T Post: m padre di n
Child (n, T) = m Pre: n  T, Leaf(n, T) = false
Post: m è il primo figlio di n
Sibling (n, T) = m Pre: n  T , HasSibling (n, T) = true
Post: m è il fratello successivo di n
IsEmptyTree(T) = true se T =  , false altr.
Leaf(n, T) = b
Pre: n  T , b = true sse n è una foglia
HasSibling(n, T) = b Pre: n  T
Post: b = true sse n ha un fratello
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Realizzazioni: vettore dei padri
a
c
b
d
etichetta del
nodo
f
e
a b
c
d
e
f
0
1
1
2
2
3
1
2
3
4
5
6
Efficiente per
rappresentare alberi
pozzo di cardinalità
(numero dei nodi)
fissata
indice del
padre
indice del nodo
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi binari: definizione induttiva
L’insieme degli alberi binari etichettati in A,
BT(A), è definito induttivamente:
a)
b)
  BT(A) (albero vuoto)
a  A, l  BT(A), r  BT(A) 
ConsTree(a, l, r)  BT(A)
Si introduce la
nozione di
sottoalbero
sinistro e destro
a
l
r
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Alberi binari realizzati con puntatori
T
info
left
right
r
r
a
c
a
b
b
d
c
T
d
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Codifica binaria di alberi k-ari
a
a
b
e
c
f
b
d
g
c
e
d
f
g
Nel caso di alberi non ordinati
la codifica non è univoca!
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Realizzazioni: con puntatori
parent
a
info
child sibling
b
c
d
e
f
g
a
b
e
c
f
d
g
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
La cardinalità di un albero binario
B
a
Right(B) = r
Left(B) = l
l
r
Cardinalità (B)
if B =  then return 0
else return 1 + Cardinalità (Left(B)) +
Cardinalità (Right(B))
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
L’altezza di un albero binario
Altezza (B)
// Pre: B  
// Post: ritorna l’altezza di B
return Altezza_aux (B)
Si usa una funzione
ausiliaria perché il
caso di base B = 
è essenziale alla
ricorsione
Altezza_aux (B)
// Post: ritorna l’altezza di B, 0 se B = 
if B =  then return 0
else return max{Altezza_aux(Left(B), Altezza_aux(Right(B)) + 1
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
La ricorsione sugli alberi
ContaFoglie (T)
// Post: ritorna il numero delle foglie di T
if T =  then return 0
due casi di base
else if T ha un solo nodo then return 1
else siano T1, …, Tk i sottoalberi con radici nei
nodi figli di della radice di T
return

k
i 1
ContaFogli e(Ti )
Questo pseudocodice è lontano
dalla realizzazione
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
La ricorsione sugli alberi
ContaFoglie (T)
// Post: ritorna il numero delle foglie di T
if IsEmptyTree(T) then return 0
else return Cf_aux(Root(T), T)
Cf_aux (n, T)
// Pre: n  T  
// Post: ritorna il numero delle foglie del sottoalbero di T con
radice in n
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
La ricorsione sugli alberi
Cf_aux (n, T)
// Pre: n  T  
// Post: ritorna il numero delle foglie del sottoalbero di T con radice in n
if Leaf(n, T) then return 1
else
// n ha almeno un figlio in T
Se m aveva un
fratello, allora
l’attuale valore di
m è un nodo di T
m  Child(n, T)
foglie  Cf_aux (m, T)
while HasSibling (m, T) do
m  Sibling (m, T)
foglie  foglie + Cf_aux (m, T)
return foglie
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Visite: Depth First Search
DFS (T)
// Post: visita i nodi di T in profondità
if T   then
visita Root(T)
siano T1, …, Tk i sottoalberi con radici nei
nodi figli di della radice di T
for i  1 to k do
DFS (Ti)
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Visite: Depth First Search
DFS (T)
// Post: visita i nodi di T in profondità
if not IsEmtyTree(T ) then
DFS_aux (Root(T), T)
DFS_aux (n, T)
// Post: visita in profondità il sottoalbero di T con radice in n
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Visite: Depth First Search
DFS_aux (n, T)
// Post: visita in profondità il sottoalbero di T con radice in n
cominciando dalla radice
visita n
if not Leaf (n, T) then
m  Child (n, T)
DFS_aux (m, T)
while HasSibling (m, T) do
m  Sibling(m, T)
DFS_aux (m, T)
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Il tipo BinTree
typedef struct tnode {
T info;
// etichetta
struct tnode *left, *right;
// puntatori ai figli sinistro e destro
} tNode;
typedef struct bintreeframe {
int card; // numero dei nodi dell’albero
tNode* root; // radice dell’albero
} BinTreeFrame
typedef BinTreeFrame* BinTree;
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Costruttori
tNode* NewtNode (T etc, tNode* l, tNode* r)
{
tNode* n = new tNode;
n->info = etc;
n->left = l; n->right = r;
return n;
}
BinTree NewBinTree (void)
{
BinTree bt = new BinTreeFrame;
bt->card = 0; bt->root = NULL;
return bt;
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Un esempio: la funzione Altezza
int Altezza (tNode* n)
// Pre: n != NULL
// Post: ritorna l’altezza dell’albero con radice in n
{
return Altezza_aux(n);
}
int Altezza_aux (tNode*)
// Post: ritorna l’altezza di tNode se != NULL, 0 altr.
{
int hl = 0, hr = 0;
if (n->left == NULL && n->right == NULL) return 0;
if (n->left != NULL) hl = Altezza_aux (n->left);
if (n->right != NULL) hr = Altezza_aux (n->right);
if (hl > hr) return hl + 1;
return hr + 1;
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
Visite in profondità
void preorder (tNode* n) {
if (n != NULL)
{
visit(n);
preorder(n->left);
preorder(n->right);
}
}
void inorder (tNode* n) {
if (n != NULL)
{
inorder(n->left);
visit(n);
inorder(n->right);
}
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
La lista dei vertici in preordine (1)
a
l
a
l
r
r
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
La lista dei vertici in preordine (2)
La soluzione ovvia è O(n2):
Node* Preorder_List (tNode* n)
{
if (n == NULL) return NULL;
return NewNode(n->info,
concat (Preorder_List(n->left),
Preorder_List(n->right));
}
La complessità quadratica deriva dall’uso di concat nel
caso in cui l’albero sia degenere sinistro.
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6
La lista dei vertici in preordine (3)
Esiste una soluzione ottima O(n):
Node* Preorder_List2 (tNode* n, Node* l)
{
if (n == NULL) return l;
return NewNode(n->info,
Preorder_List2(n->left,
Preorder_List2(n->right,l));
}
Ugo de'Liguoro - Informatica 2 a.a. 03/04 Lez. 6