1. Definizione di Albero



Scaricare 142.5 Kb.
Pagina10/11
21.12.2019
Dimensione del file142.5 Kb.
1   2   3   4   5   6   7   8   9   10   11

4.2.Altezza di un Nodo


La seguente funzione determina l’altezza di un ABR la cui radice è individuata dal puntatore rappresentato dalla variabile n di tipo abr.
unsigned int altezza(abr n)

{

unsigned int a=0,h;



abr tmp;
tmp=LeftChild(n);

if (!EmptyABR(tmp)) {

h=altezza(tmp);

if (h>=a) a=h+1;

}

tmp=RightChild(n);



if (!EmptyABR(tmp)) {

h=altezza(tmp);

if (h>=a) a=h+1;

}

return(a);



}

4.3.Distruzione di un Albero


L’eliminazione di tutti gli elementi di un albero, può essere realizzata tramite l’uso delle funzioni EmptyABR e Delete:

while (!EmptyABR(n))

Delete(&n,Label(n));
dove n è il puntatore alla radice dell'albero che si vuole distruggere.

5.Un'Applicazione relativa alla Gestione di un Albero Binario di Ricerca


Il seguente programma gestisce una struttura dati ABR contenente elementi di tipo struct composti da tre campi: cognome, nome ed età. Si suppone l’esistenza di un file di nome “abr.h” contenente l’implementazione dell’ADT ABR (con puntatori), la definizione del tipobaseABR e tutte le funzioni primitive.
#include
void flush(void);
#include "abr.h"
abr albero;
void preordine(abr);

void inordine(abr);

void postordine(abr);

unsigned int altezza(abr);


main(){

unsigned short scelta;

tipobaseABR elemento;
MakeNullABR(&albero);
do {

printf("\nMenu di Operazioni ABR \n ");

printf("\n1-Inserimento ");

printf("\n2-Ricerca ");

printf("\n3-Cancellazione ");

printf("\n4-Visita Albero Binario di Ricerca in Preordine ");

printf("\n5-Visita Albero Binario di Ricerca in Ordine ");

printf("\n6-Visita Albero Binario di Ricerca in Postordine ");

printf("\n7-Calcolo Altezza ABR ");

printf("\n8-Eliminazione ABR ");

printf("\n9-Fine ");

printf("\nInserisci la scelta -----> ");

scanf("%u",&scelta);

flush();
switch(scelta) {

case 1 :

LeggiElemento(&elemento);

InsertABR(&albero,elemento);

break;


case 2 :

if (EmptyABR(albero)) printf("\nAlbero Vuoto ");

else {

CercaElemento(&elemento);



if (Member(albero,elemento))

printf("\nElemento Trovato \n ");

else printf("\nElemento non Trovato \n ");

}

break;



case 3 :

if (EmptyABR(albero)) printf("\nAlbero Vuoto ");

else {

CercaElemento(&elemento);



Delete(&albero,elemento);

}

break;



case 4 :

if (EmptyABR(albero)) printf("\n Albero Vuoto \n");

else preordine(albero);

break;


case 5 :

if (EmptyABR(albero)) printf("\nAlbero Vuoto \n");

else inordine(albero);

break;


case 6 :

if (EmptyABR(albero)) printf("\nAlbero Vuoto \n");

else postordine(albero);

break;


case 7 :

if (EmptyABR(albero)) printf("\nAlbero Vuoto \n");

else printf("\nL'altezza dell'ABR e' %u ",altezza(albero));

break;


case 8 :

while (!EmptyABR(albero))

Delete(&albero,Label(albero));

}

} while (scelta<9);



}
void flush(void){

while (getchar()!='\n');

}
void preordine(abr n){

if (!EmptyABR(n)) {

VisualizzaElemento(Label(n));

preordine(LeftChild(n));

preordine(RightChild(n));

}

}


void inordine(abr n){

if (!EmptyABR(n)) {

inordine(LeftChild(n));

VisualizzaElemento(Label(n));

inordine(RightChild(n));

}

}


void postordine(abr n){

if (!EmptyABR(n)) {

postordine(LeftChild(n));

postordine(RightChild(n));

VisualizzaElemento(Label(n));

}

}


unsigned int altezza(abr n){

unsigned int a=0,h;

abr tmp;

tmp=LeftChild(n);

if (!EmptyABR(tmp)) {

h=altezza(tmp);

if (h>=a) a=h+1;

}

tmp=RightChild(n);



if (!EmptyABR(tmp)) {

h=altezza(tmp);

if (h>=a) a=h+1;

}

return(a);



}




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


©astratto.info 2019
invia messaggio

    Pagina principale