Visita breadth-first albero binario in C

[tommy1996q]

Come si capisce dal titolo, ho un problema a implementare in C un algoritmo di visita per livelli di un albero binario...

Avendo lavorato su visite depth-first, inizialmente pensavo che un metodo ricorsivo potesse funzionare, ma mi sono ricreduto subito in quanto passando ricorsivamente il puntatore al figlio (per esempio) sinistro alla mia funzione di visita breadth-first, questa si sarebbe "dimenticata" del figlio destro, che devo invece analizzare per terzo (dopo la radice e il figlio sinistro).

Sinceramente sono un po' bloccato e volevo chiedervi se qualcuno ha qualche idea..

Personalmente quello che avevo pensato era di aggiungere alla struct che mi definisce un elemento dell'albero un altro campo, definito come:

typedef {a,b,c} Visita ;

dove all'inizio ogni nodo ha valore a nel campo Visita, poi analizzandolo cambio il valore in b e quando analizzo i suoi figli (se ne ha) cambio ancora il valore in c, per tenere conto di chi ho già analizzato e chi no, visto che non potendo fare un algoritmo ricorsivo (almeno credo non si possa fare), ho il sospetto di dover ripartire dalla radice a ogni chiamata di funzione...

Il problema maggiore che ho riscontrato è però che quando analizzo il figlio sinistro, dovrei in qualche modo tornare indietro a suo padre e analizzare il figlio destro, perciò sono quasi sicuro di dover aggiungere un altro campo alla struttura, che memorizza un puntatore al padre.

Non so se l'idea potrebbe essere giusta, ma anche se lo fosse non capisco come mettere tutto insieme....idee?

[apatriarca]

Il metodo classico consiste nell'inserire i nodi da visitare in una coda. Ad ogni iterazione estrai un nodo dalla coda e aggiungi poi quindi i suoi figli all'interno di essa uno dopo l'altro.

[tommy1996q]

A dire il vero abbiamo parlato poco di code, nè di come implementarle in C, comunque mi sembra che sia il contrario della pila, qualcosa di tipo First in First out, giusto?

[apatriarca]

Sì, una coda è una struttura dati in cui il primo elemento inserito è anche il primo ad uscire. L'implementazione può essere basata su un buffer circolare, una lista o altro. A seconda di come è implementato l'albero potrebbe non essere necessario usare una coda per la tua visita, ma è in generale il metodo più semplice ed efficiente. Se mostri il codice posso darti consigli più mirati.

[tommy1996q]

Il generico nodo dell'albero, per come l'avevo pensata, sarebbe:

struct nodo{
int info;
struct nodo* left_son;
struct_nodo* right_son;
struct nodo* father;
Visita visita;
}

Dove visita è il tipo user-defined che ho creato con typedef(vedi post sopra). Il problema è che sono riuscito a dare al campo father di ogni nodo il puntatore al nodo che lo precede, ma adesso non ho idea di come dirgli di analizzare gli elementi per livelli... Non so se l'approccio possa essere giusto o se ci sia un modo più veloce, come ti ho detto non ho mai lavorato con strutture ad accesso FIFO...

[apatriarca]

Un'idea non molto efficiente per fare quello che desideri potrebbe essere di calcolare il massimo livello all'interno dell'array con una visita in profondità e quindi scrivere un metodo per stampare i valori ad un particolare livello (sempre usando una visita in profondità e un algoritmo ricorsivo). Per farlo non hai in realtà neanche bisogno di aggiungere ulteriori campi nell'albero.

Puoi anche seguire una strada come quella che vorresti intraprendere, ma devi prima di tutto assicurarti che tutti i campi per la visita nell'albero siano correttamente inizializzati prima di iniziare la visita. L'idea in questo caso è quella di fare una visita in profondità e stampare il primo nodo non visitato, segnarlo come visitato e quindi settare un qualche tipo di flag per sapere se sotto di esso ci sono altri nodi da visitare ad una passata successiva. Una volta finita la visita controlli il flag e se ci sono altri nodi da visitare fai una nuova visita che a questo punto visiterà il livello successivo. Continui finché ci sono nodi da visitare.

Ecco un codice di esempio che fa uso di una coda (di dimensione fissa e non particolarmente efficiente o elegante). Come puoi osservare la visita in ampiezza in questo caso è particolarmente semplice ed elegante. E' inoltre molto più efficiente. Un altro metodo per implementare una coda è poi ad esempio basato sulle liste concatenate. Come hai implementato le pile?

#include <stdio.h>
#include <stdlib.h>

typedef struct TNode TNode;
struct TNode {
   TNode *left, *right;
   char info;
};

/* Dimensione fissa per comodità. */
typedef struct Queue256 Queue256;
struct Queue256 {
   int appended;
   int removed;
   TNode *buffer[256];
};

int Queue256_size(Queue256 *q)
{
   return q->appended - q->removed;
}

void Queue256_append(Queue256 *q, TNode *n)
{
   if (Queue256_size(q) < 256) {
      q->buffer[q->appended % 256] = n;
      ++(q->appended);
   } else {
      /* Coda piena (non dovrebbe succedere in questo programma. */
      fputs("Coda piena!\n", stderr);
   }
}

TNode *Queue256_pop(Queue256 *q)
{
   if (Queue256_size(q) == 0) {
      return NULL;
   }

   TNode *ret = q->buffer[q->removed];
   ++q->removed;
   return ret;
}

void printBFS(TNode *tree)
{
   Queue256 queue = {0};
   TNode *current = NULL;

   Queue256_append(&queue, tree);
   
   while ((current = Queue256_pop(&queue)) != NULL) {
      putchar(current->info);
      putchar(' ');
      if (current->left != NULL) { Queue256_append(&queue, current->left); }
      if (current->right != NULL) { Queue256_append(&queue, current->right); }
   }
   putchar('\n');
}

int main(void)
{
   /* Creo albero (R (a (b (c . .) .) .) (d (e . .) (f . (g . .)))) */
   TNode g = {NULL, NULL, 'g'};
   TNode f = {NULL, &g, 'f'};
   TNode e = {NULL, NULL, 'e'};
   TNode d = {&e, &f, 'd'};
   TNode c = {NULL, NULL, 'c'};
   TNode b = {&c, NULL, 'b'};
   TNode a = {&b, NULL, 'a'};
   TNode R = {&a, &d, 'R'};

   /* Visito l'albero in ampiezza (dovrebbe stampare R a d b e f c g) */
   printBFS(&R);

   return 0;
}

[tommy1996q]

Ti ringrazio moltissimo apatriarca, ti dirò che in realtà non abbiamo visto particolari implementazioni per le pile, abbiamo visto solo qualche cosa su liste concatenate e alberi binari, mentre sappiamo cos'è una pila solo in linea teorica (sistema LIFO), anche se credo che una semplice implementazione potrebbe essere una lista concatenata dove ad ogni chiamata aggiungo un elemento in testa oppure lo cancello.

In ogni caso quello che hai detto è molto interessante, cercherò di capire il codice da te scritto.

Solo una cosa: ho notato che hai usato il preincremento. Prendo due esempi:
++q->removed; e ++(q->append);
potresti spiegarmi come valgono in questo caso le regole di precedenza e chi si applica prima?

Personalmente non mi è sempre chiarissimo cosa succede quando si usano molti operatori tutti insieme senza parentesi.Ad esempio so che avendo due puntatori a stringhe s e t, facendo while(*s++=*t++); ottengo che la stringa puntata da t è copiata nella zona puntata da s, ma sinceramente il codice mi sembra molto ermetico e tutt'altro che chiaro...

[apatriarca]

Il preincremento è in genere più semplice da comprendere rispetto al post-incremento perché è la prima cosa che succede.. Le due espressioni sono in realtà del tutto equivalenti in quando -> ha maggiore precedenza rispetto a ++ (prefisso). Nel pre-incremento avviene prima l'incremento della variabile e poi viene usata l'espressione, con il post-incremento viene prima restituito il valore e poi viene incrementata la variabile. Nel tuo esempio (*s++=*t++) abbiamo prima (*s = *t) e poi entrambi i valori vengono incrementati di uno. Non ho comunque sinceramente mai usato qualcosa del genere e tendo ad evitare l'uso di tali espressioni all'interno di altre. Nel codice ho infatti sempre messo tali espressioni in righe a parte.