Newsgroup: it.comp.lang.c
Titolo: Lettura da file di un'albero binario

Hello World,
c'è qualcuno che può aiutarmi?
Ho codificato un albero binario nel modo seguente:
- ogni nodo è rappresentato da due bit: 11 se ha entrambi i figli, 10 se ha
solo il figlio sinistro, 01 se ha solo il figlio destro, 00 se è una foglia.
- l'albero, letto in profondità, viene scritto su un file. Ad esempio
1111000000 rappresenta l'albero
                     o
                   /   \
                 o     o
               /   \
             o     o
dove i "o" sono i nodi. (Spero che si capisca).
Il problema è:
un programma che prende in input quel file, come può ricostruire l'albero?
Il numero di bit per la codifica dell'albero non è necessariamente multiplo
di 8. Leggendo dal file un byte alla volta, cioè 4 nodi, non riesco a
costruire una procedura ricorsiva che risolve il problema.
Inoltre: è necessario che il programma conosca il numero di nodi dell'albero
(e da questo la lunghezza della codifica) per operare come mi serve?
Infine: anche ammesso di risolvere il problema per codifiche che siano di
lunghezza multipla di 8, come si trattano i bit in eccedenza nell'altro
caso?
Grazie,
Alessandro

- l'albero, letto in profondità, viene scritto su un file. Ad esempio
...
Io di solito uso una routine generica che legge/scrive i prossimi n
bit da/su file codificata in questo modo:
  unsigned long bit_acc;   /* accumulatore corrente */
  int bit_count;           /* numero bits validi in acc */
  FILE *bit_file;          /* file contenente i dati */
  /* Legge un codice di n bit da file */
  unsigned long ReadCode(int n)
  {
    unsigned long code;
    while(bit_count<n)
    {
      /* Mancano bit: leggi un altro char */
      bit_acc|=(unsigned long)fgetc(bit_file) << bit_count;
      bit_count+=BITSPERBYTE;
    }
    /* estrazione n bit meno significativi */
    code=bit_acc & ((1<<n)-1);
 
    /* rimozione della parte letta da acc */
    bit_count-=n;
    bit_acc>>=n;
    return code;
  }
  /* Scrive un codice di n bit su file */
  void WriteCode(unsigned long x,int n)
  {
    /* Accoda i bit a acc */
    bit_acc|=x<<bit_count;
    bit_count+=n;
    /* Scrive tutti i caratteri completati */
    while (bit_count>=BITSPERBYTE)
    {
      fputc((unsigned char)bit_acc,bit_file);
      bit_acc>>=BITSPERBYTE;
      bit_count-=BITSPERBYTE;
    }
  }
Nota che alla fine di una scrittura puo' essere presente
qualcosa nell'accumulatore e quindi prima di chiudere il
file e' necessario concludere la scrittura di quest'ultima
parte con "if (bit_count) fputc(bit_acc,bit_file);".
HTH
Andrea
--
Andrea Griffini, Programmer
http://www.netservers.com/~agriff

Non e' necessario conoscere il numero di nodi, a meno che l'intero
albero non venga memorizzato in struttura tipo array; una idea di tale
struttura puo' essere una matrice bidimensionale con tante righe
quanti sono i nodi, e due colonne. Gli indici di riga rappresentano il
"nome" dei vari nodi, e in relazione a tale riga, le due colonne
contengono i valori indici degli eventuali figli sx e dx (-1 non
esistente).
Io suggerirei e porterei avanti una facile struttura dinamica:
typedef struct vertice {
    struct vertice * figlio_sx;
    struct vertice * figlio_dx;
} nodo;
Con la seguente idea algoritmica della funzione ricorsiva che crea
l'albero. Non scrivo la versione tradotta in C perche' i particolari
implementativi sono numerosi e nella lunghezza della soluzione
farebbero perdere di vista quello che a te, credo, stia a cuore,
l'algoritmo. (Per la versione completa puoi postarmi in privato)
void crea_albero(nodo * radice)
{
    radice->figlio_sx = NULL;
    radice->figlio_dx = NULL;
    LEGGI (E MEMORIZZA) DUE BIT DAL BUFFER
    SE I DUE BIT LETTI NON SONO "00" ALLORA
        {
        SE IL PRIMO BIT E' "1"
            {
            ALLOCA NUOVO NODO (del tipo: nodo * nodo_sx);
            radice->figlio_sx = nodo_sx;
            crea_albero(nodo_sx);
            }
        SE IL SECONDO BIT E' "1"
            {
            ALLOCA NUOVO NODO (del tipo: nodo * nodo_dx);
            radice->figlio_dx = nodo_dx;
            crea_albero(nodo_dx);
            }
        }
}
La deallocazione delle strutture potrebbe avvenire mediante una
scansione in profondita', deallocando in post-ordine.

 HTH
Giuro che non so cosa vuol dire. Comunque grazie mille in anticipo.
Ciao,
Ale

 esistente).
Purtroppo vorrei usare un'array di puntatori a strutture di tipo:
struct tiponodo {
                          int son[2];
                          int level;
                          int function;
}
dove level  e function sono il livello del nodo nell'albero e la sua
"funzione" (calcolata in un certo modo...).
Il mio problema è che durante la scansione del file, per incrementare
l'indice dell'elemento corrente nell'array di puntatori (cioè l'elemento che
punterà al nodo di cui sto leggendo i dati dal file), perdo la ricorsività
della procedura.
Forse la soluzione è semplice e non riesco a trovarla.
Hai qualche idea?

Giuro che non so cosa vuol dire. Comunque grazie mille in anticipo.
"Hope This Helps" -> "Spero che quanto ho scritto ti sia di aiuto"
E' uno dei modi standard di concludere una risposta su usenet...
un po' come "TIA"->"Thanks In Advance"->"Grazie in anticipo (per
le risposta che mi darete)" che spesso si vede a conclusione di
una domanda.
SCQHSTSDA ;)


 della procedura.
se non pensando che hai usato un passaggio di parametri per indirizzo
(o reference), oppure una _unica_ variabile globale.
Esplicito quanto ho gia' scritto, seguendo le tue indicazioni. Prova
questo:
#define MAX_N_NODI  ....
struct tiponodo {
                          int son[2]; /* idx '0' = figlio sx   */
                                          /* valore contenuto = idx
nell'array del figlio sx o dx */
                                          /* valore contenuto -1 =
nessun figlio */
                          int level;
                          int function;
}
struct tiponodo albero[MAX_N_NODI ]; /* per esempio definita globale
*/
.
.
void crea_albero(int radice, int livello)
{
int bit1 , bit2 ;
static int prossimo_indice_libero_in_albero = 0;
    /* inizialmente alla "radice" non e' collegato alcun figlio */
    albero[radice].son[0] = -1;
    albero[radice].son[1] = -1;
    albero[radice].level    = livello;
    bit1 = leggi_un_bit_da_file();
    bit2 = leggi_un_bit_da_file();
    /* se i due bit letti non sono "00" allora entra nell'if     */
    if (bit1+bit2) {
        /* se il primo bit e' "1" allora devo creare nodo sx */
        if (bit1) {
            albero[radice].son[0] =
++prossimo_indice_libero_in_albero;
            /* fai qui i tuoi calcoli .... */
            crea_albero(prossimo_indice_libero_in_albero , livello+1);
        }
        /* se il secondo bit e' "1" allora devo creare nodo dx */
        if (bit2) {
            albero[radice].son[1] =
++prossimo_indice_libero_in_albero;
            /* fai qui i tuoi calcoli .... */
            crea_albero(prossimo_indice_libero_in_albero , livello+1);
        }
    }
}
Questa funzione si presta per essere lanciata cosi':
crea_albero(0,0);
Perdona qualche eventuale piccolo errore dovuto alla trascrizione.
Questa soluzione e' soggetta ad ogni possibile miglioramento formale e
strutturale.
A te, o ad altri, il compito di disegnare la funzione: " int
leggi_un_bit_da_file(void);"