[C]Alberi binari

[domenico88]

Salve a tutti:)

Sto smanettando un pò con gli alberi binari, implementando nei programmi algoritmi ricorsivi per visita, inserimento, ricerca ecc.

Volevo provare a scrivere un algoritmo per la visita(per contare il numero di nodi) di un albero in versione iterativa però non saprei proprio da dove cominciare:help:

Se qualcuno ha qualche idea mi farebbe molto piacere!:D
Grazie a tutti!

[gugoXX]

Per gli alberi e le visite devi chiedere a Vincenzo1968. :)

[DanieleC88]

Non è difficile.
Immagina una visita in-order comunissima, fatta ricorsivamente:
algoritmo InOrderTraversal(albero T)
{
se T non è nullo {
InOrderTraversal(nodo sinistro di T);
visita il nodo T;
InOrderTraversal(nodo destro di T);
}
}

Qui si sfrutta pesantemente lo stack di sistema per risalire nell'albero ogni volta che si ha finito di visitare un nodo. Per farlo iterativamente di solito si fa la stessa identica cosa che implicitamente fa anche l'algoritmo ricorsivo: si usa uno stack. :D

Verrebbe fuori una cosa del genere:
algoritmo InOrderTraversal(albero T)
{
stack S;
nodo N;

N = radice di T;

ripeti {
finché N non è nullo {
aggiungi N in cima alla pila S;
N = figlio sinistro di N;
}

se la pila S è vuota {
esci;
}

N = preleva la cima della pila S;
visita N;

N = figlio destro di N;
}
}

C'è anche un altro modo di fare la visita iterativa di un albero binario, non richiede l'utilizzo di stack e bastano un paio di puntatori. Però è più complicata da scrivere. :p

ciao ;)

[fero86]

Per gli alberi e le visite devi chiedere a Vincenzo1968. :) ti confondi con le macchine a stati :asd:

[DanieleC88]

ti confondi con le macchine a stati :asd:
No, ha anche diversi tutorial su alberi binari (autobilancianti e non) sul suo sito... :D

[banryu79]

No, ha anche diversi tutorial su alberi binari (autobilancianti e non) sul suo sito... :D
Sul quale però non pubblica un articolo nuovo da eoni... gli organizziamo un autodafè? :D

[DanieleC88]

In verità stavo pensando di scrivere qualcosina io sugli alberi AVL, anche se non sono propriamente la fonte più autorevole... e comunque sì, un bel autodafè ci sta tutto. :p

[fero86]

In verità stavo pensando di scrivere qualcosina io sugli alberi AVL, LOL*!!! :D

*per capire la mia ilaritá bisogna conoscere alcuni eventi di vita reale :asd:



anche se non sono propriamente la fonte più autorevole... come no?? dopo il botto che hai fatto ad algoritmi?? :D :D

[domenico88]

grazie a tutti per le risp:D
dovrei usare una pila per ricreare la situazione che si crea in memoria con le chiamate ricorsive, non ci avevo proprio penato...