Visualizzazione dei risultati da 1 a 7 su 7
  1. #1
    Utente di HTML.it L'avatar di Ushas
    Registrato dal
    Aug 2010
    Messaggi
    11

    [c] Esercizio su alberi binari di ricerca

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

  2. #2
    Utente di HTML.it
    Registrato dal
    Jul 2008
    Messaggi
    1,326
    Perché fai tutto in una funzione? Non puoi crearti due funzioni separate per i due tipi di somma?
    every day above ground is a good one

  3. #3
    Utente di HTML.it L'avatar di Ushas
    Registrato dal
    Aug 2010
    Messaggi
    11
    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...

  4. #4
    Utente di HTML.it
    Registrato dal
    Jul 2008
    Messaggi
    1,326
    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.
    every day above ground is a good one

  5. #5
    Utente di HTML.it L'avatar di Ushas
    Registrato dal
    Aug 2010
    Messaggi
    11
    Ho risolto, riporto il frammento di codice relativo alla funzione somma:

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

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

  6. #6
    Utente di HTML.it
    Registrato dal
    Jul 2008
    Messaggi
    1,326
    Sicuro che funzioni? Hai fatto qualche prova?
    every day above ground is a good one

  7. #7
    Utente di HTML.it L'avatar di Ushas
    Registrato dal
    Aug 2010
    Messaggi
    11
    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!

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.