[C] Somma e media di un albero binario

[00disaster00]

Sto implementando le funzioni per la somma e per la media dei valori di un albero binario...
non riesco a far prendere solamente il primo elemento..come fare? Il codice è uguale a quello della visita simmetrica

double avg(NODO *a, double sum, int count)
{
  //if(a==NULL) return 0;
  if(a!=NULL)//else
  {
   avg(a->left, sum, count);
    sum++;
   printf("cicle %lf ",sum);
//   *sum+=a->value; *count++;
   avg(a->right, sum, count);
  }
//  else return 0.0;//*sum/ *count; 
}

Grazie in anticipo

[Scara95]

double sum(NODO *a) {
	if(a == NULL)
		return 0.;
	return a->value + sum(a->left) + sum(a->right);
}

int count(NODO *a) {
	if(a == NULL)
		return 0;
	return 1 + count(a->left) + count(a->right);
}

double avg(NODO *a) {
	if(a == NULL)
		return 0;
	return sum(a)/(double)count(a);
}

o

double avg(NODO *a) {
	if(a == NULL)
		return 0;
	double sum = 0.;
	int count = 0;
	_avg_support_f(a, &sum, &count);
	return sum/count;
}

void _avg_support_f(NODO *a, double *sum, int *count) {
	if(a == NULL)
		return;
	(*sum)+=a->value;
	(*count)+=1;
	_avg_support_f(a->left);
	_avg_support_f(a->right);
}

Può essere che ci sia qualche errore, non le ho provate...

Inoltre la prossima volta posta anche le strutture definite da te (NODO ad esempio).

[00disaster00]

L'ultimo codice (eccetto che c'erano le ricorsioni in cui mancavano i parametri) è perfetto...il problema è che dovrei farei una sola funzione che restituisca la media dei valori di un albero. Avevo anche pensato di farlo in modo non ricorsiva ma non saprei come...come potrei?? ..di seguito porto il codice della funzione ricorsiva da me scritta:

typedef struct nodo
{
 double value;
 struct nodo *right;
 struct nodo *left;
} NODO;

double avg(NODO *a, double *sum, int *count)
{
  if(a==NULL){ return 0;}
  else
     {
       *sum+=a->value; *count++;
       avg(a->left, sum, count);
       avg(a->right, sum, count);
     }
  return *sum/(*count);
}

penso che a rompere sia il caso banale o sia il return finale messo in maniera sbagliata
Ringrazio in anticipo per le risposte
PS: Nella funzione somma non sarebbe più opportuno mettere l'else prima del return???

[Scara95]

double avg1(NODO *a, double *sum, int *count)
{
  if(a==NULL)
  	return 0;
  (*sum) += a->value; 
  (*count)++;
  avg1(a->left, sum, count);
  avg1(a->right, sum, count);
  return (*sum)/(*count);
}

Mancavano tutte le parentesi...

L'operatore * ha precedenza più bassa degli altri operatori che hai usato e quindi devi usare le parentesi...

Nella funzione somma non sarebbe più opportuno mettere l'else prima del return???

Non cambia assolutamente nulla, se l'if si verifica avviene il return e si esce immediatamente dalla funzione, altrimenti si svolge normalmente la funzione; è una questione di stile, io preferisco non metterlo in quanto l'if delimita il caso base (quello dove si ferma la ricorsione) mentre dopo l'if c'è il corpo "normale" della funzione!
Inoltre senza l'else è leggermente più ottimizzabile perchè lasci al compilatore fare ciò che vuole col codice...

[00disaster00]

Grazie mille Scara95 ^.^...per il fatto di effettuarlo senza ricorsione avevo pensato di usare un while del tipo

while(a)
{
//prendo il valore e incremento il contatore
}

però non saprei come "girare" l'albero...

[Scara95]

E' un po' difficile attraversare tutti i nodi di un albero binario con un while inquanto ad ogni ciclo i nodi aumentano esponenzialmente!
L'unico modo sarebbe trasformare l'albero in una lista per poi attraversare linearmente la lista:

#include <malloc.h>
typedef struct LElement_s {
	double value;
	struct LElement_s *next;
} LElement;

typedef LElement * List;

List treeToList(NODO *a) {
	if(a == NULL)
		return NULL; // Lista vuota
	return concat(treeToList(NODO->left), concat(toList(a->value), treeToList(NODO->right));
}

List toList(double value) {
	List temp = (List)malloc(sizeof(LElement));
	temp->value = value;
	temp->next = NULL;
	return temp;
}

List concat(List a, List b) {
	if(a == NULL)
		return b;
	if(b == NULL)
		return a;
	List temp = a;
	while(temp->next != NULL)
		temp = temp->next;
	temp->next = b;
	return a;
}

Attento però che questa funzione non è molto efficente...

NB: Bisogna poi rilasciare la memoria degli elementi allocati!