Newsgroup: it.comp.java
Titolo: [OT] Convertire albero n-ario in albero binario...

Ciao....
Esiste un algoritmo che mi permette di convertire un albero n-ario in un
albero binario?
Grazie!
Nicola

 wrote in message
news:WPhR9.75626$TC5.2...@twister1.libero.it...

Preso da "Algoritmi e Strutture Dati" di Torvergata, corso tenuto dal prof.
A.Pettorossi
binary tree con costruttore bt= b(bt1,n,bt2)
n-ary tree con costruttore  nt=T(n,n-list)
    list-nt è la lista dei figli del nodo con valore n, per comodità un
numero intero.
 Kin (null) =null;
Kin (T(n,l))= K(T(n,l),[])
            [] è la lista vuota
K(T(n,[]),[])=b(e,n,e)
K(T(n,[]),head+tail)=b(e,n,K(head,tail))
K(T(n,head+tail),[])=b(K(head,tail),n,e)
K(T(n,head1+tai1l),head2+tail2)=b(K(head1,tai1l),n,K(head2,tail2))
dove una lista è sempre vista come
    null oppure un elemento (head)appeso ad una lista(tail)
In una chiamata K(t,lt), lt è la lista dei nodi FRATELLI a t.
L'algoritmo era stato implementato in C++ con i puntatori, dato che di Java
non so niente non so se può fare facilmente allora stesso modo.
HTH
--
Emanuele Di Saverio
---------------------------------------------
Remove NOSPAM manually for reply
Scusate le vaccate se  ne dico!

se nn mi ricordo male l'argomento e' tratto bene in "Algoritmi e strutture
dati in java" di Adam Drodzek edito dalla apogeo e tradotto da Dal passo

 dati in java" di Adam Drodzek edito dalla apogeo e tradotto da Dal passo
Marcello Dal Passo per caso?
Io forse possiedo la versione in inglese di quel testo....
Non è edito dall'Apogeo però. Il testo è di Goodrich e Tamassia.
Ricordi se quell'algoritmo ha un nome particolare oppure se fa parte di
qualche argomento particolare per cortesia?
Ad ogni modo darò un'occhiata sul quel libro!
Grazie mille!
Ciao, Nicola

 qualche argomento particolare per cortesia?
Sinceramente no, nn mi ricordo.
Forse pero' pensandoci adesso c'e' stato un equivoco!
Io sto parlando di alberi di RICERCA, tu nn li hai menzionati....
spero cmq di esserti stato cmq di aiuto!

 spero cmq di esserti stato cmq di aiuto!
 No, infatti, non parlavo di alberi di ricerca ma di alberi binari e alberi
n-ari semplicemente.
Grazie in ogni caso!
Ciao, Nicola

 n-ari semplicemente.
Mi sembra che si facesse così:
per ogni nodo dell'albero n-ario il nodo corrispondente nell'albero binario
avrà come figlio sx il PRIMO dei figli del nodo corrispondente, e come
figli destri i suoi fratelli, cugini, eccetera.
Graficamente (mancano le connessioni, ma si dovrebbe capire, *=null):
                      n-ario                                    binario
                            a                                             a
                   b       c     d        ==>                  b         *
               e   f   g                                      e         c
                                                            *    f    *    d
                                                               *   g
Ora non ho il codice pronto ma non dovrebbe essere difficile implementarlo.
Ciao, Guido.

 ha scritto nel messaggio
news:oclT9.9559$AA2.4...@news2.tin.it...

Grazie mille!
Lo implemento subito!
Ciao, Nicola

Comunque cerca di evitare di riproporre tutto il mio post quando
bastava scrivere due righe:
1: Ringraziamento
2: Il tuo nome
Ciao, Guido.

?????

 ?????
Volevo solo dire a Sargasso che quando mi ha ringraziato per
la mia "dritta" non era necessario riproporre tutto il mio post
(due post piu' "su").
Nulla di personale! :D
Ciao, Guido.

 Ciao, Guido.
Ciao, Nicola

Un giorno ormai lontano, il potente
Sargasso ritrovo' l'antica pergamena nota come
'[OT] Convertire albero n-ario in albero binario...'.
Leggendarie furono allora le sue parole:

e' facilissimo!!!! Per ogni nodo: il primo figlio diventa il figlio
sinistro, il successivo fratello il figlio destro:
   a                          a
   |                         ---
 -----                      |   |
| | | |    ------\          b
b c d h    ------/         ---
    |                     |   |
    i                         c
                             ---
                            |   |
                                d
                               ---
                              |   |
                              i   h 
-- 
__/\__ * this mail has been written by Talpa Stellare
\ TS / * che da piccolo una volta e' morto.
 |/\|  * icq# 78630739 - togli i caratteri maiuscoli x e-mail