Visualizzazione dei risultati da 1 a 5 su 5
  1. #1

    chi mi dà un'occhiata

    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.

  2. #2

    scusate [C++]

    scusate per il mancato tag

  3. #3
    Utente di HTML.it L'avatar di DydBoy
    Registrato dal
    Jul 2005
    Messaggi
    165

    Re: chi mi dà un'occhiata

    Non l'ho testata ma la puoi mettere ricorsiva così :


    codice:
    #include <stdlib.h>
    
    
    typedef struct nodeDef
    {
      int Value;
      struct nodeDef *RNode;
      struct nodeDef *LNode;
    } treeNode;
    
    
    int SomNodo (treeNode *node,int TPos){
     
      if (TPos == 0) 
    	return node->Value;
    
      else 
        return 
              SomNodo(node->LNode,TPos-1) +SomNodo(node->RNode,TPos-1);
    
    }	
    			
    
    main()
    {
    	
    	treeNode *root;
    
    	
    	int H,k, Somma;
    	
    	H=10;
    	k=4;
    
        Somma=SomNodo(root,k);
        system("PAUSE");
        
    }

  4. #4
    Utente di HTML.it
    Registrato dal
    Jun 2005
    Messaggi
    117
    codice:
    #include <stdlib.h>
    
    
    typedef struct nodeDef
    {
      int Value;
      struct nodeDef *RNode;
      struct nodeDef *LNode;
    } treeNode;
    
    
    int SomNodo (treeNode *node,int TPos){
      if (node == NULL)
         return 0;
      if (TPos == 0) 
    	return node->Value;
    
      else 
        return 
              SomNodo(node->LNode,TPos-1) + SomNodo(node->RNode,TPos-1) + node->Value;
    
    }	
    			
    
    main()
    {
    	
    	treeNode *root;
    
    	
    	int H,k, Somma;
    	
    	H=10;
    	k=4;
    
        Somma=SomNodo(root,k);
        system("PAUSE");
        
    }

  5. #5
    Utente di HTML.it L'avatar di DydBoy
    Registrato dal
    Jul 2005
    Messaggi
    165
    Ah si avevo dimenticato il nodo radice e il controllo sull'albero più corto dei livelli da contare.Tnx.

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.