Programmazione Mod. B - Alberi prof. E. Burattini
1
B
I GRAFI
C
5
2
3
20
A
D
1
15
F
E
3
B
C
5
Min(A-D) = {A,B,E,F,C,D} -->14
2
3
20
A
D
1
15
F
3
B
C
5
Min(A-F) = {A,B,E,F} -->11
E
3
20
A
2
D
1
15
Programmazione F
Mod. B3 - Alberi
Eprof. E. Burattini
2
B
5
2
3
20
A
A B C D E F
A
5
20
15
B
5
3
C
2
1
D 20
2
E
3
3
F 15
1
3
C
D
1
15
F
E
3
DEF.
Un albero è un grafo senza cicli o circuiti
B
5
20
A
1
15
F
A B C D E F
A
5
20
15
B
5
D
C
1
D 20
E
E
3
F - 15
1
3
Programmazione Mod. B - Alberi
3
C
3
prof. E. Burattini
GLI ALBERI COME STRUTTURE DATI
Search Tree - (Albero di ricerca) - Memorizza informazioni in maniera
tale che possano essere ritrovate molto velocemente e le operazioni di
inserimento e cancellazione nodi sono molto efficienti.
Programmazione Mod. B - Alberi prof. E. Burattini
4
Ricorsione lineare: al più una chiamata ricorsiva nell’ambito di uno stesso processo
ricorsivo.
Ricorsione non lineare: più di una chiamata ricorsiva nell’ambito di uno stesso
processo ricorsivo.
FUNCTION Fibonacci(N:integer):integer;
BEGIN
IF N=0 THEN
Fibonacci:=0
ELSE IF N=1 THEN
Fibonacci:=1
ELSE
Fibonacci:= Fibonacci(N-2) + Fibonacci(N-1)
END.
main
main
F(3)
F(1)
F(4)
Fibonacci(3)
F(2)
F(3)
F(2)
F(1)
F(1)
F(1)
Fibonacci(4)
F(2)
F(0)
Programmazione Mod. B - Alberi prof. E. Burattini
F(0)
5
F(1)
F(0)
F(6)
F(5)
F(4)
F(2)
F(1)
F(3)
F(0)
F(1)
F(2)
F(1)
F(1)
F(1)
1
+
F(0)
+
1F(1)
1F(2)
+
3F(4)
F(2)
F(1)
F(0)
+
F(1)
F(0)
F(2)
F(1)
F(0)
1F(1)
2F(3)
+
F(5)
F(6) Programmazione Mod. B - Alberi -
Fibonacci(6)
F(3)
0F(0)
F(0)
0
1F(2)
F(4)
F(3)
prof. E. Burattini
fibon1
6
ALBERI BINARI
• Un albero è binario se ogni nodo è al più collegato ad
altri due
• Un albero binario è:
– L’albero vuoto
– oppure è costituito da una radice e da un sottoalbero
sinistro e da un sottoalbero destro
• L’albero è una struttura ricorsiva non lineare.
• I suoi elementi sono detti nodi
Programmazione Mod. B - Alberi prof. E. Burattini
7
I due disegni rappresentano due alberi uguali ma due alberi binari
diversi.
L’ovvio modo di rappresentare un albero consiste nell’assegnare ad
ogni nodo due puntatori uno che punta al sottoalbero sinistro ed uno
che punta al sottoalbero destro.
Programmazione Mod. B - Alberi prof. E. Burattini
8
Per gestire gli alberi introduciamo un elemento costituito da nodi non più con uno ma
con due campi per i puntatori.
Attraverso questa struttura potremo rappresentare gli alberi di ricerca binari.
Radice (root)
Albero Binario
Sotto albero
Programmazione Mod. B - Alberi prof. E. Burattini
9
Ugo
Giulio
Emma
Anna
Carlo
Guido
Peppe
Carla
Angela
Programmazione Mod. B - Alberi prof. E. Burattini
Maria
Nicola
10
Definiamo sotto albero ogni nodo in cui almeno un puntatore non è uguale a NIL ma punta
ad un altro nodo o sotto albero.
Definiamo radice di un sotto albero quel nodo che punta ad almeno un altro nodo (NB
Negli alberi binari si può al massimo puntare a due nodi (destro e sinistro).
La variabile dinamica albero può essere definita attraverso la sua radice, il nodo a
partire dal quale si possono raggiungere tutti gli altri nodi della struttura.
Un albero (sotto albero), che punta a NIL e cioè non contiene nodi è detto albero (sotto
albero) vuoto.
Tree
XXX
Left Structure
Right Structure
Programmazione Mod. B - Alberi prof. E. Burattini
11
Altezza dell’albero= Massimo numero di livelli
H=3
Livello del nodo X = 3
Radice (root)
Albero Binario
Cammino
(path)
Sotto albero
Nodi fratelli
Genitore
X
Figlio
Programmazione Mod. B - Alberi prof. E. Burattini
Foglie
12
Un albero binario è ordinato quando il campo chiave di ogni
nodo è minore del campo chiave di ogni nodo del suo
sottoalbero destro ed è maggiore del campo chiave di ogni
nodo del suo sottoalbero sinistro. Si parla in questo caso anche
di binary search tree (BST).
Programmazione Mod. B - Alberi prof. E. Burattini
13
Un albero binario di ricerca (BST) è tale se:
- le foglie sinistre hanno un valore del campo chiave inferiore del nodo padre
- le foglie destre hanno un valore del campo chiave maggiore del nodo padre
Campo chiave
Left
Right
Key Field
Maria
Giulio
Dora
Anna
Sergio
Guido
Riccardo
Toni
Roberto
Luigi
Programmazione Mod. B - Alberi -
Ugo
14
prof. E. Burattini
CONST
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo NIL’
TYPE
KItemType= STRING[20]
InfoType= un data type per le informazioni non key
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
Key:KItemType;
Info: InfoType;
Left,
Right: BSTP
END;
VAR
TNode:BSTP;
TNode
Left
Key
Info
Programmazione Mod. B - Alberi prof. E. Burattini
Right
15
TNode
Left
Key
Info
Right
Le operazioni che ci interessa definire sono:
•creazione di un nuovo nodo con un valore assegnato ai campi dati (Key e Info) e NIL
ai campi link (Left e Right)
•dispose (dealloca) di un nodo supposto che esso esista come variabile dinamica
•selezionare un nodo data una chiave
•selezionare le Info collegate al nodo
•selezionare il figlio a sinistra di un dato nodo
•selezionare il figlio a destra di un
dato nodo
Programmazione Mod. B - Alberi prof. E. Burattini
16
INTERFACE
PROCEDURE MakeTNode(KeyValue:KItemType; TheInfo:InfoType; VAR TNode:BSTP);
{ Crea un nuovo nodo, assegnando a KeyValue e TheInfo un valore e il valore NIL per i campi Left e
Right }
PROCEDURE KillTNode(VAR TNode: BSTP);
{dispose la memoria allocata per il TNode e poi pone il TNode a NIL. }
PROCEDURE GetNodesKey(TNode:BSTP; VAR TheKey:KItemType);
{ritorna il key field del nodo puntato da Tnode, se Tnode è NIL allora ritorna il valore di NullKey}
PROCEDURE GetNodesInfo(TNode:BSTP; VAR TheInfo:InfoType);
{ritorna le informazioni del nodo puntato da Tnode, se Tnode è NIL allora ritorna il valore di NullInfo}
TNode
Left
Key
Info
Right
CONST
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo NIL’
TYPE
KItemType= STRING[20]
InfoType= un data type per le informazioni non key
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
Key:KItemType;
Info: InfoType;
Left, Right: BSTP
END;
Programmazione Mod. B - Alberi
17
VAR prof. E. Burattini
FUNCTION NodesLeftTree(TNode:BSTP) : BSTP;
{ritorna il puntatore al sotto albero sinistro di Tnode. Se T Node è NIL allora ritorna NIL }
FUNCTION NodesRightTree(TNode:BSTP) : BSTP;
{ritorna il puntatore al sotto albero destro di Tnode. Se T Node è NIL allora ritorna NIL }
TNode
Left
Key
Info
Right
CONST
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo NIL’
TYPE
KItemType= STRING[20]
InfoType= un data type per le informazioni non key
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
Key:KItemType;
Info: InfoType;
Left, Right: BSTP
END;
VAR
TNode:BSTP;
Programmazione Mod. B - Alberi 18
prof. E. Burattini
PROCEDURE MakeTNode(KeyValue:KItemType; TheInfo:InfoType; VAR TNode:BSTP);
{ Crea un nuovo nodo, assegnando a KeyValue e TheInfo un valore e il valore NIL per i campi
Left e Right }
BEGIN
new(Tnode);
WITH TNode^ DO
BEGIN
Key:=KeyValue;
Info:=TheInfo;
Left:=NIL;
Right:=NIL
END
END;
TNode
Left
Key
CONST
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo NIL’
TYPE
KItemType= STRING[20]
InfoType= un data type per le informazioni non key
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
Key:KItemType;
Info
Right
Info: InfoType;
Left, Right:
BSTP
Programmazione Mod. B - Alberi
19
END;
prof. E. Burattini
PROCEDURE KillTNode(VAR TNode :BSTP);
{dispose la memoria allocata per il TNode e poi pone il TNode a NIL. }
BEGIN
IF Tnode <> NIL THEN
BEGIN
dispose(TNode);
Tnode:=NIL
END
END;
TNode
Left
Key
CONST
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo NIL’
TYPE
KItemType= STRING[20]
InfoType= un data type per le informazioni non key
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
Key:KItemType;
Info
Right
Info: InfoType;
Left, Right:
BSTP
Programmazione Mod. B - Alberi
20
END;
prof. E. Burattini
PROCEDURE GetNodesKey(TNode:BSTP; VAR TheKey:KItemType);
{ritorna il key field del nodo puntato da Tnode, se Tnode è NIL allora ritorna il valore di NullKey}
BEGIN
IF TNode <> NIL THEN
TheKey:= TNode ^.Key
ELSE
TheKey:= NullKey
END;
TNode
Left
Key
CONST
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo NIL’
TYPE
KItemType= STRING[20]
InfoType= un data type per le informazioni non key
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
Key:KItemType;
Info
Right
Info: InfoType;
Left, Right:
BSTP
Programmazione Mod. B - Alberi
21
END;
prof. E. Burattini
PROCEDURE GetNodesInfo(TNode:BSTP; VAR TheInfo:InfoType);
{ritorna le informazioni del nodo puntato da Tnode, se Tnode è NIL allora ritorna il valore di
NullInfo}
BEGIN
IF TNode <> NIL THEN
TheInfo:= TNode ^.Info
ELSE
TheKey:= NullInfo
END;
TNode
Left
Key
CONST
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo NIL’
TYPE
KItemType= STRING[20]
InfoType= un data type per le informazioni non key
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
Key:KItemType;
Info
Right
Info: InfoType;
Left, Right:
BSTP
Programmazione Mod. B - Alberi
22
END;
prof. E. Burattini
FUNCTION NodesLeftTree(TNode:BSTP) : BSTP;
{ritorna il puntatore al sotto albero sinistro di Tnode. Se T Node è NIL allora ritorna NIL }
BEGIN
IF Tnode <> NIL THEN
NodesLeftTree:=Tnode^.Left
ELSE
NodesLeftTree:=NIL
END:
TNode
Left
Key
CONST
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo NIL’
TYPE
KItemType= STRING[20]
InfoType= un data type per le informazioni non key
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
Key:KItemType;
Info
Right
Info: InfoType;
Left, Right:
BSTP
Programmazione Mod. B - Alberi
23
END;
prof. E. Burattini
FUNCTION NodesRightTree(TNode:BSTP) : BSTP;
{ritorna il puntatore al sotto albero destro di Tnode. Se T Node è NIL allora ritorna NIL }
BEGIN
IF Tnode <> NIL THEN
NodesRightTree:=Tnode^. Right
ELSE
NodesRightTree:=NIL
END:
TNode
Left
Key
CONST
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo NIL’
TYPE
KItemType= STRING[20]
InfoType= un data type per le informazioni non key
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
Key:KItemType;
Info
Right
Info: InfoType;
Left, Right:
BSTP
Programmazione Mod. B - Alberi
24
END;
prof. E. Burattini
Pseudo codice per un algoritmo generalizzato di selezione nodi
PROCEDURE GetNodeField(ANode:NodeP; VAR FieldVar: FieldType)
IF ANode <> NIL THEN
FieldVar  ANode^.identificatore della variabile di campo selezionata
ELSE
FieldVar  NullValue
Programmazione Mod. B - Alberi prof. E. Burattini
25
Gli stessi dati possono essere contenuti in alberi binari di forma diversa.
Guido
Anna
Ugo
Dora
Dora
Giulio
Anna
Giulio
Sergio
Guido
Maria
Toni
Luigi
Luigi
Riccardo
Maria
Riccardo
Maria
Sergio
Giulio
Sergio
Toni
Dora
Guido
Riccardo
Toni
Ugo
Anna
Luigi
Programmazione Mod. B - Alberi
Ugo prof. E. Burattini
26
Un albero si dice bilanciato se il livello di tutte le foglie è uguale all’altezza dell’albero o a
questa stessa altezza meno 1.
H=3
L=3
H=3
L=2
Foglie
Programmazione
Mod. B - Alberi prof. E. Burattini
L=3
27
L=0
L=1
L=2
L=3
Foglie
L=4
L=5
H=5
Programmazione Mod. B - Alberi prof. E. Burattini
28
Un albero bilanciato si esplora per fare una ricerca in un numero di passi inferiore a quello necessario per
esplorare un albero non bilanciato. Nell’esempio supponiamo di cercare Riccardo:
Guido
Anna
Ugo
Dora
Dora
6 passi di computazione
Giulio
Anna
Giulio
Sergio
Guido
4 passi di computazione
Maria
Toni
Luigi
Luigi
Riccardo
Maria
Riccardo
Maria
Sergio
Giulio
Sergio
Toni
Dora
Guido
Riccardo
Toni
Ugo
Anna
Luigi
Roberto
Programmazione
Mod. B - Alberi
Ugo prof. E. Burattini
29
2 passi di computazione
Se un albero bilanciato ha M livelli, il numero di nodi di cui è
formato può variare tra
2M
e
2(M+1) -1.
In un albero bilanciato il tempo massimo di ricerca è di O(log2 (N))
dove N è il numero di nodi.
Programmazione Mod. B - Alberi prof. E. Burattini
30
ALBERO BILANCIATO CON M LIVELLI
N°
NODI
N°
NODI
20
0
20
21
1
21
M
2M
2 M 1
1
M 1
1 2
i 0
M
i
Totale Nodi
Programmazione Mod. B - Alberi prof. E. Burattini
Totale Nodi
i
2

i 0
31
M 1
M
i 0
i 0
1   2 i  N  2 i
M 1
a

(
1

x
)
i
ax 

1 x
i 0
M
Serie geometrica
a 1
x2
M 1
(
1

2
)
i
M 1
2


2
1

1 2
i 0
M
1  2 M  1  N  2 M 1  1
2
M
N 2
M 1
Programmazione Mod. B - Alberi prof. E. Burattini
1
32
Supponiamo sia assegnata una lista di N oggetti tra i quali esiste una relazione d’ordine.
Se riusciamo a inserire questi oggetti in un albero di ricerca bilanciato allora il numero di
passi per trovare un qualunque oggetto è limitato da O(log2(N)).
Se questo non avviene il caso peggiore in cui possiamo trovarci è pari a O(N).
Anna
N
O(N)
1.000
1.000.000
100.000.000
Dora
Giulio
1.000
1.000.000
100.000.000
LOG(N)
9,97
19,93
26,58
1,36*LOG(N)
14
27
36
Guido
Luigi
Maria
Riccardo
Sergio
Toni
Ugo
Si può dimostrare che un albero di ricerca binario costruito in maniera casuale, quindi non
necessariamente bilanciato, effettua
in media un
numero
di -passi per effettuare la ricerca
Programmazione
Mod.
B - Alberi
33 pari
prof. E. Burattini
a 1.36 * O(log2(N)).
ESEMPIO
Supponiamo di avere un albero di tipo BST, chiamiamo con Root il primo nodo.
Scrivere una funzione LeftMost che fornisca il puntatore del nodo più a sinistra che si
incontra a partire da Root.
Maria
Sergio
Giulio
Dora
Anna
Key
Riccardo
Toni
Roberto
Root
Left
Guido
Info
CONST
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo NIL’
TYPE
KItemType= STRING[20]
InfoType= un data type per le informazioni non key
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
Key:KItemType;
Info: InfoType;
Right
Programmazione Mod. B - Alberi
Left, Right:
BSTP
34
prof. E. Burattini END;
FUNCTION LeftMost(Root: BSTP): BSTP;
Definizione della funzione
VAR
NodoEsaminato:BSTP;
Definizione delle variabili
BEGIN
IF EmptyTree(Root) THEN
NodoEsaminato = NIL;
ELSE
NodoEsaminato = Root;
Verifica se l’albero è vuoto
WHILE NodesLeftTree(NodoEsaminato) <> NIL DO
Cerca il nodo
NodoEsaminato = NodesLeftTree(NodoEsaminato) ;
LeftMost: = NodoEsaminato
END:
CONST
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo N
FUNCTION NodesLeftTree(TNode:BSTP) : BSTP; TYPE
KItemType= STRING[20]
BEGIN
InfoType= un data type per le informazioni non key
IF Tnode <> NIL THEN
BSTP=^BSTNode
{puntatore a un nodo}
NodesLeftTree:=Tnode^.Left
BSTNode = RECORD
ELSE
Key:KItemType;
NodesLeftTree:=NIL
Info: InfoType;
END:
Programmazione Mod. B - Alberi -Left, Right: BSTP
35
END;
prof. E. Burattini
VAR Root:BSTP;
{ Dato un albero binario calcolare il puntatore dell'ultimo nodo
a sinistra.}
Program AlberoSin(input,output);
uses Crt, Alberi0;
CONST
var Albero,: BSTP;
FUNCTION ChiaveNodiSin(Tree:BSTP):BSTP;
BEGIN
IF EmptyTree(NodesLeftTree(Tree)) THEN
ChiaveNodiSin:=Tree
ELSE
BEGIN
ChiaveNodiSin:=ChiaveNodiSin(NodesLeftTree(Tree));
END;
END;
{************** MAIN***********}
begin
writeln('Costruiamo un Albero. ');
BuildNameTree(Albero);
WriteAlbero(Albero);
writeln(' La chiave e''
', ChiaveNodiSin(Albero)^.Key);
Programmazione
Mod. B - Alberi prof. E. Burattini
end.
36
OPERAZIONI SUI BST
Ogni nodo di un BST punta ad altri due nodi, ciascuno dei quali è una variabile dinamica
di tipo record.
Quindi una variabile di tipo BSTType, cioè un puntatore alla radice di un BST, che è a
sua volta una variabile BST, può essere passata da un blocco ad un altro. In altre parole
dato un nodo di un BST, questo è radice per i suoi sottoalberi e i nodi a cui punta sono a
loro volta radici di altri sottoalberi. Pertanto possiamo adoperare ricorsivamente queste
variabili.
Poiché una variabile BST può essere interpretata o come nodo di un BST o come un
sotto albero di un BST, pur essendo variabili dello stesso tipo parleremo nel primo
caso di un tipo BSTP (puntatore a un nodo) e nel secondo caso di un tipo BSTType
(puntatore a un albero)
CONST
NomeAlbero
Left
Key
NullKey= ’un simbolo o valore per indicare NIL ' ;
NullInfo=‘quando possibile assegna un significato al nodo NIL’
TYPE
KItemType= STRING[20]
InfoType= un data type per le informazioni non key
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
Key:KItemType;
Info: InfoType;
Info
Right
Left, Right: BSTP
END;
BSTType=BSTP
VAR
Programmazione
Mod. B - Alberi 37
NomeAlbero:BSTType
prof. E.
Burattini
Nodo:BSTP;
INTERFACE
PROCEDURE MakeTree(VAR Tree: BSTType);
{inizializza a NIL l’albero, creando un albero vuoto}
PROCEDURE AddTNode(KeyValue:KItemType; TheInfo:InfoType;VAR Tree: BSTType;
VAR Done:boolean);
{aggiunge un nodo all’albero rispettando la struttura di un BST, se il KeyValue è già
presente nell’albero non fa nulla e Done risulta False}
PROCEDURE DeleteTNode(KeyValue:KItemType;VAR Tree: BSTType;
VAR Done:boolean);
{elimina il nodo con chiave KeyValue, se esso non esiste Done risulta False}
FUNCTION SearchTNode(Tree: BSTType; KeyValue:KItemType): BSTP;
{cerca il nodo con chiave KeyValue, se esso non esiste ritorna NIL}
FUNCTION EmptyTree(Tree: BSTType): boolean;
{ritorna vero se l’albero è vuoto}
Programmazione Mod. B - Alberi prof. E. Burattini
38
IMPLEMENTATION
PROCEDURE MakeTree(VAR Tree: BSTType);
{inizializza a NIL l’albero, creando un albero vuoto}
BEGIN
Tree:=NIL
END;
FUNCTION EmptyTree(Tree: BSTType): boolean;
{ritorna vero se l’albero è vuoto}
BEGIN
EmptyTree:=Tree=NIL
END;
Programmazione Mod. B - Alberi prof. E. Burattini
39
ESEMPIO: COSTRUZIONE DI UN BST DI NOMI
TNode
Left
Key
Info
Right
CONST
NullKey= ’ ' ;
NullInfo=‘ ’
TYPE
KItemType= STRING[20]
InfoType= STRING[20]
BSTP=^BSTNode
{puntatore a un nodo}
BSTNode = RECORD
{variabile dinamica per un nodo}
Key:KItemType;
Info: InfoType;
Left,
{radice del sottoalbero di sinistra}
Right: BSTP
{radice del sottoalbero di destra}
END;
BSTType=BSTP;
{definizione per la variabile albero}
VAR
NameTree:BSTType;
Programmazione Mod. B - Alberi 40
prof. E. Burattini
COSTRUZIONE DI UN BST DI NOMI
Maria
Giulio
Dora
Sergio
Guido
Riccardo
Anna
Toni
Roberto
Supponiamo che vengano introdotti da tastiera i seguenti nomi:
Programmazione Mod. B - Alberi prof. E. Burattini
Maria
Giulio
Sergio
Dora
Guido
Riccardo
Toni
Anna
Roberto
return
41
Pseudo codice
MakeTree(NameTree)
introduci Nome
WHILE Nome <> NullKey DO
AddTNode(Nome, NullInfo, NameTree, Success)
IF NOT Success THEN
segnala che il Nome esiste già
introduci il nome
mostra il messaggio di fine lavoro
Programmazione Mod. B - Alberi prof. E. Burattini
42
PROCEDURE BuildNameTree(VAR NameTree: BSTType);
{costruisce un albero a cui assegna un Nome dato in input}
VAR
Nome:KItemType;
Success: boolean;
BEGIN
MakeTree(NameTree);
write(‘ Dammi un nome : ‘);
readln(Nome);
WHILE Nome <> NullKey DO
BEGIN
AddTNode(Nome, NullInfo, NameTree, Success); CONST
NullKey= ’ ' ;
IF NOT Success THEN
NullInfo=‘ ’
writeln( Nome, ‘ esiste già’);
TYPE
write(‘ Dammi un nome : ‘);
KItemType= STRING[20]
readln(Nome)
InfoType= STRING[20]
BSTP=^BSTNode
END;
writeln(‘ L’albero è stato piantato’);
BSTNode = RECORD
END;
Key:KItemType;
Info: InfoType;
Left,
Right: BSTP
END;
BSTType=BSTP;
Programmazione Mod. B - Alberi -VAR
43
prof. E. Burattini
NameTree:BSTTYpe;
DEFINIZIONE DI
ATTRAVERSAMENTO DI UN BST
Maria
Giulio
Dora
Anna
Sergio
Guido
Riccardo
Toni
Roberto
Visitare tutti i nodi di un BST di nomi, a partire dalla radice, e elencare i nomi in ordine
crescente (o decrescente).
Anna
Dora
Giulio
Guido
Maria
Riccardo
Roberto
Sergio
Programmazione Mod. B - Alberi Toni
prof. E. Burattini
44
MOSTRA IL CONTENUTO DI UN BST
Pseudo codice
Mostra le Chiavi (KeyItem) di tutti i nodi del sottoalbero sinistro di NameTree
Mostra la Chiave (KeyItem) della radice di NameTree
Mostra le Chiavi (KeyItem) di tutti i nodi del sottoalbero destro di NameTree
Maria
Giulio
Dora
Sergio
Guido
Anna
Riccardo
Toni
Roberto
ShowTree(NodesLeftTree(NameTree));
GetNodesKey(NameTree, Nome);
Writeln(Nome)
ShowTree(NodesRightTree(NameTree));
Programmazione Mod. B - Alberi prof. E. Burattini
45
La procedura ShowTree(NameTree) è una procedura ricorsiva il cui caso base è
rappresentato dall’albero vuoto (EmptyTree). In altre parole il processo di pop inizia non
appena l’argomento di ShowTree(NameTree) è un albero vuoto.
PROCEDURE ShowTree(NameTree: BSTType);
VAR
NodesKey: KItemType;
BEGIN
IF NOT EmptyTree(NameTree) THEN
BEGIN
ShowTree(NodesLeftTree(NameTree));
GetNodesKey(NameTree, Nome);
writeln(Nome)
ShowTree(NodesRightTree(NameTree));
END
END;
Programmazione Mod. B - Alberi prof. E. Burattini
46
Esercizio
Analizzare la seguente procedure ricorsiva e descrivere il suo
comportamento con un esempio
PROGRAM WriteAlbero(Tree:BSTP);
PROCEDURE Wa(Tree:BSTP;I:integer);
VAR
J:integer;
BEGIN
IF NOT EmptyTree(Tree) THEN
BEGIN
Wa(NodesRightTree(Tree),I+1);
FOR J:=1 TO I DO
write(' ');
write(Tree^.Key);
writeln;
Wa(NodesLeftTree(Tree),I+1);
END;
END;
{************* MAIN***********}
BEGIN
IF NOT EmptyTree(Tree) THEN
Wa(Tree,1)Programmazione Mod. B - Alberi prof. E. Burattini
END;
47
Ricorsione lineare: al più una chiamata ricorsiva nell’ambito di uno stesso processo
ricorsivo.
Ricorsione non lineare: più di una chiamata ricorsiva nell’ambito di uno stesso
processo ricorsivo.
FUNCTION Fibonacci(N:integer):integer;
BEGIN
IF N=0 THEN
Fibonacci:=0
ELSE IF N=1 THEN
Fibonacci:=1
ELSE
Fibonacci:= Fibonacci(N-2) + Fibonacci(N-1)
END.
main
main
F(3)
F(1)
F(4)
Fibonacci(3)
F(2)
F(3)
F(2)
F(1)
F(1)
F(1)
Fibonacci(4)
F(2)
F(0)
Programmazione Mod. B - Alberi prof. E. Burattini
F(0)
48
F(1)
F(0)
F(6)
F(5)
F(4)
F(2)
F(1)
F(3)
F(0)
F(1)
F(2)
F(1)
F(1)
F(1)
1
+
F(0)
+
1F(1)
1F(2)
+
3F(4)
F(2)
F(1)
F(0)
+
F(1)
F(0)
F(2)
F(1)
F(0)
1F(1)
2F(3)
+
F(5)
F(6) Programmazione Mod. B - Alberi -
Fibonacci(6)
F(3)
0F(0)
F(0)
0
1F(2)
F(4)
F(3)
prof. E. Burattini
fibon1
49
RICERCA DI UN DATO SU UN BST
Maria
Giulio
Dora
Anna
Sergio
Guido
Riccardo
Toni
Roberto
Riccardo ?????????
Programmazione Mod. B - Alberi prof. E. Burattini
50
FUNCTION Binary (VAR Studenti: StudenteRecord; MatrCercata:StringaNome;
Lo, Hi :integer) :integer
VAR
Mid:integer;
BEGIN
IF Lo>Hi THEN
Binary := 0
ELSE
BEGIN
Mid  (Lo+Hi) DIV 2
IF Studenti[Mid].Matr=MatrCercata THEN
CASE BASE 1
Binary := Mid
ELSE
IF Studenti[Mid].Matr<MatrCercata THEN
CASE BASE 2
Binary := Binary(Studenti, MatrCercata, Mid+1, Hi)
ELSE
Binary := Binary(Studenti, MatrCercata, Lo, Mid-1)
END;
ESPRESSIONE RICORSIVA
END;
Programmazione Mod. B - Alberi prof. E. Burattini
51
FUNCTION SearchTNode(Tree: BSTType; KeyValue:KItemType): BSTP;
{cerca il nodo con chiave KeyValue, se esso non esiste ritorna NIL}
VAR
TheKey: KItemType;
BEGIN
IF EmptyTree(Tree) THEN
SearchTNode  NIL
ELSE
TheKey:= TNode ^.Key
BEGIN
GetNodesKey(Tree, TheKey)
IF TheKey = KeyValue THEN
SearchTNode  Tree
NodesLeftTree:=Tnode^.Left
ELSE
IF KeyValue < TheKey
SearchTNode  SearchTNode(NodesLeftTree(Tree), KeyValue)
ELSE
SearchTNode  SearchTNode(NodesRightTree(Tree), KeyValue)
END
END;
NodesLeftRight:=Tnode^. Right
Programmazione Mod. B - Alberi prof. E. Burattini
52
ESERCIZIO
Sia assegnato un albero binario, scrivere un algoritmo tale che sposti ogni figlio
sinistro nel corrispondente figlio destro e viceversa.
A
A
B
D
C
E
G
C
F
B
F
H
H
Programmazione Mod. B - Alberi prof. E. Burattini
E
D
G
53
{ Scrivere un algoritmo che dato un albero
binario lo trasformi invertendo i figli
sinistro e destro di ogni nodo }
Program AlberoScambio(input,output);
{************** MAIN***********}
uses Crt, Alberi0;
CONST
begin
NKey=-100;
clrscr;
var Albero,Temp : BSTP;
writeln('Costruiamo un Albero. ');
Item: KItemType;
BuildNameTree(Albero);
Chiave:KItemType;
WriteAlbero(Albero);
Info:InfoType;
readln;
Done:boolean;
PROCEDURE ScambiaNodi(Tree:BSTP);
{scambia nodi}
ScambiaNodi(Albero);
writeln(' SCAMBIO ');
WriteAlbero(Albero);
writeln(' FINE');
readln;
BEGIN
IF NOT EmptyTree(Tree) THEN
BEGIN
ScambiaNodi(NodesLeftTree(Tree));
ScambiaNodi(NodesRightTree(Tree));
end.
Temp:=Tree^.Left;
Tree^.Left:= Tree^.Right;
Tree^.Right:=Temp;
END;
Programmazione Mod. B - Alberi END;
prof. E. Burattini
54
AGGIUNTA DI UN DATO SU UN BST
Per aggiungere un nodo a un BST è necessario innanzitutto verificare che l’Item non
esiste già, perché in tal caso il nodo non viene aggiunto. Se non esiste bisogna trovare la
sua corretta posizione nell’albero, cioè il suo genitore e mettere poi i figli a NIL.
Maria
Giulio
Dora
Sergio
Guido
Riccardo
Toni
Roberto
Anna
Programmazione Mod. B - Alberi prof. E. Burattini
Rolando
55
PROCEDURE AddTNode(KeyValue:KItemType; TheInfo:InfoType;VAR Tree: BSTType;
VAR Done:boolean);
{aggiunge una foglia all’albero rispettando la struttura di un BST, se il KeyValue è già
presente nell’albero non fa nulla e Done risulta False}
PROCEDURE DeleteTNode(KeyValue:KItemType;VAR Tree: BSTType;
VAR Done:boolean);
{elimina il nodo con chiave KeyValue ricostruendo la struttura BST. Se il Nodo non esiste
Done risulta False}
Programmazione Mod. B - Alberi prof. E. Burattini
56
Se il nodo che vogliamo inserire, avente un certo
Pseudo Codice di AddTNode
KeyValue, esiste, allora Tnode non è vuoto e
quindi non lo aggiungiamo altrimenti lo
.Search(Tree, KeyValue, TNode, Parent)
aggiungiamo
IF NOT EmptyTree(TNode) THEN
Done  FALSE
ELSE
crea e aggiungi un nuovo nodo come figlio del nodo Parent
Done  TRUE
Cerca sull’albero Tree il puntatore (TNode) al nodo con KeyValue, se esiste
ritorna anche il padre, Parent, del nodo cercato altrimenti TNode=NIL.
Programmazione Mod. B - Alberi prof. E. Burattini
57
PROCEDURE AddTNode(KeyValue:KItemType; TheInfo:InfoType;VAR Tree: BSTType;
VAR Done: boolean);
VAR
Tnode, Parent : BSTP;
{deve valere NIL se il nodo esiste già}
ParentsKey: KeyItemType; {genitore del nodo da aggiungere}
BEGIN
Search(Tree, KeyValue, TNode, Parent)
IF NOT EmptyTree(TNode) THEN
{il nodo esiste già}
Done := FALSE
ELSE
{crea e aggiungi un nuovo nodo come figlio del nodo Parent}
BEGIN
IF EmptyTree(Parent) THEN
{il nuovo nodo sarà la radice}
MakeTNode(KeyValue, TheInfo, Tree)
ELSE
BEGIN
GetNodesKey(Parent, ParentsKey); {puntatore di ParentsKey}
IF ParentsKey > KeyValue THEN {il nuovo nodo va a left}
MakeTNode(KeyValue, TheInfo, Parent^.Left)
ELSE
{il nuovo nodo va a right}
MakeTNode(KeyValue, TheInfo, Parent^.Right)
END;
Done := TRUE
END
Programmazione Mod. B - Alberi 58
prof. E. Burattini
END;
Search
Il padre dell’ultimo nodo esaminato
durante la ricerca di KeyValue
Search(Tree, KeyValue, TNode, Parent)
Obiettivo: cercare un cammino verso un determinato nodo dell’albero.
Se il nodo non esiste ritorna NIL. Se esiste ritorna il puntatore al nodo individuato e
quello di suo padre.
Pseudo Codice
Parent  NIL {la root non ha genitori}
TNode  Tree {la radice è il primo nodo esaminato}
GetNodesKey(TNode, NodesKey)
{estrai la chiave del nodo in esame}
WHILE ci sono altri nodi da esaminare AND non si è ancora trovato il nodo DO
Parent  TNode
Tnode  il sottoalbero legato al KeyValue
GetNodesKey(TNode, NodesKey)
{estrai la chiave del nodo in esame}
EmptyTree(TNode)
NodesKey <> KeyValue
IF NodesKey > KeyValue THEN
TNode  radice del sottoalbero sinistro
ELSE Programmazione Mod. B - Alberi prof.del
E. Burattini
TNode  radice
sottoalbero destro
59
PROCEDURE Search(Tree: BSTT, KeyValue: KItemType, VAR TNode, Parent: BSTP);
VAR
NodesKey: KItemType;
BEGIN
Parent:= NIL; {la root non ha genitori}
Tnode:= Tree; {la radice è il primo nodo esaminato}
GetNodesKey(TNode, NodesKey);
{estrai la chiave del primo nodo}
WHILE NOT EmptyTree(TNode) AND (NodesKey <> KeyValue) DO
BEGIN
Parent:= Tnode;
IF NodesKey > KeyValue THEN
Tnode:= NodesLeftTree(TNode)
ELSE
Tnode:= NodesRightTree(TNode);
GetNodesKey(TNode, NodesKey) {estrai la chiave del nodo in esame}
END
END;
che- GetNodesKey nel
ProgrammazioneRicordarsi
Mod. B - Alberi
prof. E. caso
Burattini
trovi NIL ritorna NullKey
60
Pseudo Codice
Search
Parent  NIL {la root non ha genitori}
TNode  Tree {la radice è il primo nodo esaminato}
GetNodesKey(TNode, NodesKey)
{estrai la chiave del nodo in esame}
WHILE ci sono altri nodi da esaminare AND non si è ancora trovato il nodo DO
19
Parent  TNode
Tnode  il sottoalbero legato al KeyValue
GetNodesKey(TNode, NodesKey)
13
12
21
15
14
20
17
16
{estrai la chiave del nodo in esame}
18
24
Aggiungi 17
Tnode  NIL
Aggiungi 22
Tnode = NIL
BEGIN
Search(Tree, KeyValue, TNode, Parent)
IF NOT EmptyTree(TNode) THEN
{il nodo esiste già}
23
Done := FALSE
26
ELSE
{crea e aggiungi un nuovo nodo come figlio del nodo Parent}
BEGIN
IF EmptyTree(Parent) THEN
MakeTNode(KeyValue, TheInfo, Tree) {il nuovo nodo sarà la radice}
22
ELSE
BEGIN
GetNodesKey(Parent, ParentsKey);
IF ParentsKey > KeyValue THEN {il nuovo nodo va a sinistra}
MakeTNode(KeyValue, TheInfo, Parent^.Left)
ELSE
{il nuovo nodo va a destra}
MakeTNode(KeyValue, TheInfo, Parent^.Right)
END;
AddTNode
Programmazione Mod. B - Alberi - Done := TRUE
61
END
prof. E. Burattini
END;
ESERCIZIO
{Scrivere una procedura o funzione che assegnato un albero
binario di interi e un livello Lev conti il numero num di
tutti i nodi presenti in quel livello. }
riga
19
13
12
21
15
14
20
17
16
18
24
23
lev
26
22
Programmazione Mod. B - Alberi prof. E. Burattini
62
riga
19
13
12
21
15
14
20
17
16
24
23
18
26
lev
22
T14, riga=3,
T17, riga=3,
lev=3, num= 1
lev=3, num= 2
procedure ContaLivello(Tree:BSTP;
riga,lev:integer;VAR num:integer);
BEGIN
if not (emptytree(tree)) THEN
BEGIN
IF riga=lev THEN num:=num+1;
IF riga<lev THEN
BEGIN
ContaLivello(NodesLeftTree(tree)
riga+1,lev,num);
ContaLivello(NodesRightTree(tree),
riga+1,lev,num);
END;END;END;
T23, riga=3,
T26, riga=3,
lev=3, num= 3
lev=3, num= 4
T12, riga=2,
T15,
T15, riga=2,
riga=2,
T20, riga=2,
T24, riga=2,
lev=3, num= 0
lev=3,
lev=3, num=
num= 021
lev=3, num= 2
num= 2
lev=3, num=4
T13, riga=1,
T21,
T21, riga=1,
riga=1,
lev=3, num= 20
lev=3,
lev=3, num=
num= 24
T19, riga=0,
lev=3, num= 4
20
Programmazione Mod. B - Alberi prof. E. Burattini
63
Problema
Realizzare una procedura che elimina il nodo con chiave KeyValue
Ritorna la chiave CandsKey puntata da Candidate
Pseudo Codice
Search(Tree, KeyValue, Candidate, Parent)
GetNodesKey(Candidate, CandsKey)
IF CandsKey <> KeyValue THEN
Done  FALSE
ELSE
riorganizza l’albero dopo aver rimosso Candidate
KillTNode(Candidate)
Done  TRUE
Implica che se cerco di nuovo un nodo con chiave CandsKey non lo
trovo e che l’albero che resta, deallocando il nodo Candidate, è ancora
un BST
Programmazione Mod. B - Alberi prof. E. Burattini
64
Analizziamo il problema della riorganizzazione dell’albero una volta eliminato un nodo.
Caso a- il nodo da eliminare ha il sotto albero sinistro vuoto.
Parent
Candidate
QQQ
Eliminare
Riccardo
Maria
RRR
Giulio
Sergio
Dora
Guido
Riccardo
Toni
Anna
left
right
Roberto
Caso b- il nodo da eliminare ha il sotto albero destro vuoto.
La procedura è analoga alla precedente.
65
Pseudo Codice
IF EmptyTree(NodesLeftTree(Candidate)) THEN
LinkParent(Candidate, NodesRightTree(Candidate), Parent, Tree)
ELSE
IF EmptyTree(NodesRightTree(Candidate)) THEN
LinkParent(Candidate, NodesLeftTree(Candidate), Parent, Tree)
ELSE
continua a riorganizzare l’albero
Parent
Candidate
QQQ
RRR
left
right
PROCEDURE LinkParent (OldChild, NewChild, Parent: BSTP;VAR Tree: BSTType);
{riorganizza l’albero BST dopo l’eliminazione di un nodo}
Programmazione Mod. B - Alberi prof. E. Burattini
66
Riassunto dei tipi di cancellazione
Old
Parent
New
Old
New
PROCEDURE DeleteTNode(KeyValue:KItemType;VAR Tree: BSTType; VAR Done:boolean);
{elimina il nodo con chiave KeyValue ricostruendo la struttura BST. Se il Nodo non esiste Done
risulta False}
Programmazione Mod. B - Alberi prof. E. Burattini
67
Nel caso in cui il Nodo da cancellare ha sia il sotto albero di sinistra che quello di destra
allora si procede come segue:
si sostituisce al nodo da cancellare o il nodo di valore maggiore del suo sottoalbero di
sinistra o quello di valore minore del suo sotto albero di destra. Se questo nodo ha a
sua volta un sottoalbero di destra e uno di sinistra ci si comporta nei suoi confronti
come se fosse un nodo da cancellare e quindi si esegue la stessa procedura sopra
descritta.
Nodo da cancellare
35
30
40
5
3
3
40
5
8
80
35
38
Programmazione Mod. B - Alberi prof. E. Burattini
8
80
35
38
68
PROCEDURE DeleteTNode(KeyValue: KItemType; VAR Tree:BSTType; VAR Done:boolean);
VAR
Candidate,
{puntatore al nodo candidato per la cancellatura}
Parent,
{puntatore al genitore del nodo candidato}
OldCandidate :BSTP;
CandsKey: KItemType:
Se il sottoalbero sinistro è
BEGIN
Se ilcollega
sottoalbero
destrodiè
vuoto
il genitore
Done:= TRUE
vuoto collega
genitore
di
candidate
con la il
radice
del sotto
della Key
da eliminare
candidate
radice dele
Search(Tree, KeyValue, Candidate, Parent); Fornisce il puntatore
albero
destro.con
Se la
Parent=NIL,
quello del suo genitore.
Se Candidate=NIL
sotto
albero
sinistro. Se
GetNodesKey(Candidate, CandsKey);
cioè
si vuole
cancellare
la
Fornisce
la chiave
CandsKey
Candidate
significa che
la Key
non c’è. dicioè
Parent=NIL,
si
vuole
radice allora poni in Tree la
IF CandsKey<> KeyValue THEN
cancellare
la radice
allora
radice
del
sotto
albero
destro.
Done:=FALSE
Non c’è niente da cancellare
poni in Tree la radice del
ELSE
sotto albero sinistro.
IF EmptyTree(NodesLeftTree(Candidate)) THEN
LinkParent(Candidate, NodesRightTree(Candidate), Parent, Tree)
ELSE
IF EmptyTree(NodesRightTree(Candidate)) THEN
LinkParent(Candidate, NodesLeftTree(Candidate), Parent, Tree)
ELSE
Se nessuno dei sue sotto
GetNewCandidate(KeyValue, Candidate, Tree); alberi è vuoto allora
KillTNode(Candidate);
chiama
Programmazione Mod. B - Alberi 69
END;
GetNewCandidate
prof. E. Burattini
PROCEDURE LinkParent(OldChild, NewChild, Parent: BSTP; VAR Tree:BSTType);
{collega il nodo genitore con il sottoalbero connesso al nodo da cancellare}
BEGIN
IF Parent=NIL THEN
{sostituiamo la root}
Tree:= NewChild
ELSE
IF OldChild = NodesLeftTree(Parent) THEN
Parent^.Left:=NewChild
{sostituiamo al genitore il figlio sinistro}
ELSE
Parent^.Right:=NewChild
{sostituiamo al genitore il figlio destro}
END;
Old
Parent
New
Old
New
Programmazione Mod. B - Alberi prof. E. Burattini
70
Problema
Realizzare una procedura che elimina il nodo con chiave KeyValue
Ritorna la chiave CandsKey puntata da Candidate
Pseudo Codice
Search(Tree, KeyValue, Candidate, Parent)
GetNodesKey(Candidate, CandsKey)
IF CandsKey <> KeyValue THEN
Done  FALSE
ELSE
riorganizza l’albero dopo aver rimosso Candidate
KillTNode(Candidate)
Done  TRUE
Pseudo Codice
Implica che se cerco di nuovo
un nodo con chiave CandsKey non lo
IF EmptyTree(NodesLeftTree(Candidate))
THEN
trovo e che l’albero
che resta, deallocando il nodo
Candidate,
LinkParent(Candidate,
NodesRightTree(Candidate),
Parent,
Tree) è ancora
un BST
ELSE
IF EmptyTree(NodesRightTree(Candidate)) THEN
LinkParent(Candidate, NodesLeftTree(Candidate), Parent, Tree)
ELSE
Programmazione Mod. B - Alberi 71
continua a riorganizzare
l’albero
prof. E. Burattini
RICAPITOLANDO
Search(Tree, Key, Candidate, Parent)
fornisce il puntatore Candidate del node che ha chiave Key e il puntatore Parent come padre
a
b
Key=b
Candidate=P(b)
Parent=P(a)
LinkParent(Old, New, Parent, Tree)
collega New con Parent eliminando OLD,
se Parent=NIL, cioè Old=Tree è la radice allora mette New al posto di Old e quindi di Tree
Parent
Old
New
Old
New
Programmazione Mod. B - Alberi prof. E. Burattini
72
Pesudo codice di DeleteTNode(Key, Tree, Done)
Search(Tree, Key, Candidate, Parent)
Fornisce il puntatore della Key da eliminare e
quello del suo genitore. Se Candidate=NIL
significa che la Key non c’è.
GetNodesKey(Candidate, CandsKey)
Fornisce la chiave CandsKey di Candidate
IF CandsKey<> Key
Se la chiave trovata e quella di partenza non
corrispondono CandsKey=NIL allora esci
ELSE
Se il sottoalbero sinistro è
vuoto collega il genitore di
candidate con la radice del sotto
albero destro. Se Parent=NIL,
cioè si vuole cancellare la
radice allora poni in Tree la
radice del sotto albero destro.
Se il sottoalbero destro è vuoto
collega il genitore di candidate
con la radice del sotto albero
sinistro. Se Parent=NIL, cioè si
vuole cancellare la radice allora
poni in Tree la radice del sotto
albero sinistro.
Se nessuno dei due sotto
alberi è vuoto allora
chiama
GetNewCandidate
73
Nodo da cancellare
35
30
old
40
5
parent
3
40
5
8
3
80
35
candidate
8
80
35
38
38
Programmazione Mod. B - Alberi prof. E. Burattini
74
Pseudo Codice di GetNewCandidate
OldCandidate  Candidate
Ricerca OldCandidate a partire dal suo
nodo destro con la conseguenza che
trova il più piccolo di questo sottoalbero
(Candidate) (Dummy vale NIL)
Search(NodesRightTree(OldCandidate), KeyValue, Dummy, Candidate)
OldCandidate^.Key  Candidate^.Key
Sostituisci il nodo da cancellare con Candidate
CandsKey := Candidate^.Key;
Riprendi la chiave del nodo spostato
Search(NodesRightTree(OldCandidate), CandsKey, Dummy, Parent)
Cerca il più piccolo nodo del sottoalbero destro del nodo
spostato a partire dalla sua primitiva posizione
IF Parent = NIL THEN
Se il nodo da cancellare è la root e segue immediatamente
il padre allora collega il sottoalbero destro con la root
LinkParent(Candidate,NodesRightTree(Candidate), OldCandidate, Tree)
ELSE
LinkParent(Candidate,NodesRightTree(Candidate), Parent, Tree)
Collega il sottoalbero destro con il padre del nodo spostato
Programmazione Mod. B - Alberi prof. E. Burattini
75
PROCEDURE GetNewCandidate(KeyValue: KItemType; VAR Candidate:BSTP;
VAR Tree:BSTType);
VAR
Dummy,
{variabile ausiliare per la chiamata alla Search}
Parent, OldCandidate :BSTP;
CandsKey: KItemType:
BEGIN
OldCandidate := Candidate
Search(NodesRightTree(OldCandidate), KeyValue, Dummy, Candidate)
OldCandidate^.Info := Candidate^.Info ;
OldCandidate^.Key := Candidate^.Key;
CandsKey := Candidate^.Key;
Search(NodesRightTree(OldCandidate), CandsKey, Dummy, Parent);
IF Parent= NIL THEN
LinkParent(Candidate,NodesRightTree(Candidate), OldCandidate, Tree)
ELSE
LinkParent(Candidate,NodesRightTree(Candidate), Parent, Tree)
END;
Programmazione Mod. B - Alberi prof. E. Burattini
76
Cancellare il nodo 30
DeleteTNode(KeyValue, Tree, Done)
90
50
93
30
34
17
40
Search(Tree, KeyValue, Candidate, Parent)
GetNodesKey(Candidate, CandsKey);
IF CandsKey<> KeyValue THEN Done:=FALSE
ELSE
95
IF EmptyTree(NodesLeftTree(Candidate)) THEN
LinkParent(Candidate, NodesRightTree(Candidate), Parent, Tree)
ELSE
IF EmptyRight(NodesRightTree(Candidate)) THEN
LinkParent(Candidate, NodesLeftTree(Candidate), Parent, Tree)
98
ELSE
GetNewCandidate(KeyValue, Candidate, Tree);
KillTNode(Candidate);
Done:= TRUE
100
13
15
GetNewCandidate(KeyValue, Candidate, Tree);
P30
OldCandidate := Candidate
NIL P34
30
P40
Search(NodesRightTree(OldCandidate),
KeyValue, Dummy, Candidate)
36
47
34
38
35
34
OldCandidate^.Key := Candidate^.Key;
34
CandsKey := Candidate^.Key;
34
P40
P34
P36
Search(NodesRightTree(OldCandidate), CandsKey, Dummy, Parent);
IF Parent = NIL THEN
LinkParent(Candidate,NodesRightTree(Candidate), OldCandidate, Tree)
ELSE
P36
P34
P35
LinkParent(Candidate,NodesRightTree(Candidate),
Parent, Tree)
END;
77
51
45
30
30
60
25
35
55
65
23
27
33
37
53
57
63
67
21 24 26 28 31 34 36 38 51 54 56 58 61 64 66 68
cancella il nodo 45
25
35
23
27
33
37
21 24 26 28 31 34 36 38
60
55
65
53
57
63
67
54 56 58 61 64 66 68
45
51
60
30
25
23
21
24
27
26
55
35
28
33
31
34
37
36
65
53
38
51
57
54
Programmazione Mod. B - Alberi prof. E. Burattini
56
63
58
61
67
64
66
78
68
{cancella nodo}
Program AlberoProva(input,output); write(' cancella il nodo ');
uses Crt, Alberi0;
readln(chiave);
CONST
DeleteTNode(Chiave , Albero,Done);
NKey=-100;
IF DONE=FALSE THEN writeln(' il nodo',
var Albero : BSTP;
Chiave,' non è nell''albero');
Item: KItemType;
WriteAlbero(Albero);
Chiave:KItemType;
readln;
Info:InfoType;
WriteAlbero(Albero);
Done:boolean;
writeln;
writeln(' FINE');
{************** MAIN***********} readln;
begin
end.
clrscr;
writeln('Costruiamo un Albero. ');
BuildNameTree(Albero);
WriteAlbero(Albero);
Info:=33;
writeln(' inserisci il nodo - per finire -100');
readln(chiave);
WHILE Chiave<>NKey DO
BEGIN
AddTNode(Chiave,Info, Albero,Done);
write(' aggiungi il nodo - per finire -100 >>>
readln(chiave);
END;
Programmazione Mod. B - Alberi WriteAlbero(Albero);
prof. E. Burattini
readln;
');
albpr6
79
PROCEDURE StampaAlbero(Tree : BSTP; riga,inizio,fine:integer);
var medio: integer;
1
1
80
BEGIN
if not(emptytree(tree)) then
begin
medio:=(inizio+fine) div 2;
gotoxy(medio,riga);
GetNodesKey(tree,Item);
write(Item);
StampaAlbero(NodesLeftTree(tree),riga+1,inizio,medio);
StampaAlbero(NodesRightTree(tree),riga+1,medio,fine);
END;
END;
PROCEDURE WriteAlbero(Tree:BSTP);
PROCEDURE Wa(Tree:BSTP;I:integer);
VAR
J:integer;
BEGIN
IF NOT EmptyTree(Tree) THEN
BEGIN
Wa(NodesRightTree(Tree),I+1);
FOR J:=1 TO I DO
write(' ');
write(Tree^.Key);
writeln;
Wa(NodesLeftTree(Tree),I+1);
Programmazione
END; Mod. B - Alberi prof. E. Burattini
80
ALGORITMI DI ATTRAVERSAMENTO DI BST
Algoritmi di attraversamento di un albero:
LNR - (LeftNodeRight) Attraversamento inorder
Per ogni nodo
1 - Visita il sottoalbero sinistro
2 - Visita il nodo root
3 - Visita il sottoalbero destro
NLR - (NodeLeftRight) Attraversamento pre-order
Per ogni nodo
1 - Visita il nodo root
2 - Visita il sottoalbero sinistro
3 - Visita il sottoalbero destro
LRN - (LeftRightNode) Attraversamento post-order
Per ogni nodo
1 - Visita il sottoalbero sinistro
2 - Visita il sottoalbero destro
3 - Visita il nodo root
Programmazione Mod. B - Alberi prof. E. Burattini
81
LNR - (LeftNodeRight) Attraversamento ordinato
Per ogni nodo
1 - Visita il sottoalbero sinistro
2 - Visita il nodo
3 - Visita il sottoalbero destro
PROCEDURE ShowTree(NameTree: BSTType);
VAR NodesKey: KItemType;
BEGIN
IF NOT EmptyTree(NameTree) THEN
BEGIN
ShowTree(NodesLeftTree(NameTree));
GetNodesKey(NameTree, Nome);
writeln(Nome)
ShowTree(NodesRightTree(NameTree));
END
END;
PROCEDURE Traverse(Root)
IF root <> NIL THEN
Traverse(Root^.Left)
Visit(Root)
Traverse(Root^.Right)
{visita tutti i nodi del sottoalbero sinistro}
{visita tutti i nodi del sottoalbero destro}
Programmazione Mod. B - Alberi prof. E. Burattini
82
NLR - (NodeLeftRight) Attraversamento pre-ordinato
Per ogni nodo
1 - Visita il nodo root
2 - Visita il sottoalbero sinistro
3 - Visita il sottoalbero destro
PROCEDURE StampaAlbero(Tree : BSTP;
riga,inizio,fine:integer);
var medio: integer;
BEGIN
if not(emptytree(tree)) then
begin
medio:=(inizio+fine) div 2;
gotoxy(medio,riga);
GetNodesKey(tree,Item);
write(Item);
StampaAlbero(NodesLeftTree(tree),riga+1,inizio,medio);
StampaAlbero(NodesRightTree(tree),riga+1,medio,fine);
END
PROCEDURE Traverse(Root)
IF root <> NIL THEN
Visit(Root)
Traverse(Root^.Left)
Traverse(Root^.Right)
{visita tutti i nodi del sottoalbero sinistro}
{visita tutti i nodi del sottoalbero destro}
Programmazione Mod. B - Alberi prof. E. Burattini
83
LRN - (LeftRightNode) - Attraversamento post-ordinato
Per ogni nodo
1 - Visita il sottoalbero sinistro
2 - Visita il sottoalbero destro
3 - Visita il nodo root
PROCEDURE Traverse(Root)
IF root <> NIL THEN
Traverse(Root^.Left)
Traverse(Root^.Right)
Visit(Root)
{visita tutti i nodi del sottoalbero sinistro}
{visita tutti i nodi del sottoalbero destro}
Programmazione Mod. B - Alberi prof. E. Burattini
84
Problema
Eliminare un BST senza lasciare spazzatura.
Soluzione
Attraversa l’albero con un algoritmo LRN (post-order) e cancella ogni nodo incontrato.
E’ utilizzato l’LRN perché la root è sempre l’ultima ad essere deallocata dopo aver deallocato i
nodi figli, e quindi nessun link è eliminato prima del dovuto.
PROCEDURE KillTree(VAR Tree:BSTType);
BEGIN
IF NOT EmptyTree(Tree) THEN
BEGIN
KillTree(NodesLeftTree(Tree);
KillTree(NodesRightTree(Tree);
KillTNode(Tree)
END
END;
Dora
Anna
Maria
Giulio
Sergio
Guido
Riccardo
Roberto
Toni
85
Problema
Espressioni aritmetiche.
/
Notazione infissa
(5*3)/(4-1)
-
*
Visita LNR
inorder
5
4
3
Notazione Polacca Inversa
5 3 *4 1- /
Visita LRN
post-order
PROCEDURE Traverse(Root)
IF root <> NIL THEN
Traverse(Root^.Left)
Visit(Root)
1
Traverse(Root^.Right)
/
PROCEDURE Traverse(Root)
IF root <> NIL THEN
Traverse(Root^.Left
Traverse(Root^.Right)
Visit(Root)
-
*
5
4
3
Notazione Polacca Diretta
/ * 5 3 - 4 1
1
PROCEDURE Traverse(Root)
IF root <> NIL THEN
Visit(Root)
Traverse(Root^.Left)
Traverse(Root^.Right)
/
Visita NLR
pre-order
-
*
5
3
4
Programmazione Mod. B - Alberi prof. E. Burattini
1
86
ESERCIZIO
{ Dato un albero binario calcolare quanti nodi hanno il sottoalbero sinistro nullo.}
Program AlberoConta(input,output);
uses Alberi0;
CONST
{************** MAIN***********}
NKey=-100;
begin
var Albero,Temp : BSTP;
writeln('Costruiamo un Albero. ');
Item: KItemType;
BuildNameTree(Albero);
Chiave:KItemType;
WriteAlbero(Albero);
Info:InfoType;
writeln('Ci sono ', ContaNodiSinNul(Albero),'
Done:boolean;
nodi con sotto albero sinistro nullo');
Cont:integer;
end.
FUNCTION ContaNodiSinNul(Tree:BSTP):integer;
VAR cont1:integer;
BEGIN
IF EmptyTree(Tree) THEN
ContaNodiSinNul:= 0
else
BEGIN
IF NOT EmptyTree(NodesRightTree(Tree)) THEN
ContaNodiSinNul:=ContaNodiSinNul(NodesRightTree(Tree));
IF NOT EmptyTree(NodesLeftTree(Tree)) THEN
ContaNodiSinNul:=ContaNodiSinNul(NodesLeftTree(Tree))
ELSE
ContaNodiSinNul:=ContaNodiSinNul(NodesRightTree(Tree))+1;
END;
END;
Programmazione Mod. B - Alberi prof. E. Burattini
87
ALBCONT2
{ Scrivere un algoritmo che dato un albero binario scriva le chiavi in ordine prima crescente e poi
decrescente }
Program ScriviAlbero (input,output);
uses Alberi0;
CONST
NKey=-100;
{************** MAIN***********}
var Albero : BSTP;
begin
Item, Chiave : KItemType;
writeln('Costruiamo un Albero. ');
Info:InfoType;
BuildNameTree(Albero);
Done:boolean;
WriteAlbero(Albero);
PROCEDURE Crescente(Tree:BSTP);
writeln('crescente ');
BEGIN
Crescente(Albero);
IF Not EmptyTree(Tree) THEN
writeln('decrescente ');
BEGIN
DeCrescente(Albero);
Crescente(NodesLeftTree(Tree));
end.
write(' ',tree^.key);
Crescente(NodesRightTree(Tree));
END;
END;
PROCEDURE DeCrescente(Tree:BSTP);
BEGIN
IF Not EmptyTree(Tree) THEN
BEGIN
DeCrescente(NodesRightTree(Tree));
write(' ',tree^.key);
DeCrescente(NodesLeftTree(Tree));
Programmazione Mod. B - Alberi 88
END;
prof. E. Burattini
END;
ESERCIZI
1- Scrivere una procedura che assegnato un albero binario di interi
positivi non ordinato restituisca un puntatore al valore massimo e
quante volte questo valore massimo è contenuto nell'albero.
ES2GEN04
2- Scrivere una procedura che assegnato un albero binario di interi
positivi non ordinato e due numeri positivi N1 e N2 restituisca la
quantità di numeri pari compresi tra N1 e N2.
ES2FEB04
3- Assegnato un albero non ordinato di interi scrivere una
procedura ricorsiva che trasformi l'albero non ordinato in un
albero BST. Determinare l'altezza dell'albero non ordinato e
dell'albero BST.
ESN0N0R2
Programmazione Mod. B - Alberi prof. E. Burattini
89
PROGRAM DispariNulli(input,output);
{ Assegnato un albero BST di numeri interi, fornire una procedura ricorsiva che dica quanti
nodi, la cui chiave è un numero dispari, hanno sottoalbero destro nullo..}
{************** MAIN***********}
BEGIN
writeln('Costruiamo un Albero. ');
uses Alberi0;
BuildNameTree(Albero);
CONST
WriteAlbero(Albero);
NKey=-100;
cont:=0;
VAR
ContaNodiNul(Albero,Cont);
Albero: BSTP;
writeln(' Ci sono ',cont,' nodi con sotto albero
Cont:integer;
destro nullo e padre
dispari');
END.
PROCEDURE ContaNodiNul(Tree:BSTP; VAR Conta:integer);
BEGIN
IF NOT EmptyTree(Tree) THEN
BEGIN
ContaNodiNul(NodesLeftTree(Tree),Conta);
ContaNodiNul(NodesRightTree(Tree),Conta);
IF (Tree^.Right=NIL) AND (Tree^.key MOD 2 <>0) THEN Conta:=Conta+1;
Programmazione Mod. B - Alberi 90
END;
prof. E. Burattini
END;
ALBERO BILANCIATO CON M LIVELLI
N°
NODI
N°
NODI
20
0
20
21
1
21
M
2M
2 M 1
1
M 1
1 2
i 0
M
i
Totale Nodi
Programmazione Mod. B - Alberi prof. E. Burattini
Totale Nodi
i
2

i 0
91
ESERCIZIO
{ Dato un albero binario non bilanciato costruire un albero
bilanciato.}
Controllo bilanciamento
Non bilanciato
bilanciato
Da Albero a Vettore
Bilanciamento
Stampa
Programmazione Mod. B - Alberi prof. E. Burattini
92
1
2
Controllo bilanciamento
3
5
Non bilanciato
7
8
Da Albero a Vettore
1
2
3
5
7
8
9
9
bilanciato
5
Bilanciamento
8
2
1
3
7
9
Stampa
Programmazione Mod. B - Alberi prof. E. Burattini
1235789
93
FUNCTION UnisciAlberi(e:KItemType;a,b:BSTP) : BSTP;
{crea un albero con chiave ‘e’ e sottoalbero sinistro ‘a’ e destro ‘b’
eventualmente anche vuoti }
VAR c:BSTP;
BEGIN
new(c);
c^.left:=a;
c^.right:=b;
c^.key:=e;
UnisciAlberi:=c;
END;
e
a
x
b
y
Programmazione Mod. B - Alberi prof. E. Burattini
z
w
94
{************** MAIN***********}
Program Bilanciare(input,output); BEGIN
uses Alberi0;
writeln('Costruiamo un Albero. ');
CONST
BuildNameTree(Albero);
NKey=-100;
IF not ControlloBilanciamento(Albero) THEN
TYPE
BEGIN
Vettore=ARRAY[1..40] OF integer;
Vmax:=0;
var Albero,Bilanciato : BSTP;
DaAlberoAVettore(Albero,V,Vmax);
Item: KItemType;
Bilanciato:=Vet2ALb(V,1,Vmax);
Chiave:KItemType;
writeln(ControlloBilanciamento(Bilanciato));
Info:InfoType;
END
Done:boolean;
ELSE
V:vettore;
writeln(' FINE');
I,Vmax:integer;
END.
FUNCTION vet2alb(vx:vettore;i,j:integer):BSTP;
{a partire dal vettore V ordinato genero l'albero vet2alb}
PROCEDURE DaAlberoAVettore(A:BSTP;VAR V:vettore;VAR max:integer);
{Dato un albero BST costruisce un vettore ordinato}
FUNCTION Bilancia(A:BSTP):integer;
{Dato un albero controlla se è bilanciato, quasi-bilanciato o non bilancitao}
PROCEDURE ControllaBilanciamento(A:BSTP);
Programmazione Mod. B - Alberi prof. E. Burattini
95
FUNCTION Bilancia(A:BSTP;VAR cmax,cmin:integer;livello:integer):integer;
BEGIN
IF not EmptyTree(A) THEN
BEGIN
IF EmptyTree(NodesRightTree(A)) OR EmptyTree(NodesLeftTree(A)) THEN
BEGIN
IF cmax<livello THEN
cmax:=livello;
IF cmin>livello THEN
cmin:=livello;
END;
bilancia:=bilancia(NodesRightTree(A),cmax,cmin,livello+1);
bilancia:=bilancia(NodesleftTree(A),cmax,cmin,livello+1);
END;
Bilancia:=cmax-cmin
END;
FUNCTION ControlloBilanciamento(A:BSTP):boolean;
VAR cmx,cmn:integer;
BEGIN
cmx:=0;cmn:=maxint;
IF Bilancia(A,cmx,cmn,0)=0 Then BEGIN
ControlloBilanciamento:=TRUE;writeln(' L''albero è bilanciato')
END
ELSE
IF Bilancia(A,cmx,cmn,0)=1 Then BEGIN
ControlloBilanciamento :=TRUE;writeln(' L''albero è quasi bilanciato')
END
ELSE
BEGIN
Programmazione Mod. B - Alberi
96
ControlloBilanciamento:=FALSE;writeln('
L''albero
non è bilanciato');
prof. E. Burattini
END;
PROCEDURE DaAlberoAVettore(A:BSTP;VAR V:vettore;VAR max:integer);
VAR I:integer;
BEGIN
IF NOT EmptyTree(A) THEN
BEGIN
DaAlberoAVettore(NodesLeftTree(A),V,max);
Max:=max+1;
V[max]:=Tree^.key;
DaAlberoAVettore(NodesRightTree(A),V,max);
END;
END;
{************** MAIN***********}
begin
writeln('Costruiamo un Albero. ');
BuildNameTree(Albero);
WriteAlbero(Albero);
ControllaBilanciamento(Albero);
Vmax:=0;
DaAlberoAVettore(Albero,V,Vmax);
Bilanciato:=Vet2ALb(V,1,Vmax);
ControllaBilanciamento(Bilanciato);
writeln;
writeln(' FINE');
Programmazione Mod. B - Alberi readln;
97
prof. E. Burattini
end.
{************** MAIN***********}
FUNCTION vet2alb(vx:vettore;i,j:integer):BSTP;
begin
{a partire dal vettore V ordinato genero l'albero vet2alb}
writeln('Costruiamo un Albero. ');
VAR
BuildNameTree(Albero);
K:integer;
WriteAlbero(Albero);
BEGIN
ControllaBilanciamento(Albero);
IF I>J THEN
Vmax:=0;
Vet2alb:=NIL
DaAlberoAVettore(Albero,V,Vmax);
ELSE
Bilanciato:=Vet2ALb(V,1,Vmax);
IF I=J THEN
ControllaBilanciamento(Bilanciato);
Vet2alb:=UnisciAlberi(Vx[I],NIL,NIL)
writeln(' FINE');
ELSE
end.
BEGIN
K:=(I+J) DIV 2;
Vet2alb:=UnisciAlberi(Vx[K],vet2alb(Vx,I,K-1),vet2alb(vx,K+1,j))
END;
END;
FUNCTION UnisciAlberi(e:KItemType;a,b:BSTP) : BSTP;
{crea un albero con chiave ‘e’ e sottoalbero sinistro ‘a’ e destro ‘b’
eventualmente anche vuoti }
VAR c:BSTP;
BEGIN
new(c);
c^.left:=a;
c^.right:=b;
c^.key:=e;
Programmazione Mod. B - Alberi UnisciAlberi:=c;
prof. E. Burattini
END;
ALBBIL3
98
Vet2ALb(V,1,Vmax);
UnisciAlberi(Vx[K],vet2alb(Vx,I,K-1),vet2alb(vx,K+1,j))
a
b
c
d
e
f
g
1
2
3
4
5
6
7
d
UnisciAlberi(Vx[4],vet2alb(Vx,1,3),vet2alb(vx, 5,7))
d
Vet2ALb(V,1,7);
K=4
Vet2ALb(V,1,3);
K=2
b
a
f
c
e
g
f
Vet2ALb(V,5,7);
K=6
UnisciAlberi(Vx[2],vet2alb(Vx,1,1),vet2alb(vx, 3,3))
a
Vet2ALb(V,1,1);
K=1
b
c
Vet2ALb(V,3,3);
K=3
UnisciAlberi(Vx[4],vet2alb(Vx,1,3),vet2alb(vx, 6,7))
e
Vet2ALb(V,5,5);
K=5
Programmazione Mod. B - Alberi prof. E. Burattini
g
Vet2ALb(V,7,7);
K=7
99
ESERCIZIO
LA FAMIGLIA
{calcola le parentele }
Descritte le parentele secondo un albero non ordinato scrivere le funzioni
FUNCTION Padre
{dato un nome determinare se ha un padre e chi è}
PROCEDURE Figlio
{dato un nome determinare se ha uno o due figli e chi sono}
FUNCTION Nonno
{dato un nome determinare chi è il nonno}
FUNCTION Fratello
{dato un nome determinare se ha un fratello e chi è}
FUNCTION Zio
{dato un nome determinare se ha uno zio e chi è}
END;
Programmazione Mod. B - Alberi prof. E. Burattini
100
Esercizio
.
Dato un albero determinare quanti nonni hanno un solo nipote.
Programmazione Mod. B - Alberi prof. E. Burattini
101
Programmazione Mod. B - Alberi prof. E. Burattini
102