Conta i nodi di un albero binario[C]

[fk16]

Salve a tutti, volevo un aiuto nel risolvere il seguente programma:

/*Scrivere una funzione che restituisca in un vettore di 2 interi il numero di elementi
a destra e a sinistra del nodo radice di un albero binario di double.*/

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

struct nodo{         
   int val_nodo;     
   struct nodo *dx;
   struct nodo *sx;
   };

typedef struct nodo NODO;
typedef NODO *albero;  

int* conta(albero,int*);
albero costruisci(int, albero sx, albero dx);
void visita(albero);

int main(){
	int n;
	int *vet;
	vet=(int*)calloc(2,sizeof(int));
    vet[0]=0,vet[1]=0;
    albero t1,t2,t3,t4;
	t1=costruisci(3,NULL,NULL);
	t2=costruisci(2,NULL,NULL);
	t3=costruisci(5,t1,t2);    
	t1=costruisci(7,NULL,NULL); 
	t2=costruisci(6,NULL,NULL);
	t4=costruisci(1,t1,t2);    
	t1=costruisci(4,t3,t4);    
	visita(t1);                
    vet=conta(t1,vet);
    printf("\nA destra ci sono %d nodi\n", vet[0]);
    printf("A sinistra ci sono %d nodi\n", vet[1]);
    free(vet);
system("pause");
return 0;
}

albero costruisci(int val, albero sinistra, albero destra){ 
	   albero radice;                                       
	   radice=(NODO*)malloc(sizeof(NODO));
	   radice->val_nodo=val;
	   radice->sx=sinistra;
	   radice->dx=destra;
	   return radice;
	   }
	   							  		
void visita(albero radice){
     if(radice!=NULL){
	 	printf("%d  ",radice->val_nodo);	
		visita(radice->sx);
		visita(radice->dx);
		}
		return;
		} 		  

int* conta(albero radice, int *vettore){
     if(radice==NULL)
        return 0;
     else{
       conta(radice->sx,vettore);
          vettore[1]++;
       conta(radice->dx,vettore);   
          vettore[0]++;
          }
     return vettore;
     }

La funzione che ho fatto io per contare i nodi me ne conta 7 a destra e 7 a sinistra, dove sbaglio???

[hamming_burst]

Ciao,
allora considero che la costruzione dell'albero sia corretta (anche se mi sembra parecchio inutile quell'elenco di codice, se vuoi costruire un albero generico basta una singola linea alla funzione costruisci() ma ne riparliamo quando abbiamo risolto il problema del post).

	
    vet=conta(t1,vet);
    printf("\nA destra ci sono %d nodi\n", vet[0]);
    printf("A sinistra ci sono %d nodi\n", vet[1]);
   ...

int* conta(albero radice, int *vettore){
     if(radice==NULL)
        return 0;
     else{
       conta(radice->sx,vettore);
          vettore[1]++;
       conta(radice->dx,vettore);   
          vettore[0]++;
          }
     return vettore;
     }

La funzione che ho fatto io per contare i nodi me ne conta 7 a destra e 7 a sinistra, dove sbaglio???

ma te vuoi avere i nodi totali, o vuoi avere il risultato distinto di nodi sinistri e nodi destri?

[fk16]

Voglio avere il numero di nodi destri(e assegnare questo valore al primo elemento del vettore) e sinistri(e assegnare questo valore al secondo elemento del vettore)....Grazie per eventuali risposte.

[hamming_burst]

"fk16":Voglio avere il numero di nodi destri(e assegnare questo valore al primo elemento del vettore) e sinistri(e assegnare questo valore al secondo elemento del vettore)....Grazie per eventuali risposte.

Ho visto ora, c'era già scritto in un commento del codice che ci vuoi fare...

Comunque veniamo al problema.
Il tuo codice non può funzionare perchè non distingui quando aumentare il numero di nodi destri e sinistri, se vedi è una sequenza di istruzioni senza distinzione.

quello che bisogna fare è:
- visita nodo sinistro -> aumento NS
- visita nodo destro -> aumento ND

perciò:

void conta(tree t,int NS, int ND){

 if(t!=NULL){
     conta(t->left,NS+1,ND);
     conta(t->right,NS,ND+1);
 }
}

che chiamerai con

conta(t,0,0)

in C esiste il passaggio per riferimento (la tua soluzione può andar bene). Un'altra versione può consistere nel tipizzare il codice nell'aumento di un solo parametro alla volta, per non utilizzare gli array od altro. Oppure penso che si possa usare un la ricorsione con accumulatore, ma questa versione va benissimo è semplice

Attento che l'esercizo chiede un albero di double non int.

[fk16]

Scusa ma la funzione mi dovrebbe restituire un vettore, in questo caso la funzione che mi hai proposto restituisce un void. Come dovrei impostarla???? Grazie comunque del tuo aiuto.

[hamming_burst]

"fk16":Scusa ma la funzione mi dovrebbe restituire un vettore, in questo caso la funzione che mi hai proposto restituisce un void. Come dovrei impostarla???? Grazie comunque del tuo aiuto.

un po' di astrazione suvvia
ho scritto un po' velocemente ieri, forse non hai compreso ciò che ti ho proposto.

Il codice te lo ho "astratto" per farti capire cosa avveniva. Con "passaggio per riferimento" intendo di utilizzare questa tecnica (non te lo ho scritto nel codice esplicitamente...) oppure la tua soluzione con vettore che di per sè è passatto per riferimento, perciò il valore di ritorno è inutile (da qui il void).

Perciò il codice completo sarebbe:

passaggio per riferimento:

void conta(tree t, int* NS, int* ND){

     if(t!=NULL){
          conta(t->left,(*NS)++,ND);
          conta(t->right,NS,(*ND)++);
     }
}

che chiamerai avendo dichiarato due variabili nel tuo codice (es. nel main):

int NS = 0;
int ND = 0;
...
conta(t,&NS,&ND);

OPPURE utilizzando il vettore:

void conta(tree t, int* vect){ //void conta(tree t, int vect[]){ 

     if(t!=NULL){
          conta(t->left,vect[0]++);
          conta(t->right,vect[1]++);
     }
}

che chiamerai con:

int vect[2] = {0};
...
conta(t,vect);

cmq dalla tua domanda, mi sorge un dubbio:
sai che il vettore è passato per riferimento (è passato l'indirizzo di memoria) e non per valore (non è passato una copia di tutto il vettore)?