HomeWork060703 < Programmazione2pz

---++ Un esempio di alberi bilanciati: gli alberi di Fibonacci

---+++ Rappresentazione di alberi binari

Supponiamo di rappresentare alberi binari etichettati con interi per mezzo di espressioni così definite:

   * l'albero vuoto è indicato con 0
   * assumendo che, se l &ge; 0, allora l<sup>+</sup> = 0, mentre se l < 0, allora l<sup>+</sup> = l, l'albero T la cui radice contiene l'etichetta l e ha come figlio sinistro l'albero T<sub>1</sub> e come figlio destro l'albero T<sub>2</sub>, lo si rappresenta con l<sup>+</sup> t<sub>1</sub> t<sub>2</sub>, ovvero con la sequenza formata da l<sup>+</sup> seguita dalla sequenza t<sub>1</sub> che rappresenta l'albero T<sub>1</sub> e dalla seqeunza t<sub>2</sub> che rappresenta T<sub>2</sub>.

Si osservi che l'aggiunta di 1 alle etichette non-negative serve a garantire la possibilità di usare 0 per indicare l'albero vuoto.

*Esempio* La sequenza

1 2 0 -2 3 4 0 0 5 -6 0 0 0 0 -1 0 1 0 0

 corrisponde all'albero

<img src="%ATTACHURLPATH%/AlberoBinario.jpg" alt="AlberoBinario.jpg" width='243' height='282' />

---+++ Gli alberi di Fibonacci

Gli alberi di Fibonacci sono un caso particolare di alberi binari bilanciati in altezza. Per ogni numero naturale i = 0,1,2,3,... il corrispondente albero di Fibonacci di ordine i è definito ricorsivamente da:

   * l'albero vuoto è l'unico albero di Fibonacci di ordine 0
   * tutti gli alberi contenenti un solo nodo sono alberi di Fibonacci di ordine 1
   * un albero binario la cui radice ha come figlio sinistro un albero di Fibonacci di ordine n+1 e come figlio destro un albero di Fibonacci di ordine n è un albero di Fibonacci di ordine n+2

E' facile vedere che ogni albero di Fibonacci di ordine i > 0 ha altezza i-1. Quindi, per ogni nodo non-foglia di un albero di Fibonacci si ha che l'altezza del figlio sinistro è maggiore di 1 dell'altezza del figlio destro.

---+++ Funzioni da implementare

   1. Scrivere una funzione che legge una sequenza di interi che rappresenta un albero binario in base alle regole sopra descritte e costruisce il corrispondente albero.
   2. Scrivere una funzione che, in base alle regole sopra descritte, stampa la sequenza corrispondente a un albero binario.
   3. Scrivere una funzione che verifica se un albero binario è un albero di Fibonacci.
   4. Scrivere un programma che, dopo aver letto un albero binario T, stampa gli alberi contenuti in T che non-sono alberi di Fibonacci, ma tali che i loro sotto-alberi sinistro e destro sono alberi di Fibonacci. 

-- Users.StefanoGuerrini - 05 Jun 2007
This topic: Programmazione2pz > WebHome > AnnoAcc0607 > HomeWork0607 > HomeWork060703
Topic revision: r1 - 2007-06-05 - StefanoGuerrini