devo rispondere ad una domanda del tipo: ( chi mi darebbe una mano ad avere lo stesso risultato diminuendo le righe di codice?)
DOMANDA
Si consideri un albero binario di altezza h. Ciascun nodo contiene solamente un valore
intero ed i puntatori ai figli. Si scriva un algoritmo (in pseudocodice oppure codice C++)
che data la radice dell’albero ed un valore k<=h restituisca la somma dei nodi
appartenenti ai primi k livelli dell’albero.
Nota: la struttura dell’albero fornito in ingresso alla funzione non può essere modificata.
Si determini la complessità dell’algoritmo proposto.
io ho risposto così:
#include <iostream>
#include <stdlib.h>
struct Nodo{
int Valore;
Nodo *RNodo;//il nostro Ramo Dx
Nodo *LNodo;//il nostro Ramo Sx
};
int SomNodo (Nodo *Foglia,int TPos);
int main()
{
int H,k, Somma;
H=10;
k=4;
Nodo *Root;
Somma=SomNodo(Root,k);
system("PAUSE");
return 0;
}
int SomNodo (Nodo *Foglia,int TPos){
int TSomma;
TPos--; //sono a un livello piuù basso
if(TPos>=0){//mi accerto di non essere nella condizione 0 = k
if(Foglia->RNodo!=NULL){
TSomma=TSomma+SomNodo(Foglia->RNodo, TPos);
}
if(Foglia->LNodo!=NULL){
TSomma=TSomma+SomNodo(Foglia->RNodo, TPos);
}
}
TSomma=TSomma+Foglia->Valore;//sommo il valore della foglia
return TSomma; //ho ottenuto il valore
}
/*
La funzione , o per meglio dire la sua complessità dipende dall’altezza dell’albero. Per cui per ottenere il valore finale dovremo scorrere tutto l’albero.