Newsgroup: it.comp.lang.c
Titolo: ALBERI E FOGLIE

Salve a tutta la NG,
ragazzi ho un problemino, non riesco a fare una funzione che datole in input
un albero binario mi restituisca il numero di foglie contenuto in esso, mi
date una mano?
Grazie 1000

 ha scritto nel messaggio
news:bt9Ra.179143$Ny5.5...@twister2.libero.it...

Devi fare una semplice funzione di visita che nel caso base della
riscorsione (in nodo non ha figli) incrementi una variabile di 1.
Ciao

 wrote

int ContaNodi(nodo *ptr)
{
    if(ptr)
          return (Conta(ptr->left) + Conta(ptr->right) + 1);
    else
         return 0;
}
oppure per le foglie:
int ContaFoglie(nodo *ptr)
{
    int ret=0;
    if(ptr){
        if((ptr->left==NULL)&&(ptr->right==NULL)){
            ret = 1;
        }else{
            ret = (ContaFoglie(ptr->left) + ContaFoglie(ptr->right));
        }
    }
    return ret;
}
Ovviamente dovrai riadattare il codice a seconda della struttura albero che
usi.
Tommy

 wrote
Ovviamente nel post precedente, dove ho scritto:
int ContaNodi(nodo *ptr)
{
    if(ptr)
          return (Conta(ptr->left) + Conta(ptr->right) + 1);
    else
         return 0;
}
la riga:
 return (Conta(ptr->left) + Conta(ptr->right) + 1);
deve essere:
 return (ContaNodi(ptr->left) + ContaNodi(ptr->right) + 1);
(per chi avesse letto solo questo post, questa funzione conta i nodi, quella
per le foglie e' presente nell'altro post!)
Tommy

 incrementi una variabile di 1.
Il vantaggio di questa tua soluzione e' la semplicita'. E' la soluzione
immediata a cui tutti pensano.
Lo svantaggio e' che usi una variabile globale..... E questo e' male. (e
pure cercare di non usarne una globale porta a codice "cattivo").
Il vantaggio della funzione che ho postato:
int ContaFoglie(nodo *ptr)
{
    int ret=0;
    if(ptr){
        if((ptr->left==NULL)&&(ptr->right==NULL)){
            ret = 1;
        }else{
            ret = (ContaFoglie(ptr->left) + ContaFoglie(ptr->right));
        }
    }
    return ret;
}
e' che non usa variabili globali, mentre seguendo il tuo consiglio ottieni
qualche cosa tipo:
void ContaFoglie2(nodo *ptr)
{
    if(ptr){
        if((ptr->left==NULL)&&(ptr->right==NULL)){
            ++global_var;
        }
        ContaFoglie2(ptr->left);
        ContaFoglie2(ptr->right);
    }
}
e come vedi sei "costretto" ad utilizzare le variabili globali!
Ci sono vari svantaggi nella seconda implementazione:
- il numero non e' ritornato dalla funzione, ma piuttosto la funzione setta
una variabile,
quindi non puoi fare:
n_foglie=ContaFoglie(tree);
ma devi invece fare:
ContaFoglie2(tree);
n_foglie=global_var;
- In secondo luogo, una seconda chiamata a ContaFoglie2 non darebbe il
risultato giusto, bisognerebbe prima azzerare global_var:
global_var=0;
Per non usare le variabili globali uno sarebbe tentato ad utilizzare una
variabile statica, ma questo rende piu' difficile riportarla a 0.
Per risolvere il problema che la funzione non ritorna il numero di foglie
uno sarebbe tentato di ritornare sempre il valore di global_var, ma questa
soluzione e' davvero poco elegante.
Credo quindi che la tua soluzione, per quanto immediata non sia la piu'
pulita.
Tommy

 n_foglie=global_var;
e cosi' puoi fare:
ContaFoglie3(my_var, tree);
vantaggi? e' tail recursive (si dice cosi'?) ovvero quando arriva
in fondo allo stack dlle chiamate ricorsive ha finito l'elaborazione.
-- 
mattia
-- 
Posted via Mailgate.ORG Server - 
http://www.Mailgate.ORG

 in fondo allo stack dlle chiamate ricorsive ha finito l'elaborazione.
Uhmm, sicuro che sia cosi' come lo dici tu?
Io mi ricordavo che nella ricorsione di coda l'ultima operazione di una
chiamata ricorsiva fosse l'unica chiamata ricorsiva e dopo di questa ci
fosse solo la return.
Questa e' vantaggiosa perche' e' facile trasformarla in iterativa (senza
dover ricorrere ad uno stack di supporto), cosa che *probabilmente* sara'
necessaria nella ricorsione di coda.
-- 
Mox
"Trust the programmer."
"Don't prevent the programmer from doing what needs to be done."
"Keep the language small and simple."
"Provide only one way to do an operation."

 in fondo allo stack dlle chiamate ricorsive ha finito l'elaborazione.
Il vantaggio di essere tail recursive e' che la ricorsione riesce ad essere
evitata, l'optimiser se e' buono, fa il suo lavoro e trasforma la ricorsione
in iterazione....
La tua funzione pero' non e' tail recursive e non riesce ad essere
ottimizzata!
Questo te lo dimostro disassemblando l'implementazione corretta della tua
fuzione (con puntatore):
=========
:00401000 56                      push esi
:00401001 8B74240C                mov esi, dword[esp+0C]
:00401005 85F6                    test esi, esi
:00401007 742C                    je 00401035
:00401009 57                      push edi
:0040100A 8B7C240C                mov edi, dword[esp+0C]
:0040100E 8BFF                    mov edi, edi
---------
:00401010 8B4604                  mov eax, dword[esi+04]
:00401013 85C0                    test eax, eax
:00401015 7507                    jne 0040101E
:00401017 8B4E08                  mov ecx, dword[esi+08]
:0040101A 85C9                    test ecx, ecx
:0040101C 7414                    je 00401032
---------
:0040101E 50                      push eax
:0040101F 57                      push edi
:00401020 E8DBFFFFFF              call 00401000
:00401025 8B7608                  mov esi, dword[esi+08]
:00401028 83C408                  add esp, 00000008
:0040102B 85F6                    test esi, esi
:0040102D 75E1                    jne 00401010
:0040102F 5F                      pop edi
:00401030 5E                      pop esi
:00401031 C3                      ret
---------
:00401032 FF07                    inc dword[edi]
:00401034 5F                      pop edi
---------
:00401035 5E                      pop esi
:00401036 C3                      ret
Questo e' un codice prodotto da compilatore + optmiser.
Come vedi l'inizio della funzione e' 401000 e poi all'indirizzo 401020 hai
un call 401000, beh, questa e' la chiamata ricorsiva!  Quindi la ricorsione
non e' sparita per nulla!
In pratica non e' tail recursive nel vero senso della parola e la maggior
parte dei compilatori C (se non tutti) non ti toglieranno la ricorsione!
Tommy

 Uhmm, sicuro che sia cosi' come lo dici tu?
ehrm... no... :)
devo ammettere che la tail recursion non e' un concetto che mi e' ancora
particolarmete chiaro... e gia' grazie a questo post la matassa si 
sta sbrogliando.


 parte dei compilatori C (se non tutti) non ti toglieranno la ricorsione!
yup!
grazie mille per la chiarezza
-- 
mattia
PS: scusate se ho *segato* troppo testo dai post precedenti ma questo
maledetto 
mailgate.org
 continua a rifiutarmi il messaggio


 maledetto 
mailgate.org
 continua a rifiutarmi il messaggio
No, anzi forse e' meglio cosi'!
Tommy

 pure cercare di non usarne una globale porta a codice "cattivo").
No, ti sbagli. Non intedevo usare una variabile globale. Ciao

 No, ti sbagli. Non intedevo usare una variabile globale. Ciao
ok, ho frainteso allora.