[C] albero n-ario ==> binario

[gepeppe]

salve a tutti, sono giorni che tento di fare un algoritmo per trasformare un albero enario in uno binario, ma senza successo. Ho un albero di questo tipo:


ogni nodo è una struct che ha un link al primo figlio e uno ai fratelli. Devo trasformarlo in un albero binario. Ecco un esempio:

==>

se un nodo ha più di due figli, aggiungo un nodo X per rispettare il "binario", ma i nodi 2, 6, 7 hanno lo stesso livello, anche se ho inserito la x, come i 3 4 5.

Come potrei fare????

grazie

[Furla]

il modo migliore è son-brother, ma da come descrivi la struct sembra sia già in quella forma. quindi il tuo albero generico è già memorizzato in una struttura dati ad albero binario, devi solo imparare ad usarla.

un albero son-brother, come dice il nome stesso, è un albero in cui ogni nodo punta ad un figlio e ad un fratello. di solito a sinistra c'è il figlio e a destra il fratello. in c la struct sarebbe tipo questa

struct nodo 
{
 int label;
 nodo* son;
 nodo* brother;
}

ovviamente un nodo che è l'ultimo dei suoi fratelli avrà puntatore destro nullo, mentre un nodo senza figli avrà puntatore sinistro nullo.
il risultato è questo (le frecce orizontali indicano il puntamento di destra, ovvero ai fratelli, quelli verticali indicano il puntamento a sinistra, ovvero ai figli):

[gepeppe]

ma scusa, un albero binario non è un albero in cui ogni nodo ha al massimo due figli?? Il mio problema è appunto trasformare (o soltanto stampare) un albero n-ario, con n figli per nodo, in un albero binario, con 2 figli per nodo, rispettando oviamente il fatto che se il nodo 2 ha 4 figli(i quali stanno tutti allo stesso livello) dopo il nodo 2 nell'albero binario avrà ancora 4 figli (che dovranno ipoteticamente stare nello stesso livello). Per questo faccio uso dei nodi X.

L'immagine che hai postato è proprio la mia idea di albero n-ario...ma la stampa e la trasformazione in albero binario non mi sono chiari....

io la vedo ancora una cosa molto complicata, ma purtroppo ne ho bisogno...

[wingman87]

Non ho capito la storia dello stare allo stesso livello, cioè, nel tuo esempio la X non conta ai fini del livello?
E poi un'altra cosa, il tuo esempio è con nodi di al massimo 3 figli ma il tuo algoritmo può prendere in input un albero con nodi con un qualunque numero di figli?

[Furla]

Originariamente inviato da gepeppe

ma scusa, un albero binario non è un albero in cui ogni nodo ha al massimo due figli?? Il mio problema è appunto trasformare (o soltanto stampare) un albero n-ario, con n figli per nodo, in un albero binario, con 2 figli per nodo, rispettando oviamente il fatto che se il nodo 2 ha 4 figli(i quali stanno tutti allo stesso livello) dopo il nodo 2 nell'albero binario avrà ancora 4 figli (che dovranno ipoteticamente stare nello stesso livello). Per questo faccio uso dei nodi X.

L'immagine che hai postato è proprio la mia idea di albero n-ario...ma la stampa e la trasformazione in albero binario non mi sono chiari....

io la vedo ancora una cosa molto complicata, ma purtroppo ne ho bisogno...

l'immagine che ho postato è un albero binario, infatti se guardi bene da ogni nodo partono al massimo due freccie, ma usato in modo "astuto" per poter rappresentare alberi generici. che io sappia è il modo migliore di farlo, soprattutto per quanto riguarda la realizzazione di funzioni che ci lavorino sopra. basta sfruttare la definizione ricorsiva di albero binario e il fatto che a sinistra c'è la lista dei figli, a destra ci sono i fratelli. quindi ti consiglio, se il problema è stampare, di sfruttare questa struttura dati così com'è e di scrivere la funzione che lo stampa. se ci dai informazioni su come deve essere stampato ti possiamo dare una mano

[gepeppe]

uso il nodo X per fare in modo che i figli di un certo nodo, anche se più di due, stanno allo stesso livello diciamo, anche se graficamente non sembra. Nel disegno ho messo 3 figli, è un caso, potrebbe averne 10 o di più. cmq il problema non è l'albero n-ario, come il disegno, con puntatore al figlio e ai fratelli...quello è implementato bene, riesco a fare tutto. Il problema è che devo rappresentare in memoria l'albero binario corrispondente a quello n-ario e stamparli entrambi.

ad esempio, la funzione per visitare l'albero in profondità preordine è questa:

Visita_Preordine(nodo *T)
{
	/*vista T*/
   if(T -> figlio != NULL)
      Visita-Preordine(T -> figlio);
   if(T -> fratello != NULL)
     Visita-Preordine(T -> fratello);
}

dove mi vede prima la radice, poi scende a sinistra e cosi via...ma applicata ad un albero n-ario, lo stampa come uno binario???

io pensavo che dovevo ricrearlo in memmoria l'albero binario partendo da quello n-ario..cioè creare un nodo X, fare in modo che stiano allo stesso livello, e fare tutto il resto..ma dite che non c'è bisogno??

[claxon]

ue gepeppe, ci acchiappiamo pure qua, pure io mi stavo documentando un po' su questo fatto, in parte mi trovo su quanto detto, nel senso che un albero n-ario è già un albero binario (ogni nodo ha 2 puntatori), ma viene visto diversamente, noi non dobbiamo fare altro che modificare la lista dei "fratelli" in modo tale che non sia lineare ma diventi anche essa un albero a puntatori (non è difficile perchè ogni elemento è un nodo dello stesso tipo). La cosa da fare è sfruttare il puntatore sx di ogni nodo della lista, visto che all'inizio noi utilizzavamo solo il dx per puntare al fratello. Così facendo trasformeremo la lista in albero inserendo opportunamente dei nodi neutri che contengono un'informazione fittizia e saranno utilizzati solo per diramare l'albero. Cmq oggi chiedo un po' a Lamberti e poi ne parliamo.

[gepeppe]

ehehe...ttt per LASD

cmq non è chiarissima la spiegazione... nessun altro suggerimento?

[gepeppe]

up

[wingman87]

Io sinceramente non ho capito cosa stai chiedendo.. Perchè non fai come ti ha detto Furla?

[Furla]

è facile accorgersi che per ottenere la visita anticipata dell'albero generico basta fare la visita anticipata dell'albero binario figlio-fratello che lo rappresenta. una visita posticipata dell'albero figlio-fratello corrisponde ad una visita simmetrica dell'albero generico da esso rappresentato. per ottenere la visita posticipata dell'albero generico a partire dalla sua rappresentazione figlio-fratello invece c'è da scrivere una funzione apposta, se ti vuoi divertire

il mio consiglio è di lasciar perdere l'uso di nodi fittizi che sono uno spreco di memoria ed una palla al piede quando vuoi lavorare sulle etichette e/o sui livelli, qualsiasi cosa tu voglia fare con un albero generico la puoi realizzare con una funzione che lavori sulla sua rappresentazione figlio-fratello

[gepeppe]

oltre che stamparlo dovrei crearlo proprio fisicamente l'albero binario. Cmq se io volessi trasformare un albero n-ario in uno binario, non avrei nessun problema, se non dovessi RISPETTARE LE PARENTELE...è semplicicssimo. Io invece devo rispettarle...cioè se un nodo di un albero n-ario ha 3 figlio, nel rispettivo albero binario deve ancora avere 3 figli..ovvero uno che aveva prima, un nodo X, di cui sono figli gli altri due nodi. Ecco rispettata la parentela, non facendo contare il nodo X. forse non riesco a farmi capire io...

Furla ho letto quello che hai scritto, e ti ringrazio per le risposte, ma la vedo troppo complicata come descrizione...non ci ho capito molto

[wingman87]

Nella prima immagine di Furla se guardi la parentela è rispettata:
Il nodo 1 ha un figlio con 2 fratelli e quindi un totale di 3 figli
Il nodo 2 ha un figlio con 2 fratelli e quindi sempre 3 figli
Il nodo 3 ha un figlio.

E' un altro discorso se quello che ti è stato richiesto è l'uso di questo nodo X...

[Furla]

scusa, ma se non conservi le parentele non è lo stesso albero! la rappresentazione figlio fratello le conserva eccome, ci mancherebbe altro. il fatto che ogni nodo punti ad un fratello significa, in pratica, avere la lista dei figli di ogni nodo. tant'è che il tuo albero generico di partenza è già memorizzato in forma figlio-fratello.

a meno che non ti sia stato esplicitamente richiesto di usare la rappresentazione che dici tu, che è poco efficiente e scomoda, ti conviene cercare un po' di documentazione sui son-brother che sono molto più semplici da maneggiare, una volta che hai capito come funzionano.

se ci dici quali sono le operazioni che devi fare sull'albero ti aiutiamo volentieri a scrivere le funzioni

[gepeppe]

ok...le operazioni sono 3:

la prima è creare un albero n-ario partendo da un file di testo...FATTO (nella forma figlio, fratello con fratello che punta ad una lista di 0 o massimo 10 fratelli]

la seconda è stampare l'albero n-ario appena creato (pensavo ad una vistita in preordine) ecco il codice:

void Visita_Preordine(nodo *T)
{
	/*vista T*/
	printf("%s\n", T -> info);
	if(T -> figlio != NULL)
	Visita_Preordine(T -> figlio);
	if(T -> fratello != NULL)
	Visita_Preordine(T -> fratello);
}

devo solo pensare a come "far vedere meglio" il fatto di essere figlio o fratello..cosi me li stampa semplicemente uno sotto l'altro.

la terza cosa è trasformare l'albero appena creato in binario (e qui casco io )

ora, ho ho un blocco mentale che non mi permette di capire come implementare la cosa...o non saprei. detta da voi sembra semplice..ma io non ci arrivo proprio!! cmq i nodi X potrei evitarli se riuscissi a rispettare la parentela, ma io la vedo impossibile(se un nodo ha 3 figli, come fa in binario ad averne ancora 3 senza nodo X??)

[cionci]

Guarda che quello che ti ha postato Furla qui è un albero n-ario rappresentato sotto forma di albero binario
http://img530.imageshack.us/my.php?image=abvzm6fw5.jpg

Il trucco è proprio nella forma figlio - fratello. Immaginati un albero n-ario memorizzato in quella forma. A questo punto immaginiamoci di chiamare figlio -> figlio1 e fratello -> figlio2. Ti torna che sia un albero binario ?

[gepeppe]

Originariamente inviato da cionci

Guarda che quello che ti ha postato Furla qui è un albero n-ario rappresentato sotto forma di albero binario
http://img530.imageshack.us/my.php?image=abvzm6fw5.jpg

Il trucco è proprio nella forma figlio - fratello. Immaginati un albero n-ario memorizzato in quella forma. A questo punto immaginiamoci di chiamare figlio -> figlio1 e fratello -> figlio2. Ti torna che sia un albero binario ?

sisi..mi trovo...è tranquillamente un albero binario...però non esiste solo figlio2,...ma anche figlio3, figlio4, figlio5....so che la struttura è quella di un albero binario, ma ha più figli di quanti ne dovrebbe avere...questo è il mio problema..ha più figli di quanti ne dovrebbe avere(ne dovrebbero essere 2 per ogni genitore)

[cionci]

In che senso ? Ogni nodo ha solo due figli

[gepeppe]

Originariamente inviato da cionci

In che senso ? Ogni nodo ha solo due figli

ehehe..ecco il grosso problema. se vedi il mio primo post ho fatto una descrizione (credo chiara) del problema. trasformare un albero n-ario con più di due figli per genitore in un albero binario con due figli per genitore e con un nodo X, quando serve, per far rispettare i gradi di parentela. (padre con 3 figli ==> diventa in binario ==> padre con 1 figlio + 1 figlio "X" che ha gli altri 2 figli e che non da contribbuto ai livelli (il livello dei sui 2 figli ha lo stesso suo livello)...

è proprio un problema...

[banryu79]

Originariamente inviato da gepeppe

...
trasformare un albero n-ario con più di due figli per genitore in un albero binario con due figli per genitore e con un nodo X, quando serve, per far rispettare i gradi di parentela. (padre con 3 figli ==> diventa in binario ==> padre con 1 figlio + 1 figlio "X" che ha gli altri 2 figli e che non da contribbuto ai livelli (il livello dei sui 2 figli ha lo stesso suo livello)...

Ipotesi diverse in base a quello che ho capito:

a) Durante il run dell'algoritmo di conversione da albero enario a albero binario potresti semplicemente "segnare" in modo opportuno il "figlio X" per poterlo riconoscere e interpretare il fatto che i suoi nodi figlio si trovano al suo stesso livello (e quindi a quello dei fratelli di "figlio X"): ovvero quando lo si "attraversa" per raggiungere un suo figlio non si "incrementa" il livello...

b) Se si può, ogni nodo memorizza il livello in cui si trova, così i figli generati da "figlio X" riporterebbero lo stesso valore di livello del padre e quindi dei fratelli del padre, rispettando così la stessa situazione che c'era nell'albero enario di partenza...

Es.: albero enario:

           |A|
          /   \
       |B|   |C|
      / | \
    |D||E||F|

converito (* == "figlio X"):

          |A|
          /  \
        |B| |C|
        / \
       |D||E|*
           /\
         |F||-|

La logica che devi definire ed implementare è quella che si occupa, per ogni nodo dell'albero enario in cui sono presenti più di due figli, di prendere i figli maggiori del primo a tre a tre; il primo della terna diventa "figlio X" e il secondo e terzo della terna i suoi figli; il terzo della terna in particolare, diventa a suo volta "figlio X" se ci sono ulteriori terne oltre la prima da inserire.

Ho capito bene?