Alberi...scervelliamoci un pò

[pictor]

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 ) ma mi chiedevo se qualcuno poteva trovarmi la soluzione.....

Grazie mille

[LeleFT]

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]

Grazie mille

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

eheheheh a questo punto è semplicissimo... :gren:

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

Grazie di nuovo