C - Somma nodi livello k

[gabama]

Ho creato questa funzione ,dovrei modificarla per fargli ritornare la somma dei nodi a livello k
ho elemento (int) e 2 puntatori ai figli

void printLevel(Albero a, int currentLevel, int level){
    
    if(a == NULL)
        return NULL;

    if(currentLevel == level)  {


         inserisci(a->inf,&l);

    }
    printLevel(a -> sinistro, currentLevel + 1, level);
    printLevel(a -> destro, currentLevel + 1, level);
}

ovviamente dovrei cambiare in int eccetera,ma come faccio a fargli sommare gli elementi a una certa profondità,qui semplicemente li stampa
Come posso fare?
Grazie in anticipo

[MrX87]

bhè provo a dare una risposta anche senza provare il codice; da come ho capito bisogna fare la somma di tutti i nodi che sono al livello k...come hai fatto tu potrebbe essere un inizio...come hai scritto tu nella funzione, dovrebbe essere una specie di visita InOrder, e potrebbe essere una soluzione facendo:

void printLevel(Albero a, int currentLevel, int level, int* somma){
    
    if(a == NULL || currentLevel > level)
        return NULL;

    if(currentLevel == level)  {
         (*somma) += a->valore;
    }
    printLevel(a -> sinistro, currentLevel + 1, level, &somma);
    printLevel(a -> destro, currentLevel + 1, level, &somma);
}

In questo modo teoricamente al termine della ricorsione, avendo visitato tutto l'albero, dovresti avere in somma la somma dei nodi al livelli "level"! provalo e fammi sapere...

[gabama]

allora

void stampalivk(Albero a, int currentLevel, int level, int* somma){

    if(a == NULL || currentLevel > level)
        return NULL;

    if(currentLevel == level)  {
         printf("\n %d",(*somma) += a->inf);
    }
    stampalivk(a -> sinistro, currentLevel + 1, level, &somma);
    stampalivk(a -> destro, currentLevel + 1, level, &somma);
}

invocata da
int sk=0;
stampalivk(a,0,2,&sk);
va in errore,ho lasciato dietro qualcosa?

[ignaziodeblasi]

Dando un occhiata al codice non posso fare altro che notare queste due righe:

stampalivk(a -> sinistro, currentLevel + 1, level, &somma);
stampalivk(a -> destro, currentLevel + 1, level, &somma);

Strano che non hai ricevuto nessun avviso da parte del compilatore quando l'hai compilato;
intendo dire che l'ultimo argomento della funzione stampalivk è un int*;
la variabile somma dentro la funzione è già di questo tipo, quindi non capisco perchè, quando fai le due chiamate sopra, passi alla funzione l'indirizzo(in questo modo passi una variabile di tipo int** ).
modificherei queste due righe con:

stampalivk(a -> sinistro, currentLevel + 1, level, somma);
stampalivk(a -> destro, currentLevel + 1, level, somma);

CIAO

[MrX87]

a variabile somma dentro la funzione è già di questo tipo, quindi non capisco perchè, quando fai le due chiamate sopra, passi alla funzione l'indirizzo(in questo modo passi una variabile di tipo int** ).
modificherei queste due righe con:
codice:

stampalivk(a -> sinistro, currentLevel + 1, level, somma);
stampalivk(a -> destro, currentLevel + 1, level, somma);

bhè hai perfettamente ragione...perdonatemi per l'errore...comunque provo personalmente il codice su compilatore per vedere se funziona correttamente e vi faccio sapere!

[MrX87]

apposto...ho controllato il codice al compilatore...ho scritto un pò tutto...e dovrebbe funzionare così:

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

typedef struct albero_binario {
        int val;
        struct albero_binario *left;
        struct albero_binario *right;
} bst;
        
bst* insert ( bst* top, int val );        
void printLevel( bst* a, int currentLevel, int level, int* somma);

int main ()
{
    bst* head;
    int val;
    int somma=0;
    
    
    head = NULL;
    
    while ( val != 0 ) {
          
          printf ("Inserire valore (0-termina): ");
          scanf  ("%d", &val);
          
          if ( val != 0 ) 
             head = insert ( head, val );
    }    
             
    printLevel ( head, 0, 1, &somma );      
    
    printf ("La somma del livello e: %d\n", somma);
    
    system ("pause");
    return 1;
}

bst* insert ( bst* top, int val ) 
{
    bst *pNew;
    
    if ( top == NULL ) {
       pNew = (bst*)malloc(sizeof(struct albero_binario));
       pNew->val = val;
       pNew->left = NULL;
       pNew->right = NULL;
       top = pNew;
    }
    else {
         if ( val > top->val ) {
              top->right = insert ( top->right, val );
         }
         else top->left = insert ( top->left, val );
    }
    return top;
}
    
void printLevel( bst* a, int currentLevel, int level, int* somma)
{
    
    if(a == NULL || currentLevel > level)
        return;

    if(currentLevel == level)  {
         (*somma) += a->val;
    }
    printLevel(a->left, currentLevel+1, level, somma);
    printLevel(a->right, currentLevel + 1, level, somma);
    return;
}

fatemi sapere ancora se c'è qualcosa che non quadra. e scusatemi per l'errore di prima, ma è dovuto un pò alla distrazione di aver scritto il codice senza provarlo!

[gabama]

ci mancherebbe ancora,MrX87,sei stato troppo gentile a cercare una soluzione al mio problema
Non mi è chiara una cosa però
se io inserisco 1 4 7 3 9
l' albero sarebbe
1
4 7
3 9
giusto?

come somma del livello 2 non dovrebbe essere 12 (3+9)?
Se non sbaglio l' implementazione di un albero può essere fatta in vari modi,tra cui con una lista,è questo il caso (come mi hai creato)?

Spero di non aver detto una stupidaggine

Grazie ancora

[MrX87]

eh si ci sono varie implementazioni...in questo caso io ho inserito secondo le regole del bst...albero binario di ricerca! quindi inserendo 1 4 7 3 9 si ha:
1
4 (figlio dx)
3 7
9 (figlio dx di 7)
se vuoi inserire senza un ordine particolare devi fare delle piccole modifiche alla funzione di inserimento!

[gabama]

per modificare il codice in modo da non aver questa condizione per l' inserimento,devo eliminare la condizione
"if ( val > top->val )"?
e mettere in caso il top non sia vuoto e sinistro non sia vuoto vada a destra e viceversa?

[MrX87]

per modificare il codice in modo da non aver questa condizione per l' inserimento,devo eliminare la condizione
"if ( val > top->val )"?
e mettere in caso il top non sia vuoto e sinistro non sia vuoto vada a destra e viceversa?

Si in realtà non basta proprio togliere quell'if ma bisogna cambiare solo il controllo da fare! posto sotto il codice della funzione di inserimenti modificata per inserire senza le regole del bst ma in un normale albero binario.

bst* insert ( bst* top, int val )
{
    bst *pNew;

    if ( top == NULL ) {
       pNew = (bst*)malloc(sizeof(struct albero_binario));
       pNew->val = val;
       pNew->left = NULL;
       pNew->right = NULL;
       top = pNew;
    }
    else {
        if ( top->right == NULL )
            top->right = insert ( top->right, val );
        else    top->left = insert ( top->left, val );
    }
    return top;
}