1. Definizione di Albero



Scaricare 142.5 Kb.
Pagina9/11
21.12.2019
Dimensione del file142.5 Kb.
1   2   3   4   5   6   7   8   9   10   11
Figura 2 - Esempio della Procedura di Cancellazione
In accordo a quanto detto, la funzione di cancellazione risulta:

void Delete(abr *p, tipobaseABR x)

{

abr tmp;


if (!EmptyABR(*p)) {

if (!Confronta((*p)->info,x)) {

tmp=*p;

if (EmptyABR((*p)->leftchild)) {

*p=(*p)->rightchild;

free (tmp);

} else if (EmptyABR((*p)->rightchild)) {

*p=(*p)->leftchild;

free (tmp);

} else {


*p=DelMin(&(*p)->rightchild);

(*p)->leftchild=tmp->leftchild;

(*p)->rightchild=tmp->rightchild;

free (tmp);

}

} else if (Confronta((*p)->info,x)>0) Delete(&(*p)->leftchild,x);



else Delete(&(*p)->rightchild,x);

}

}


dove la funzione DelMin restituisce il puntatore al nodo più piccolo del sottoalbero di destra:
abr DelMin(abr *p)

{

abr pmin;



if ((*p)->leftchild==ALBEROVUOTO) {

pmin=*p;


*p=(*p)->rightchild;

return(pmin);

} else return(DelMin(&(*p)->leftchild));

}
Infatti, l’elemento più piccolo del sottoalbero di destra è quello posto più a sinistra che non possiede alcuno figlio sinistro.



4.Operazioni Non Primitive sulla Struttura Dati Astratta ABR




4.1.Algoritmi di Visita


Alcune tra le procedure ricorsive più utilizzate per gli alberi binari di ricerca sono le visite. Esse possono essere in preordine, in ordine e in postordine. Le differenze risiedono nelle modalità con cui le chiamate ricorsive si susseguono.
Visita di un Albero in Preordine

La visita in preordine di un generico albero T, consiste nel compiere una determinata azione di accesso al contenuto informativo della radice dell'albero T, e poi applicare ricorsivamentre la procedura ai due sottoalberi aventi come radice i figli della radice, partendo dal sottoalbero a sinistra e procedendo con quello a destra. L'azione di accesso al contenuto informativo di ciascun nodo dipende ovviamente dal singolo problema. Nel seguito, per semplicità, si supporrà che l'operazione di accesso al contenuto informativo è quella relativa alla sua visualizzazione sullo schermo; supponendo che il tipobaseABR sia un float, l’accesso all’informazione contenuta in ogni nodo dell’ABR sarà:


void VisualizzaElemento(tipobaseABR x)

{

printf("\n%f ", x);



}

void preordine(abr n)

{

if (!EmptyABR(n)) {



VisualizzaElemento(Label(n));

preordine(LeftChild(n));

preordine(RightChild(n));

}

}


Visita di un Albero in Ordine

La visita in ordine di un generico albero T, consiste nell'applicare la visita ricorsivamente al sottoalbero di sinistra della radice di T, poi nel visitare la radice di T e poi nell'applicare ricorsivamentre la procedura al sottoalbero di destra. La procedura è:

void inordine(abr n)

{

if (!EmptyABR(n)) {



inordine(LeftChild(n));

VisualizzaElemento (Label(n));

inordine(RightChild(n));

}

}


Visita di un Albero in Postordine

La visita in postordine di un generico albero T, consiste nell'applicare ricorsivamente la procedura ai sottoalberi aventi come radice i due figli della radice (procedendo da quello a sinistra verso quello a destra) e poi nell'applicare la visita alla radice dell'albero T. La procedura è:


void postordine(abr n)

{

if (!EmptyABR(n)) {



postordine(LeftChild(n));

postordine(RightChild(n));

VisualizzaElemento(Label(n));

}

}






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


©astratto.info 2019
invia messaggio

    Pagina principale