"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?
codice:
#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!