PDA

Visualizza la versione completa : [C] Esercizio: alberi binari di ricerca e somme


Ushas
30-01-2011, 16:13
"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
30-01-2011, 21:09
Perché fai tutto in una funzione? Non puoi crearti due funzioni separate per i due tipi di somma?

Ushas
30-01-2011, 23:13
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
30-01-2011, 23:36
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
30-01-2011, 23:41
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
30-01-2011, 23:56
Sicuro che funzioni? Hai fatto qualche prova?

Ushas
30-01-2011, 23:59
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!

Loading