Sequenza Selezione Iterazione Funzioni Ricorsione Operat. su interi Stringhe Vettori Array
Tabelle File Liste Alberi Esami Maturità Preparazione esami Database Macchina di Turing Automi
Algebra Geometria Giochi            

Esercizi sugli Alberi

 

1

Scrivere una procedura che, dato un albero binario di interi restituisca TRUE se tutte le foglie sono allo stesso livello, FALSE altrimenti.

2

Scrivere una procedura che, dato un albero, ricerchi un elemento dato X e restituisca tutti i suoi ascendenti (antenati) oltre a se stesso.

3

Scrivere una procedura che, dato un albero binario di interi, restituisca TRUE se esiste almeno un nodo tale che "il nodo ha due figli e questi figli sono uguali".

4

Scrivere una procedura che, dato un albero binario di interi distinti fra loro e dato un intero X, elimini gli eventuali sottoalberi di X se X occorre nell'albero.

5

Scrivere una procedura che, dato un albero binario di interi ne generi un secondo identico al primo.

6

Scrivere una procedura che, dato un albero binario di interi, ne generi un secondo simile al primo, ma con ogni nodo avente come valore il numero di ascendenti del nodo stesso.

7

Scrivere una procedura che, dato un albero binario di interi, restituisca la lunghezza del cammino medio dell'albero.

8

Dato un insieme di numeri interi, si vogliono distribuire tali numeri in un albero binario secondo il seguente metodo: il primo numero letto costituisce la radice dell'albero. Per ogni altro numero si percorre l'albero confrontando tale numero con i nodi successivi che si incontrano (a partire dalla radice) e proseguendo sul ramo destro se il numero dato è maggiore del nodo, sul sinistro in caso contrario, finché‚ non si trova una foglia. A questo punto si inserisce il nuovo numero, a destra o a sinistra della foglia (che ora diviene nodo), a seconda che sia maggiore o no del numero.

9

Scrivere una procedura che visualizza solo le foglie di un albero binario.

10

Scrivere una procedura che, dato un elemento di un albero binario, visualizza il sottoalbero che ha tale elemento come radice.

11

Si vuole realizzare una funzione che verifichi se un albero binario avente informazioni dei nodi di tipo carattere, presenta tali nodi ordinati in modo binario, ovvero in modo tale che, considerato un qualsiasi nodo N, tutte le informazioni dei nodi presenti nel sotto albero sinistro di N siano minori dell'informazione di N e tutte quelle dei nodi del sotto albero destro siano maggiori o uguali della stessa informazione presente in N.

  1. descrivere in Linguaggio di Progetto l'algoritmo per implementare la funzione;

  2. descrivere adeguatamente l'interfaccia della funzione (parametri e valori restituiti);

  3. implementare l'algoritmo in un linguaggio ad alto livello conosciuto.

12

Si richiede una funzione che prendendo in ingresso il puntatore ad un albero binario con campo informazione dei nodi di tipo intero, verifichi se si tratta di un albero binario di ricerca, ovvero se le informazioni dei nodi sono ordinate in modo binario, e in caso contrario, ne crei uno avente stessa radice e che sia ordinato secondo quanto detto.

  1. descrivere in Linguaggio di Progetto un algoritmo per realizzare la funzione;

  2. descrivere adeguatamente l'interfaccia della funzione (parametri e valori restituiti);

  3. implementare l'algoritmo in un linguaggio ad alto livello conosciuto.

 

13

Realizzare in linguaggio C una funzione che, presa una foresta di alberi radicati aventi campo informazione di tipo intero, li ordini in modo crescente rispetto alla somma delle informazioni di ogni albero.

14

Dato un albero binario di numeri interi, si vuole una funzione per contare gli elementi di tale albero che hanno valore minore di un valore assegnato.

Dopo aver detto come si possono utilizzare procedure già note per risolvere il problema, scrivere la funzione richiesta in linguaggio C:

  1. come vi comportate per verificare che la funzione sia corretta?

  2. quali sono le indicazioni da dare insieme alla funzione per chi volesse utilizzarla senza sapere come è stata costruita?