[C] Funzione per scorrere un albero

[faLBI]

Ciao a tutti, ho bisogno una mano per scrivere una funzione in C che mi sta dando non pochi grattacapi.
Io ho due tipi di dati così definiti:

typedef struct nodo * punt;
typedef struct nodo{
char carattere;
int array[N];
punt left;
punt right;
}nodo;


Ho bisogno di una funzione che riceve in ingresso un puntatore punt al primo nodo dell'albero e riempa gli array in questo modo:
Consideriamo il nodo in testa. Questo nodo deve avere l'array vuoto. I puntatori left e right di questo nodo punteranno ad altri due nodi (o magari uno od entrambi i puntatori posso puntare a null, le caratteristiche dell'albero le descrivo alla fine di questo post).
Nell'array del nodo puntato da right bisognerà inserire tutto il contenuto dell'array del nodo precedente (che essendo il primo era vuoto) e aggiungere nel primo spazio vuoto dell'array uno 0 mentre nell'array del nodo raggiunto da left bisognerà sempre copiare il contenuto dell'array del nodo precedente e poi inserie nel primo spazio vuoto di questo array un 1. Si supponga che la dimensione dell'array sia sufficiente a contenere tutti gli elementi necessari per arrivare ai nodi foglia. Infine la funzione, arrivata ai nodi foglia, deve stampare il carattere seguito da tutti gli elementi dell'array... Altra nota: l'albero non è nè simmetrico, nè binario, nè altro... non ha una struttura particolare, deve andare bene per qualsiasi tipo di albero. Ci sto impazzendo da un paio di giorni, riuscite a darmi una mano?
Grazie

[gugoXX]

Si puo' risolvere con una funziona ricorsiva.

[faLBI]

Lo so.. il mio problema è proprio che non sono riuscito a scrivere una funzione ricorsiva che funzioni...
Vi posto quello che ho fatto fin'ora, ma è una vera schifezza....
punt riempi_array(punt t){
int n,i;
for (n=0; t->array[n]!='\n'; n++){
};
if ((t->left->left==NULL)&&(t->left->right==NULL)){
for (i=0; i<n; i++){
t->left->array[i]=t->array[i];
}
i++;
t->left->array[i]=1;
printf("\n%c: ", t->left->carattere);
for(n=0; n<=i; n++){
printf("%d", t->left->array[n]);
};
return t;
}
if((t->right->left==NULL)&&(t->right->right==NULL)){
printf("\n%c: ", t->right->carattere);
for (i=0; i<n; i++){
t->right->array[i]=t->array[i];
}
i++;
t->right->array[i]=0;
for(n=0; n<=i; n++){
printf("%d", t->right->array[n]);
};
return t;
}
else{
t->left->array[n+1]=1;
t->right->array[n+1]=0;
t=riempi_array(t->left);
if (t->left->left==NULL)
return riempi_array(t->right);
else
return riempi_array(t->left);
}
}


Dovrei riuscire a farla entro stasera... AIUTOOOOOOOOO!!!!:help: :help: :help:

[gugoXX]

Provo a buttare giu' un po' di pesudocodice...


// La funzione verra' chiamata la prima volta con:
// Riempi(radice);
void Riempi(nodo* corrente)
{
if (corrente->left!=NULL)
{
nodi* prossimo=corrente->left;
Copio l'array di corrente sopra prossimo
Aggiungo uno 0 in coda
Riempi(prossimo); //Ricorro su mio figlio sinistro
}
if (corrente->right!=NULL)
{
nodi* prossimo=corrente->right;
Copio l'array di corrente sopra prossimo
Aggiungo un 1 in coda
Riempi(prossimo); //Ricorro su mio figlio destro
}
if ( (corrente->left!=NULL) && (corrente->right!=NULL) )
{
//Se sono qui entrambi i miei figli sono NULL, sono una foglia.
Stampo il carattere e l'array del nodo corrente, come richiesto
}
}

[faLBI]

Grazie mille:D:D

L'ho tradotto in questo modo...

void riempi_array(punt t){
int n,i;
punt prossimo;
for (n=0; t->array[n]!='\n'; n++){ /*misura la lunghezza dell'array*/
};
if(t->left!=NULL){
prossimo=t->left;
for (i=0; i<n; i++){
prossimo->array[i]=t->array[i];
}
i++;
prossimo->array[i]=1;
riempi_array(prossimo);
}
if(t->right!=NULL){
prossimo=t->right;
for (i=0; i<n; i++){
prossimo->array[i]=t->array[i];
}
i++;
prossimo->array[i]=1;
riempi_array(prossimo);
}
if( (t->left!=NULL) && (t->right!=NULL) ){
printf("\n%c: ", t->let);
for(n=0; n<=i; n++){
printf("%d", t->right->array[n]);
}
}
}

Il problema è che nell'esecuzione mi dà segmentation fault... Mi aiutate a capire il problema? Sono più che sicuro che il problema sia in questa funzione perché il resto del programma viene eseguito senza problemi, viene stampato tutto ciò che c'è prima della chiamata di questa funzione e abbiamo controllato tutto diverse volte...

Grazie ancora per l'aiuto

[gugoXX]

Grazie mille:D:D

L'ho tradotto in questo modo...

void riempi_array(punt t)
{
int n,i;
punt prossimo;
for (n=0; t->array[n]!='\n'; n++){ /*misura la lunghezza dell'array*/
};
if(t->left!=NULL){
prossimo=t->left;
for (i=0; i<n; i++){
prossimo->array[i]=t->array[i];
}
i++;
prossimo->array[i]=1;
riempi_array(prossimo);
}
if(t->right!=NULL){
prossimo=t->right;
for (i=0; i<n; i++){
prossimo->array[i]=t->array[i];
}
i++;
prossimo->array[i]=1;
riempi_array(prossimo);
}
if( (t->left!=NULL) && (t->right!=NULL) ){
printf("\n%c: ", t->let);
for(n=0; n<=i; n++){
printf("%d", t->right->array[n]);
}
}
}

Il problema è che nell'esecuzione mi dà segmentation fault... Mi aiutate a capire il problema? Sono più che sicuro che il problema sia in questa funzione perché il resto del programma viene eseguito senza problemi, viene stampato tutto ciò che c'è prima della chiamata di questa funzione e abbiamo controllato tutto diverse volte...

Grazie ancora per l'aiuto


Le righe in bold hanno un errore, il secondo ce l'ho messo io (quando bisogna stamapare?)
il terzo e' grave, cosa bisogna stampare?
Ma non potete fare una sessione di debug, per vedere cosa succede quando entrate in quella funzione?

[faLBI]

Succede una cosa stranissima..
Ho provato a mettere un printf("0") all'inizio della funzione, subito dopo la dichiarazione delle variabili e prima di tutti gli if e del for che controlla la lunghezza dell'array...
Eppure mi dà segmentation fault appena entra nella funzione, non riesce nemmeno a stampare quello 0.
Ho pensato allora che il puntatore alla radice puntasse in realtà a qualcos'altro... Allora ho provato a controllare che il puntatore che riceve in ingresso effettivamente sia la radice di un albero, e ho verificato che lì non ci sono problemi.. il problema è proprio nella funzione.
Per quanto riguarda il terzo errore, gravissima svista, ma a quanto pare c'è un errore ancora prima :muro: :muro:

void riempi_array(punt t)
{
int n,i;
punt prossimo;
printf("0");
for (n=0; t->array[n]!='\n'; n++) /*misura la lunghezza dell'array*/
{
};
if(t->left!=NULL)
{
printf("A");
prossimo=t->left;
for (i=0; i<n; i++){
prossimo->array[i]=t->array[i];
}
i++;
prossimo->array[i]=0;
riempi_array(prossimo);
}
if(t->right!=NULL)
{
printf("B");
prossimo=t->right;
for (i=0; i<n; i++)
{
prossimo->array[i]=t->array[i];
}
i++;
prossimo->array[i]=1;
riempi_array(prossimo);
}
if( (t->left!=NULL) && (t->right!=NULL) )
{
printf("C");
printf("\n%c: ", t->let);
for(n=0; n<=i; n++)
{
printf("%d", t->array[n]);
}
}
}

[faLBI]

Rettifica!!!
Ho appena scoperto che la funzione che crea l'albero non funziona come dovrebbe!! Sotto a spulciare!!
Grazie 1000 gugoXX per l'aiuto, ora dovrei riuscire a cavarmela!!
Ciao!!