[C] Somma e media di un albero binario

scegli un altro forum

Indietro Ricarica Avanti

Autore

Discussione

00disaster00
Utente di HTML.it

Registrato il: Jul 2012

Provenienza:

Messaggi: 40

ICQ:

MSN:

Skype:

[C] somma e media albero binario

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
codice:

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

Segnala ad un moderatore | IP: Collegato | Permalink

05-07-2012 15:41

Clicca qui per inviare all'utente 00disaster00 un messaggio privato

Visualizza ulteriori messaggi scritti dall'utente 00disaster00

Aggiungi l'utente 00disaster00 alla tua lista degli utenti amici

Scara95
Utente di HTML.it

Registrato il: Jul 2009

Provenienza: Verona (provincia)

Messaggi: 1176

ICQ :

MSN :

Skype :

codice:

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
codice:

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).

__________________
"Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

Segnala ad un moderatore | IP: Collegato | Permalink

05-07-2012 21:15

Clicca qui per inviare all'utente Scara95 un messaggio privato

Visualizza ulteriori messaggi scritti dall'utente Scara95

Aggiungi l'utente Scara95 alla tua lista degli utenti amici

00disaster00
Utente di HTML.it

Registrato il: Jul 2012

Provenienza:

Messaggi: 40

ICQ :

MSN :

Skype :

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:

codice:

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???

Ultima modifica ad opera dell'utente 00disaster00 il 06-07-2012 alle 18:13

Segnala ad un moderatore | IP: Collegato | Permalink

06-07-2012 17:52

Scara95
Utente di HTML.it

Registrato il: Jul 2009

Provenienza: Verona (provincia)

Messaggi: 1176

ICQ :

MSN :

Skype :

codice:

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...

Citazione:

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...

__________________
"Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

Segnala ad un moderatore | IP: Collegato | Permalink

06-07-2012 20:34

00disaster00
Utente di HTML.it

Registrato il: Jul 2012

Provenienza:

Messaggi: 40

ICQ :

MSN :

Skype :

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

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

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

Segnala ad un moderatore | IP: Collegato | Permalink

07-07-2012 11:04

Scara95
Utente di HTML.it

Registrato il: Jul 2009

Provenienza: Verona (provincia)

Messaggi: 1176

ICQ :

MSN :

Skype :

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:
codice:

#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!

__________________
"Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

Segnala ad un moderatore | IP: Collegato | Permalink

07-07-2012 11:40