ESERCIZIO Scrivere una procedura o funzione che assegnato un albero binario di interi calcoli la sua...
-
Upload
floriano-cecchini -
Category
Documents
-
view
214 -
download
1
Transcript of ESERCIZIO Scrivere una procedura o funzione che assegnato un albero binario di interi calcoli la sua...
ESERCIZIOScrivere una procedura o funzione che assegnato un albero binario di interi
calcoli la sua altezza e assegnato un livello Lev conti il numero num di tutti i nodi presenti in quel livello e il numero di foglie.
Nodi=14
19
13 21
12 15
14 17
16 18
20 24
23 26
22
lev
lev
H=4
Lev=3Nodi=4
Nodi Lev=314, 17, 23, 26
N. Foglie=7
int contanodi(Tnodo A) {// CONTA I NODI DI UN ALBERO A if (A==NULL) return 0; else return contanodi(A->left)+contanodi(A->right)+1;}
int Altezza(Tnodo A) {// CALCOLA L’ALTEZZA DI UN ALBERO A int Hs=0, Hd=0; if (A==NULL) return -1; else { Hs=Altezza(A->left); Hd=Altezza(A->right); if (Hs > Hd) return Hs=1+Hs; else return Hd=1+Hd; }}
void ContaL(Tnodo A, int n, int& conta) {//CONTA i NODI DI LIVELLO n if (A!=NULL) if (n==0) conta++; else { ContaL(A->left,n-1,conta); ContaL(A->right,n-1,conta); } }
void StampaLivello(Tnodo A, int n) {// SI RICHIAMA CON n=livello scelto if (A!=NULL) if (n==0) cout<<A->key<<" "; else { StampaLivello(A->left,n-1); StampaLivello(A->right,n-1); }}
Tnodo estremaSinistra(Tnodo A) { if (A->left==NULL) return A; else return estremaSinistra(A->left) ;}
Tnodo estremaDestra(Tnodo A) { if (A->right ==NULL) return A; else return estremaDestra(A->right) ;}
alberiGenerale0_2
19
13 21
12 15
14 17
16 18
20 24
23 26
22
lev
lev
CANCELLAZIONE DI UN NODO DI UN ALBERO
La cancellazione di un nodo di un albero presuppone che
una volta avvenuta venga mantenuta l’integrità dell’albero
e che nel caso si tratti di un BST si salvaguardata anche
la relazione tra i vari nodi.
Cancellazione in un albero non ordinato
Nel caso degli alberi non ordinati è necessario preoccuparsi solo di mantenere l’integrità dell’albero non essendoci relazioni d’ordine tra i vari nodi.
E’ pertanto sufficiente scorrere l’albero per trovare il nodo da cancellare, conoscendo ad esempio la chiave. Se viene trovato, è sufficiente ricercare una foglia dell’albero, non importa quale, sostituire la chiave della foglia a quella da cancellare e quindi eliminare la foglia.
Nel lucido seguente è mostrato un esempio.
30
35
3
44
35
8
38
28
Nel caso dell’albero di figura si vuole cancellare il nodo con chiave 30. Poichè la chiave esiste è allora sufficiente cercare una foglia, ad esempio quella con chiave 28, sostituire questa chiave a quella da cancellare e eliminare la foglia.
10
3
50 35
3
44
35
8
38
28
10
3
50
Cancellazione in un albero ordinato BST
Nel caso degli alberi ordinati è necessario preoccuparsi non
solo di mantenere l’integrità dell’albero ma anche la
relazione d’ordine esistente tra i vari nodi.
Vanno distinti tre casi:
•Il nodo da cancellare è una foglia
•Il nodo da cancellare ha un solo figlio
•Il nodo da cancellare ha sia un sotto albero destro che un
sotto albero sinistro.
Nella figura seguente si mostrano i primi due casi che sono di semplice soluzione.
Infatti se il nodo è una foglia è sufficiente eliminarla ponendo a NULL il puntatore del parent (padre) che la riguardava. Si vedano gli esempi (a) e (b).
Nel caso in cui il nodo da cancellare ha un solo sottoalbero, è allora sufficiente legare la radice del sotto albero a cui punta il nodo da cancellare, con il parent che punta al nodo. In questa maniera, ovviamente si preserva l’ordine. Si vedano gli esempi (c) e (d).
ELIMINAZIONE DI UN NODO SU UN BST
New
Old
Parent
Old
New
Parent
Old
Parent
Old
(a)
(d)
(b)
(c)
Nel caso in cui il nodo da cancellare abbia sia il sotto albero
di sinistra che quello di destra allora si procede come segue:
si sostituisce alla chiave del nodo da cancellare o la chiave
del nodo di valore maggiore del suo sottoalbero di sinistra o
quella di valore minore del suo sotto albero di destra.
Se questo nodo ha a sua volta un sottoalbero di destra o 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.
Nell’esempio di figura si sostituisce alla chiave 30 del nodo individuato, la chiave del nodo 35 che è la più piccola del suo sottoalbero destro.
Nodo da cancellare
30
5
3
40
35
80
38
8
35
5
3
40
35
80
38
8
15
Analizziamo il problema della riorganizzazione dell’albero una volta eliminato un nodo.
Caso a- il nodo (QQQ) da eliminare ha il sotto albero sinistro vuoto. Nell’esempio si usa la stessa nomenclatura che verrà utilizzata in seguito nel codice.
QQQ
RRR
Parent
Candidate
left right
Il puntatore che da Parent prima puntava a Candidate ora acquista il valore del puntatore a RRR ottenuto in questo caso da Candidate->right
16
Analizziamo il problema della riorganizzazione dell’albero una volta eliminato un nodo.
Caso a- il nodo (QQQ) da eliminare ha il sotto albero sinistro vuoto.
QQQ
RRR
Parent
Candidate
left right
Caso b- il nodo da eliminare ha il sotto albero sistro vuoto.La procedura è analoga alla precedente.
Eliminare Dora
Maria
Giulio Sergio
Dora Guido ToniRoberto
Elena
Maria
Giulio Sergio
Guido ToniRoberto
Elena
Pseudo Codice
if (Candidate->left==NULL)LegaPadre(Candidate, Candidate ->right, Padre, Tree)
elseif (Candidate->right==NULL)) LegaPadre(Candidate, Candidate ->left, Padre, Tree) else continua a riorganizzare l’albero
void LegaPadre(Tnodo OldChild, Tnodo NewChild, Tnodo Padre, Tnodo &Tree){riorganizza l’albero BST dopo l’eliminazione di un nodo}
QQQ
RRR
Padre
Candidate
left right
void LegaPadre(Tnodo OldChild, Tnodo NewChild, Tnodo Padre, Tnodo &Tree)//collega il nodo genitore con il sottoalbero connesso al nodo da cancellare{ if (Padre==NULL) // {sostituiamo la root} Tree= NewChild; else if (OldChild ==Padre->left) Padre->left=NewChild; // {sostituiamo al genitore il figlio sinistro} else Padre->right=NewChild; // {sostituiamo al genitore il figlio destro}}
New
Old
Parent
Old
New
Riassunto dei tipi di cancellazione
New
Old
Parent
Old
New
void DelTNode(int KeyValue, Tnodo &Tree, bool &Done) {elimina il nodo con chiave KeyValue ricostruendo la struttura BST. Se il Nodo non esiste Done risulta False}
30
5
3
40
35
80
38
8
35
5
3
40
3580
38
8
20
Pesudo codice di DelTNode(Key, Tree, Done)
Cerca(Tree, Key, Candidato, Parent) Fornisce il puntatore della Key da eliminare e quello del suo genitore. Se Candidato=NULL significa che la Key non c’è.
DammiChiave(Candidato, CandsKey) Fornisce la chiave CandsKey di Candidato
if CandsKey<> Key Se la chiave trovata e quella di partenza non corrispondono CandsKey=NULL allora esci
else
Se il sottoalbero sinistro è vuoto collega il genitore di Candidato con la radice del sotto albero destro. Se Parent=NULL, cioè si vuole cancellare la radice allora poni in Tree la radice del sotto albero destro.
Se nessuno dei due sotto alberi è vuoto allora chiama NuovoCandidato
Se il sottoalbero destro è vuoto collega il genitore di Candidato con la radice del sotto albero sinistro. Se Parent=NULL, cioè si vuole cancellare la radice allora poni in Tree la radice del sotto albero sinistro.
Se il sottoalbero destro è vuoto collega il genitore di candidato con la radice del sotto albero sinistro. Se Padre=NULL, 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 NuovoCandidato
Non c’è niente da cancellare
void DelTNode(int KeyValue, Tnodo &Tree, bool &Done){ Tnodo Candidato; // puntatore al nodo candidato per la cancellatura Tnodo Padre; // puntatore al genitore del nodo candidato} int CandsKey; Done=true; Cerca( Tree, KeyValue, Candidato, Padre); DammiChiave(Candidato, CandsKey); if (CandsKey!=KeyValue) Done=false; else if (Candidato->left==NULL) LegaPadre(Candidato, Candidato->right, Padre, Tree); else if (Candidato->right==NULL) { LegaPadre(Candidato, Candidato->left, Padre, Tree);
} else NuovoCandidato(KeyValue, Candidato, Tree); KillTNode(Candidato);}
Se il sottoalbero sinistro è vuoto collega il genitore di candidato con la radice del sotto albero destro. Se Padre =NULL, cioè si vuole cancellare la radice allora poni in Tree la radice del sotto albero destro.
void NuovoCandidato(int KeyValue, Tnodo &Candidato, Tnodo &Tree){ Tnodo Dummy; //variabile ausiliare per la chiamata a Cerca
Tnodo Padre; Tnodo OldCandidato;int CandsKey;
OldCandidato= Candidato;
Cerca(OldCandidate->right, KeyValue, Dummy, Candidato)
OldCandidato->key= Candidato->key;
DammiChiave(Candidato, CandsKey);
Cerca(OldCandidate->right, CandsKey, Dummy, Padre)
if (Padre==NULL) LegaPadre(Candidato, Candidato->right, OldCandidato, Tree);else LegaPadre(Candidato, Candidato->right, Padre, Tree);}
Ricerca OldCandidate a partire dal suo nodo destro con la conseguenza che trova il più piccolo di questo sottoalbero (Candidato) (Dummy vale NULL)
Sostituisci il nodo da cancellare con Candidate
Riprendi la chiave del nodo spostato
Cerca il più piccolo nodo del sottoalbero destro del nodo spostato a partire dalla sua primitiva posizione
Collega il sottoalbero destro con il padre del nodo spostato
Se il nodo da cancellare è la root allora collega il sottoalbero destro con la root
CercaCerca(Tree, KeyValue, TNode, Padre)Obiettivo: cercare un cammino verso un determinato nodo dell’albero.Se il nodo non esiste ritorna NULL. Se esiste ritorna il puntatore al nodo individuato e quello di suo padre.
Pseudo Codice
Padre NULL {la root non ha genitori}
TNode Tree {la radice è il primo nodo esaminato}
DammiChiave(TNode, NodesKey) {estrai la chiave del nodo in esame}
while ci sono altri nodi da esaminare AND non si è ancora trovato il nodo {
Padre TNode
Tnode il sottoalbero legato al KeyValue
DammiChiave(TNode, NodesKey) {estrai la chiave del nodo in esame}
Tnode!=NULL NodesKey <> KeyValue
if (NodesKey > KeyValue) TNode radice del sottoalbero sinistroelse TNode radice del sottoalbero destro
Il padre dell’ultimo nodo esaminatodurante la ricerca di KeyValue
void Cerca(Tnodo Tree, int KeyValue, Tnodo &Node, Tnodo &Padre){ int NodesKey; Padre=NULL; Node=Tree; DammiChiave(Node, NodesKey) ; while ((Node!=NULL) && (NodesKey!=KeyValue)) { Padre=Node; if (NodesKey>KeyValue) Node=Node->left; else Node=Node->right; DammiChiave(Node, NodesKey); }};
Ricordarsi che DammiChiave nel caso trovi NULL ritorna una chiave nulla.
void DammiChiave(Tnodo TNode, int &TheKey){ //ritorna il key field del nodo puntato da Tnode, se Tnode è // NULL allora ritorna il valore di -100
if (TNode != NULL ) TheKey= TNode ->key;else TheKey= -100;
}
DelTNode(K,T,d)
Cancella il nodo K dell’albero T
Cerca(T,K,N,P)
Cerca in T il nodo K. Il suo puntatore è N e P è suo padre
DammiChiave(K,N)
Verifica che a N corrisponde la chiave K
La chiave non cè: ESCI
N->left=NULL N->right=NULL
LegaPadre(N,N->right,P,T)
Collega il padre P con N->right e cancella N
Collega il padre P con N->left e cancella N
LegaPadre(N,N->left,P,T)
NuovoCandidato(K,N,T)
NuovoCandidato(K,N,T)
Cerca(N->right, K, D, U)
DammiChiave(Uk,U)
Cerca(N->right, Uk, D, P)
P=NULL PNULL
LegaPadre(U,U->right,N,T)
LegaPadre(U,U->left,N,T)
Cerco il più piccolo a destra. Parto a destra di K cerco K e così ottengo il più piccolo, U
A partire dal sotto albero destro di N, cerco Uk per avere suo padre P
RICAPITOLANDO
26
Pesudo codice di DeleteTNode(Key, Tree, Done)
Cerca(Tree, Key, Candidato, Parent) Fornisce il puntatore della Key da eliminare e quello del suo genitore. Se Candidato=NULL significa che la Key non c’è.
DammiChiave(Candidato, CandsKey) Fornisce la chiave CandsKey di Candidato
if CandsKey<> Key Se la chiave trovata e quella di partenza non corrispondono CandsKey=NULL allora esci
else
Se il sottoalbero sinistro è vuoto collega il genitore di Candidato con la radice del sotto albero destro. Se Parent=NULL, cioè si vuole cancellare la radice allora poni in Tree la radice del sotto albero destro.
Se nessuno dei due sotto alberi è vuoto allora chiama NuovoCandidato
Se il sottoalbero destro è vuoto collega il genitore di Candidato con la radice del sotto albero sinistro. Se Parent=NULL, cioè si vuole cancellare la radice allora poni in Tree la radice del sotto albero sinistro.
RICAPITOLANDO
RICAPITOLANDO
Cerca(Tnodo Tree, int KeyValue, Tnodo &Node, Tnodo &Padre)fornisce il puntatore Candidato del node che ha chiave Key e il puntatore Padre come padre
a
b
KeyValue=bNode=P(b)Padre =P(a)
LegaPadre(Tnodo OldChild, Tnodo NewChild, Tnodo Padre, Tnodo &Tree)collega NewChild con Parent eliminando OldChild,se Padre =NULL, cioè Old=Tree è la radice allora mette NewChild al posto di OldChild e quindi di Tree
Padre
NewChild
OldChild
OldChildNewChild
RICAPITOLANDO
NuovoCandidato(int KeyValue, Tnodo &Candidato, Tnodo &Tree)
Cerca nel sottoalbero destro di OldCandidato il nodo con chiave minima. Questa chiave va a sostituire quella del nodo OldCandidato. Inoltre se il nodo con chiave minima ha sotto alberi allora opera come precedentemente visto.
35
5
3
40
3580
38
8
OldCandidato
Candidato
void NuovoCandidato(int KeyValue, Tnodo &Candidato, Tnodo &Tree){ Tnodo Dummy; //variabile ausiliare per la chiamata a Cerca Tnodo Padre; Tnodo OldCandidato; int CandsKey;OldCandidato= Candidato;Cerca(OldCandidate->right, KeyValue, Dummy, Candidato)OldCandidato->key= Candidato->key;DammiChiave(Candidato, CandsKey);Cerca(OldCandidate->right, CandsKey, Dummy, Padre)if (Padre==NULL) LegaPadre(Candidato, Candidato->right, OldCandidato, Tree);else LegaPadre(Candidato, Candidato->right, Padre, Tree);}
29
90
50 95
30
34
40
3615
93 98
10017
13
35
47
Cerca(Tree, KeyValue, Candidate, Parent)
DammiChiave(Candidate, CandsKey);
if CandsKey<> KeyValue Done=FALSE
else
if (Candidate->left==NULL) LegaPadre(Candidate, Candidate-> Right, Parent, Tree) else if (Candidate->right==NULL)) LegaPadre(Candidate, Candidate-> Left, Parent, Tree) else NuovoCandidato(KeyValue, Candidate, Tree);KillTNode(Candidate);
Cancellare il nodo 30
OldCandidate = Candidate
Cerca( OldCandidate->right), KeyValue, Dummy, Candidate)
OldCandidate->Key = Candidate^.Key;
CandsKey = Candidate->Key;
Cerca(OldCandidate->right, CandsKey, Dummy, Parent);
if Parent = NULL THEN
LegaPadre(Candidate, Candidate ->right, OldCandidate, Tree)
else
LegaPadre(Candidate, Candidate ->right, Parent, Tree);
P30
P4030 NULL P34
34
34
P40 34 P34 P363834
P34 P35 P36
NuovoCandidato(KeyValue, Candidate, Tree)
DelTNode(KeyValue, Tree, Done)
alberiGenerale0_4
500
400600
700
800
420
410
454 456
900
430
Cancella un nodo
440
470
455 475
460
450 480
500
400600
700
800
420
410
454 456
900
430
450
470
455 475
460
480
500
400 600
550
564
558
553
556
555 557
566
559
550
400 600
553
564
556
558
555557
566
559
Cancella la root
ESERCIZIO
Sia assegnato un albero binario, scrivere un algoritmo tale che sposti ogni figlio sinistro nel corrispondente figlio destro e viceversa.
A
B C
D E F
G H
A
C B
DF E
H G
PROVE INTERCORSO 2010-2011B1
Scrivere una funzione ricorsiva che verifichi che la somma degli elementi delle singole righe di una matrice M(NxN) sono uguali ai primi N elementi generati dalla successione partendo da a5:a1 =2, a2=1, a3=-1, a4=3 - an = an-1 -3* an-2 + an-3- an-4
EsempioSia N=4 ; Successione= 2, 1, -1, 3, -5, 12, -27, 57, -125, 275, -598, 1305,
bool verificaMat(int A[][Nmax],int N,int i, int j, int a1,int a2,int a3, int a4){ int an=0,somma=0;if (i>N-1) return true; else an=a1 -3* a2 + a3- a4 ;if (sommaRighe(A,N,i,0,a1,somma)==false) return false; else return verificaMat(A,N, i+1,0, a2, a3, a4,an);}
PRECONDIZIONIa1 =2; a2=1; a3=-1; a4=3;i=0,j=0;
an
B2Data una matrice M(NxN) e un vettore A[N] scrivere una procedura ricorsiva che calcoli il vettore B[N] tale che
iAjiMiBNj
j*
1
0
Esempio:3 1 2 0 1 10
M= 4 -7 -10 4 A= 3 B= -37
5 2 0 -5 2 11
1 13 10 -7 0 -18
void ricB2(int M[][Nmax],int A[],int B[], int i, int j, int N ){ if (i>N-1) return; else if (j>N-1) ricB2(M,A,B,i+1,0,N); else { //B[i]=M[i][j]*A[i]+B[i]; B[i]=M[i][j]*A[j]+B[i]; ricB2(M,A,B,i,j+1,N); }}
PRECONDIZIONIi=0,j=0;
B31- Data una matrice di caratteri M(NxN) contare, utilizzando solo funzioni ricorsive, quante delle sue righe sono palindrome.Esempio
q e r w e s
t r e e r t
s d f f d s
d a w s re f
f g h h g f
r e w e r t
Risposta Numero righe palindrome=3
int ricB3(char A[][Nmax], int i, int j, int N){ if (i>N-1) return 0; else if (j<=N/2-1) {if (A[i][j]!=A[i][N-1-j]) return ricB3(A,i+1,0,N); else return ricB3(A,i,j+1,N);} else { return ricB3(A,i+1,0,N)+1;}}
PRECONDIZIONIi=0,j=0;
B4Scrivere una funzione ricorsiva che verifichi che la somma degli elementi delle colonne di una matrice M(NxN) sono uguali ai primi N elementi, a partire dal quinto, generati dalla successione:a1 =2, a2=1, a3=-1, a4=3
an = an-1 -3* an-2 + an-3- an-4
EsempioSia N=4; Successione= 2, 1, -1, 3, -5,12,-27,57,-125,275,-598,1305
-1 4 0 -5 20 0 2 -2
3 6 -10 3 24 57 1 2
-1 -10 3 -15 -6 -10 6 0
-6 12 -26 -7 -121 1 -215 5
121 -6 -5 5 -36 125 22 2
-129 2 3 41 -2 -3 -429 1
4 12 4 0 1 100 8 1300
-3 -10 1 25 15 -49 -70 67
bool verificaMat(int A[][Nmax],int N,int i, int j,int a1,int a2,int a3, int a4)
{ int an=0,somma=0; if (j>N-1) return true; else an=a1 -3* a2 + a3- a4 ; if (sommaColonne(A,N,i,j,an,somma)==false) return false; else return verificaMat(A,N, 0, j+1, a2, a3, a4, an);}
PRECONDIZIONIa1 =2; a2=1; a3=-1; a4=3;i=0,j=0;
int main(){ int item, pos, som; string nome; Pnodo L1,L2, TL1,TL2,TL; cout<<" LISTA DI PARTENZA L1 \n"<<endl; nome="LA1.txt"; costruisciLista(L1,nome); stampaLista(L1); TL1=L1; cout<<"\n LISTA DI PARTENZA L2 \n"<<endl; nome="LA2b.txt"; costruisciLista(L2,nome); TL2=L2; stampaLista(L2); TL=A1Lis(TL1,L1,L2,TL2); cout<<"\n\n LISTA NUOVA L1 \n"<<endl; stampaLista(TL);cout<<endl;system("pause");}
A1Date due liste di caratteri L1 e L2 verificare se una delle due liste è sottolista dell'altra. Se questo accade, ad esempio L2 sottolista di L1, eliminare questa sottolista da quella in cui è stata trovata, cioè L2 da L1.EsempioL1=p-> r->o->t->o->t->i->p->a->l->eL2= t->o->t->iL1= p->r->o->p->a->l->e
Pnodo A1Lis(Pnodo TL1,Pnodo L1,Pnodo L2, Pnodo TL2){ Pnodo precL1=NULL;Pnodo temp, currL1=NULL; while (L1->next!=NULL) { L2=TL2; currL1=L1; while ((currL1->next!=NULL)&&(L2->next!=NULL)&&(currL1->info==L2->info)) { currL1=currL1->next; L2=L2->next; } if (currL1->next==NULL) {cout<<"\n\n L2 non e' sotto stringa di L1 \n"; return TL1;} if (L2->next==NULL) { cancella(L1,currL1->next,TL1,precL1); return TL1; } else { precL1=L1; L1=L1->next; } }}
void cancella(Pnodo L1, Pnodo currL1, Pnodo &TL1, Pnodo precL1){ Pnodo temp; if (precL1==NULL) TL1=currL1; else precL1->next=currL1;
while (L1->next!=currL1->next) { temp=L1; L1=L1->next; delete temp; }}