[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

Se qualcuno ha qualche idea mi farebbe molto piacere!
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.

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.

ciao

[fero86]

Originariamente inviato da gugoXX

Per gli alberi e le visite devi chiedere a Vincenzo1968.

ti confondi con le macchine a stati

[DanieleC88]

Originariamente inviato da fero86

ti confondi con le macchine a stati

No, ha anche diversi tutorial su alberi binari (autobilancianti e non) sul suo sito...

[banryu79]

Originariamente inviato da DanieleC88

No, ha anche diversi tutorial su alberi binari (autobilancianti e non) sul suo sito...

Sul quale però non pubblica un articolo nuovo da eoni... gli organizziamo un autodafè?

[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.

[fero86]

Originariamente inviato da DanieleC88

In verità stavo pensando di scrivere qualcosina io sugli alberi AVL,

LOL*!!!

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

anche se non sono propriamente la fonte più autorevole...

come no?? dopo il botto che hai fatto ad algoritmi??

[domenico88]

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