Newsgroup: it.comp.lang.c
Titolo: gestire i BST (alberi binari) iterativamente

Ho un albero binario.
So copiarlo in un altro albero binario, portando parallelamente avanti
la ricorsione.
So farci altra roba, ma tutto ricorsivamente. Non riesco a fare nulla
iterativamente, perché da un nodo non riesco a risalire a suo padre.
Questo è fortemente collegato ad un algoritmo di sorting che
semplicemente prende un array, lo copia in un BST (quindi lo copia
"ordinatamente"), e fin qui è facile, e poi lo ricopia daccapo, ordinato
appunto.
Non riesco a seguire ricorsivamente gli indirizzi dei puntatori degli
elementi dell'array, perché so gestre un albero binario solo
ricorsivamente.
Qualcuno sa come si fa? Ho cercato in lungo e in largo, ma non sono
riuscito a trovare spiegazioni in dettaglio, ma solo "accenni" a
funzioni peraltro a me sconosciute...
Grazie a chi vorrà aiutarmi, ho l'esame di Laboratorio di Fisica
Computazionale tra una settimana... :-)
ciao

 iterativamente, perché da un nodo non riesco a risalire a suo padre.
Infatti. Come mai vuoi implementare un algoritmo iterativo? L'unico modo 
è che ti implementi tu stesso un stack di puntatori. A quel punto puoi 
simulare il codice ricorsivo in maniera iterativa. Hai un vantaggio di 
prestazioni (e di memoria) dovuto al fatto che non è necessario fare 
chiamate a funzione.
E.


Oppure, se lo spazio non e' un problema, aggiungi ai record che
usi per i nodi dell'albero un puntatore al nodo padre, cosi' puoi
muoverti a piacimento su e giu'.
Oppure anche un puntatore al fratello di destra e/o di sinistra, per
muoverti allo stesso livello, etc. etc.
Non che questo risolva necessariamente il problema del
ricorsivo vs. iterativo (non ho capito bene cosa non ti va bene
della ricorsione, e in particolare trovo questa tua frase
un po' criptica:
 > Non riesco a seguire ricorsivamente gli indirizzi dei puntatori degli
 > elementi dell'array, perché so gestre un albero binario solo
 > ricorsivamente.
ciao,
g.

chiamate a funzione.
so di cosa parli (conosco gli stack, li uso per esempio per
"invertire"...) ma non ho capito quello che hai detto
ciao, grazie


Quando attraversi l'albero per il tuo algoritmo, hai bisogno di poter 
risalire verso la radice. Visto che il tuo albero non ha i puntatori al 
nodo padre, quello che puoi fare è mantenere in uno stack l'elenco degli 
antenati del nodo che stai esaminando. Quando scendi di un livello 
nell'albero fai un "push", per risalire fai un "pop".
E.

muoverti allo stesso livello, etc. etc.
troppo facile così...
non so se è "permesso".
mi spiego meglio. un albero binario è una struttura con il campo
puntatoore a destra, un puntatore a sinistra, e uno o più  dati.
la struttura di questa struttura (ehm...) sono i due puntatori. ma i
puntatori sono ai figli, non al padre...
certo, uno si può inventare quello che vuole...ma boh.
...
mettiamo che io ho un albero così:
			A
	B				C
D		E		F		G
			      H
alla funzione passo la struttura albero, il puntatore all'array, e la
dimensione dell'albero (che è anche la dimensione dell'array, che è già
dichiarato ed allocato)
la funzione ha un int i=0, contatore ,e lo incrementa un ciclo alla
volta, ed ha un tree_t *tmp, un puntatore temporaneo alla struttura
albero 
tmp=tree;
1) tmp->left!=NULL, quindi scende a sinistra, mettiamo con un
tmp=tmp->left; Facciamo che quando scende registra il fatto che è sceso
a sinistra, con un char lr che è uguale a l, e registra anche il
puntatore del nodo dal quale viene, con un tree_t *parent
Questa cosa succede fino a D
2)D->left=NULL, e allora controlla D->right che pure è uguale a NULL.
Quindi registra D->data in *(array++)
3) risale a dx, perché è venuto da lì (e lo sa grazie al flag lr), e
risale a B, di cui sa il puntatore, che viene registrato in parent
4) sei venuto da sinistra, quindi registri il dato B e provi a scendere
a destra, per ultimo provi a scendere a destra, da E
5) registri E, e risali a sinistra, perché è da lì che sei venuto
6) sei in B. Ora dovresti risalire in A. Ma come fai a sapere il suo
indirizzo?
Un modo sarebbe appunto di fare un struttura-albero in cui ogni nodo ha
anche un puntatore al proprio padre.
Un altro modo sarebbe quello di avere un array che registra tutti i
puntatori dei nodi che visita (magari l'array di prima, bidimensionale,
gestito opportunamente), e quindi saprebbe che il puntatore che gli
serve è quello prima di quello dal quale viene.
Tutte e due le soluzioni mi sembrano un po' macchinose...
Possibile che non c'è altro modo?
grazie, ciao

 albero 
Non ho capito se stai cercando di implementare il metodo ricorsivo o 
quello iterativo. Quello ricorsivo è più semplice di come stai cercando 
di fare. Quello iterativo è più complicato, perché credo che sia 
*necessario* utilizzare un stack se vuoi visitare tutti i nodi del tuo 
albero.
E.

albero.
vediamo, se è più semplice, come dovrei procedere?
nell'altro caso, è proprio quello il punto: come faccio iterativamente a
visitare tutti i nodi del mio albero? io scendo, scendo, e scendo, e poi
risalgo perché in qualche modo mi ricordo il padre, ma e poi riscendo
dall'altra parte e risalgo; ma a questo punto non so più quale è il
"padre del padre", perché non ne so il puntatore.

nell'albero fai un "push", per risalire fai un "pop".
carino.
devo rifletterci. poi ti faccio sapere :-)
grazie

 "padre del padre", perché non ne so il puntatore.
...devi memorizzare i puntatori di tutti gli antenati del nodo corrente.
E.