[C] Esercizio: alberi binari di ricerca e somme

[Ushas]

"Scrivere un programma che legga da tastiera una sequenza di N interi strettamente
positivi e li inserisca in un albero binario di ricerca, nell’ordine in
cui vengono forniti in input.
Dato un nodo y, si definisce:
• Somma interna I(y): somma di tutte le chiavi contenute nei nodi
interni del sottoalbero radicato in y, escluse quindi le foglie discendenti
da y ed escluso y stesso se esso è una foglia.
• Somma delle foglie F(y): somma di tutte le foglie discendenti da y,
incluso y se esso è una foglia.
Contare i nodi y dell’albero per cui vale che I(y)maggiore o uguale di F(y) e
(I(y) − F(y)) mod 7 = 0.


Il mio problema è la funzione "somma"(indicata con --->), non ho ben chiara la ricorsione, quindi non so bene come scriverla.
Potete aiutarmi?

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

typedef struct _tree{
   int dato;
   struct _tree *sx;
   struct _tree *dx;
} tree;

tree *inserisciAlbero(tree *u, int e){
   tree *nodo=malloc(sizeof(tree));
   nodo->dato=e;
   nodo->sx=nodo->dx=NULL;

   if(u==NULL)
      return nodo;
   if(e<=u->dato)
      u->sx=inserisciAlbero(u->sx, e);
   else
      u->dx=inserisciAlbero(u->dx, e);
}

---> int somma(tree *u){
   if(u==NULL) return -1;

   int sommaint=0;
   int sommafog=0;
   int k;

   if((u->sx!=NULL)||(u->dx!=NULL))
      sommaint+=u->dato;
   if(u->sx!=NULL)
      sommaint=somma(u->sx);
   if(u->dx!=NULL)
      sommaint=somma(u->dx);
   if((u->sx==NULL)&&(u->dx==NULL))
      sommafog+=u->dato;

   k=sommaint-sommafog;

return k;
}

int ricerca(tree *u, int elem, int conta){
   if(u==NULL) return 0;
   int sommaint=0;
   int sommafog=0;

   if(u->dato==elem){
      int k=somma(u);
      if(k>=0 && k%7==0)
         conta++;
      return conta;
   }
   if(elem<u->dato){
      u=u->sx; return ricerca(u, elem, conta);
   }else{
      u=u->dx;
      return ricerca(u, elem, conta);
   }
}

int main(){
   int i, n, e, *a, conta=0;
   tree* u=NULL;

   scanf("%d", &n);
   if(n<=0) return 0;
   a=malloc(n*sizeof(int));

   for(i=0; i<n; i++){
      scanf("%d", &e);
      if(e<=0) return 0;
      u=inserisciAlbero(u, e);
      a[i]=e;
   }

   for(i=0;i<n;i++)
      conta=ricerca(u, a[i], conta);
   printf("%d\n",conta);

return 0;
}

Grazie!

[YuYevon]

Perché fai tutto in una funzione? Non puoi crearti due funzioni separate per i due tipi di somma?

[Ushas]

Originariamente inviato da YuYevon
Perché fai tutto in una funzione? Non puoi crearti due funzioni separate per i due tipi di somma?

Sì, solo che volevo evitare di scorrere l'albero una volta per la somma dei nodi interni e un'altra per la somma delle foglie...

[YuYevon]

Sì può fare anche con una sola funzione ma devi ricorrere a due puntatori a int in modo che la funzione possa calcolare entrambe le somme in contemporanea e restituirle al main(), dove poi potresti fare i calcoli richiesti.

[Ushas]

Ho risolto, riporto il frammento di codice relativo alla funzione somma:

int somma(tree *u, int sommaint, int sommafog){
   if(u==NULL) return -1;

   int k;

   if((u->sx!=NULL)||(u->dx!=NULL))
      sommaint+=u->dato;
   if(u->sx!=NULL)
      sommaint=somma(u->sx, sommaint, sommafog);
   if(u->dx!=NULL)
      sommaint=somma(u->dx, sommaint, sommafog);
   if((u->sx==NULL)&&(u->dx==NULL))
      sommafog+=u->dato;

   k=sommaint-sommafog;

return k;
}

Inoltre, poiché l'albero può contenere elementi ripetuti, ho associato ad ogni nodo un campo "mark", che all'inizio è a 0; il primo caso della funzione ricerca è quindi modificato così:

 if((u->dato==elem)&&(u->mark==0)){
      u->mark=1;
      int k=somma(u,0,0);
      if(k>=0 && k%7==0)
         conta++;
      return conta;
   }

[YuYevon]

Sicuro che funzioni? Hai fatto qualche prova?

[Ushas]

Avevo degli input (con relativi output) dati dal professore, con quelli che ho provato funziona! Me ne inventerò degli altri per continuare a testare

Grazie comunque, se per caso non dovesse funzionare provo come hai detto te!