PDA

Visualizza la versione completa : Alberi...scervelliamoci un p


pictor
12-12-2003, 17:23
Salve....ho un quesito per voi :)
Premetto che sono in 4 superiore e per voi potrebbe essere una cosa semplicissima, ma ve lo chiedo lo stesso :tongue:

Il mio prof. di informatica mi ha dato un esercizio sugli alberi che, nonostante ci abbia pensato un p, non riesco a risolvere....

Mi chiedevo se aveva sbagliato lui o se effettivamente possibile risolvere l'esercizio....

Vi riporto qua sotto il testo: :)

Visitando un albero binario, contenente dei caratteri, in ordine differito e stampando il contenuto di ogni nodo si ottiene la sequenza:
CFEDBINMLHGA

mentre lo stesso albero visitato in ordine binario simmetrico fornisce la sequenza:
CBEFDAIGMNHL

Ricostruire l'albero binario in oggetto specificando se trattasi o meno di un albero binario di ricerca.


Sar io che sono ottuso (probabile :fagiano: ) ma mi chiedevo se qualcuno poteva trovarmi la soluzione.....

Grazie mille :ciauz:

LeleFT
12-12-2003, 17:56
Se per ordine differito si intende il post-ordine (ossia la visita eseguita nell'ordine SOTTOALBERO SX, SOTTOALBERO DX, RADICE) e per ordine binario simmetrico si intende la visita in ordine (ossia la visita eseguita nell'ordine SOTTOALBERO SX, RADICE, SOTTOALBERO DX), allora l'albero proposto non pu essere un albero binario di ricerca.

Motivazione: la visita post-ordine (differita) ha come ultimo elemento visitato la radice dell'albero. In questo caso 'A'; per essere un albero binario di ricerca, quindi, deve essere un albero sbilanciato che non ha alcun sottoalbero di sinistra; ma questo in contraddizione con la visita in ordine: prima di A, infatti, vengono visitati i nodi 'CBEFD'.


Ciao.

pictor
12-12-2003, 18:26
Grazie mille :D

Mi hai aperto gli occhi....io avevo assunto l'esercizio nel modo sbagliato.....non risolvendolo usando la sola logica :dh:

eheheheh a questo punto semplicissimo... :gren:

E pensare quanto mi ci sono scervellato per trovare una struttura giusta :fagiano:

Grazie di nuovo :ciauz:

Loading