Newsgroup: it.comp.programmare.win32
Titolo: -*-@@@HELP!!!@@@-*-

Ho definito in VC++ un albero binario con la seguente struttura:
struct nodo
{nodo* p_dx;
int info;
nodo* p_sx;
};
c'è qualcuno che può aiutarmi ad implementare gli algoritmi di visita a
livelli
e di riduzione da un albero non binario a un albero binario?
sono disperato!!!
ringrazio tutti coloro che mi aiuteranno.
Daniele
gio...@freemail.it
 

livelli e di riduzione da un albero non binario a un albero binario?
Comiciamo dalla riduzione n-ario -> binario. Innanzitutto bisogna
sapere come l'albero n-ario è organizzato:
1) ciascun nodo potrebbe avere un array di puntatori per indirizzare
tutti i nodi figli, oppure potrebbe organizzarli in una lista;
2) gli alberi binari sono utili per rappresentare delle relazioni
d'ordine sui dati (e quindi sveltire successive operazioni di
ricerca), gli alberi n-ari si prestano invece a cose tipo albero
genealogico (o schema di una rete) che non ha senso rendere binario
(cioè imporre ad alcuni nodi di essere ad un livello inferiore di
altri se prima non lo erano);
diciamo allora che tu hai un albeo genealogico e vuoi utilizzare la
struttura binaria che hai scritto solo perchè è semplice e non ti
costringe ad avere array (magari di lunghezza variabile) di puntatori
nei vari nodi:
                [1]          struct nodo {
               / | \          nodo* p_dx;     --> primo fratello
              /  |  \         int info;
            [2] [3] [4]       nodo* p_sx;     --> primo figlio
           /       / | \     };
          /       /  |  \
        [5]     [6] [7] [8]
Un binario immagazzina i riferimenti ai sottoalberi dx e sx.
Un n-ario immagazzina in p_sx il riferimento al primo figlio ed in
p_dx il riferimento al primo fratello.
             [1]
             /
           [2]
           / \
         [5] [3]            se guardi le sequenze 2-3-4 e 
               \            6-7-8 vedi che sono delle liste
              [4]           collegate tramite p_sx la cui
               /            testa parte da un p_dx
             [6]            
              \             viene comunque mantenuto un certo
              [7]           ordine nella struttura, ma i livelli
               \            sono tutti saltati: [5] è a livello
               [8]          3, ma [6] è a 5, ecc..
Passiamo ora alla visita a livelli e cominciamo da un albero binario.
Immagina di avere una coda (first-in,first-out): inizialmente è vuota,
tu ci aggiungi il puntatore alla radice dell'albero (&[1]) e poi
chiami una funzione VisitaLivelli. Questa non è altro che un loop
finchè la coda contiene elementi: ad ogni iterazione elabora nel modo
che ti interessa l'informazione puntata dal primo elemento in uscita
dalla coda, poi immette nella coda i due puntatori p_sx e p_dx e
toglie il puntatore già elaborato:
Contenuto della coda all'inizio dell'iterazione:
1) [1]
2) [NULL] [2]
3) [3] [5] [NULL]
4) [3] [5]
5) [ NULL] [NULL] [3] 
6) ...  ( la coda scorre così -----> )
Se l'albero è n-ario c'è qualche differenza:
1) se ogni nodo mantiene i puntatori a tutti i figli (cioè ha una
sorta di array di p_figlio1...p_figlion) puoi usare la coda di prima,
basta che ogni volta immetti tutti i puntatori.
2) se invece usi la struttura a due puntatori (figlio e fratello)
dovresti vedere ogni volta p_sx, che è la lista dei fratelli, e
percorrerla. Praticamente fai una visita in post-ordine dell'albero
(nodo attuale - visita sottoalbero sx - visita sottoalbero dx)
[1]
 |
[2]-[3]-[4]
 |       |
[5]     [6]-[7]-[8]
Ultime cose: nella coda puoi anche evitare di metteri i [NULL] e se
vuoi che la tua visita a livelli processi un livello per volta e poi
si fermi ti basta prevedere che la coda contenga dei puntatori
speciali di fine livello: sta poi a te fare in modo che vengano
inseriti dopo l'ultimo elemento di un livello.
salutoni
virgilio