Per generare un albero con chiavi casuali e non ordinato è sufficiente utilizzare una funzione rand() per ottenere chiavi casuali e inserire queste chiavi una volta a destra e una volta a sinistra nell’albero, come mostrato dal codice che segue.
Allegato: alberi generale
Per utilizzare il codice Allegato: alberi generale è necessario costruire un file di nome TREE0 .txt in cui vanno inserite le chiavi dei singoli nodi dell'albero che si vuole costruire.
Due alberi binari ordinati si dicono isomorfi solo se sono identici, cioè le radici sono uguali, i rispettivi sottoalberi sinistri sono identici ed i rispettivi sottoalberi destri sono identici.
Per gli alberi non ordinati, è del tutto indifferente se una chiave è presente nel sottoalbero destro o nel sottoalbero sinistro della radice. Pertanto due alberi non ordinati sono isomorfi se le loro radici contengono lo stesso elemento ed inoltre o accade che i due sottoalberi sinistri ed i due sottoalberi destri sono isomorfi tra loro oppure accade che il sottoalbero sinistro del primo sia isomorfo al sottoalbero destro del secondo ed il sottoalbero destro del primo è isomorfo al sottoalbero sinistro del secondo.
Una procedura ricorsiva, che sfrutta questa definizione permette di verificare se due alberi A e B, non ordinati, sono isomorfi tra di loro.
Allegato: albIsomorf
Per utilizzare il codice Allegato: albIsomorf è necessario costruire un file di nome TREE1 .txt in cui vanno inserite le chiavi dei singoli nodi dell'albero che si vuole costruire.
In generale se si vogliono contare i nodi di un albero contenenti un elemento che soddisfa una proprietà data P si adotta il seguente schema per la funzione conta:
if (A==NULL) return 0;
else
if (A->key soddisfa P) k=1
else k=0
return k +conta(A->left)+conta(A->right)
dove l’espressione booleana in parentesi nei casi in cui P sia una proprietà difficile da verificare può diventare una funzione booleana che verifica se A->key gode o meno della proprietà.
ALBERI non ordinati
Scrivere una procedura tale che assegnato un albero binario non ordinato di interi positivi restituisca un puntatore al valore massimo e indichi quante volte questo valore massimo è contenuto nell’albero.
Scrivere, inoltre una procedura tale 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.
Allegato: alb non ordinati
Per utilizzare il codice Allegato: alb non ordinati è necessario costruire un file di nome TREE1 .txt in cui vanno inserite le chiavi dei singoli nodi dell’albero che si vuole costruire.
Ricordiamo che un albero si dice bilanciato se il livello di tutte le foglie è uguale all’altezza dell’albero o a questa stessa altezza meno 1.
Dato ad esempio, un albero BST di interi non bilanciato, si attraversa l’albero secondo la procedura IN-ORDER, e per ogni chiave letta:
{ Dato un albero binario BST non bilanciato costruire un albero bilanciato }
Mostra codiceL’animazione che segue mostra come opera l’agoritmo prima descritto e successivamente viene mostrato un suo output.
Allegato: albBilanciato
Per utilizzare il codice Allegato: abBilanciato è necessario costruire un file di nome TREE8 .txt in cui vanno inserite le chiavi dei singoli nodi dell’albero che si vuole costruire
Illustriamo di seguito due esercizi già sviluppati:
Verificare se un albero A contiene almeno uno zero.
Mostra codiceVerificare se l'albero A contiene solo zeri.
Mostra codiceLa Famiglia
{calcola le parentele}
Supponiamo di avere una famiglia tale che ogni suo membro ha al più due figli.
Descritte le parentele secondo un albero non ordinato scrivere le funzioni
char Padre
{dato un nome determinare se ha un padre e chi è}
void Figlio
{dato un nome determinare se ha uno o due figli e chi sono}
char Nonno
{dato un nome determinare chi è il nonno}
Sviluppare una funzione che, assegnato un nodo T di un albero binario, restituisce il puntatore al nodo “Zio” di T se esiste, NULL altrimenti (nodo “zio” è quel nodo che è figlio dello stesso genitore del nodo T).
char Fratello
{dato un nome determinare se ha un fratello e chi è}
char Cugino
{dato un nome determinare se ha un Cugino e chi è}
Di seguito si mostra lo pseudo-codice che risolve il problema dell’albero genealogico utilizzando alcune delle function già descritte in precedenza.
Assegnato un albero A trovare rispettivamente il padre di un assegnato figlio, il figlio di un assegnato padre, il nonno di un assegnato nipote, lo zio di un assegnato nipote,
// MAIN cerca_il_padre(A);
cerca_il_figlio(A);
cerca_il_nonno(A);
cerca_lo_zio(A);
Dati due alberi non ordinati verificare che ordinatamente tutte le chiavi dell’albero A sono multipli delle chiavi dell’albero B.
Allegato: alberimultipli
Sia A un albero binario non ordinato. Ogni qualvolta un nodo dell’albero ha al più un figlio e presenta il campo numero uguale a zero eliminare il nodo sostituendolo con l’unico figlio.
Esempio:
Dato un albero binario calcolare quanti nodi hanno il sottoalbero sinistro nullo.
Dato un albero binario ordinato di interi definire una funzione ricorsiva che restituisca il numero di elementi positivi in esso presenti.
Dato un albero BST contare quanti nodi ci sono al di sotto di un nodo preassegnato.
Dato un albero BST e la chiave K di un suo nodo determinare il valore della chiave più piccola e di quella più grande del sotto albero di K.
Dato un albero non ordinato contare quanti nodi hanno la stessa chiave e quanti figli sono multipli del padre.