Pages: [1] 2   Go Down
Print
Author Topic: metodo conta altezza albero  (Read 2814 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Gpeppe69
Apprendista Forumista
**
Offline Offline

Posts: 294



« on: 22-05-2012, 17:00:31 »

salve ragazzi ma vorrei sapere una cosa sul metodo di oggi per calcolare l'altezza di un albero

Code:
public int conta_altezza(BSTNodo a)
{

if(a.root==null)return -1;
else
{
int i=Math.max(conta_altezza(a.root.left));
Math.max(conta_altezza(a.root.right));

return 1+i;
}

per me il metodo è sbagliato perchè ogni volta che richiama se stesso crea sempre la i che varrà sempre 1 e poi non capisco perchè ad i non copia il valore della seconda chiamata Huh?
Logged
Nessuno
Apprendista Forumista
**
Offline Offline

Posts: 204



« Reply #1 on: 22-05-2012, 18:10:41 »

per il calcolo dell'altezza in un albero in mod. ricorsiva parti dalla radice...e come segue:
Code:
public int height (Tnode r){

if( r==null || ( r.getRight() && r.getLeft()==null ) ) //controllo se "r" è una foglia..o l'albero è vuoto come [b]caso base[/b]
 return 0;
if( height(r.getRight() ) > height( r.height(r.getLeft() )
 return (1+ height (r.getRight() ) );
else
 return (1+ height(r.getLeft() ) );
}

..ma oggi ha spiegato qualcos'altro oltre il calcolo dell'altezza di un albero, oggi a lezione?
Logged

Sorridi anche se il tuo sorriso è triste, perchè più triste di un sorriso triste c'è la tristezza di non saper sorridere.

::Jim Morrison::
Gpeppe69
Apprendista Forumista
**
Offline Offline

Posts: 294



« Reply #2 on: 22-05-2012, 18:20:08 »

scusa ma questo metodo funziona ? è secondo te quello che ho scritto io funziona ? quel metodo l'ha fatto un ragazzo oggi alla lavagna l'ho copiato xke il prof. ha detto che funziona poi oggi l'ho guardato bene e sinceramente per me non ha nessun senso logico, oggi il prof. mi ha un pò confuso è non ha fatto capire bene come procedere  nel calcolare l'altezza, oltre a questo abbiamo provato a fare il metodo che trova se l'albero è bilanciato  ma sempre ha fatto una confusione pazzesca
Logged
Nessuno
Apprendista Forumista
**
Offline Offline

Posts: 204



« Reply #3 on: 22-05-2012, 18:40:00 »

nel metodo postato la condizione a.root == null , controlla solo se l'albero è vuoto ...a quanto ne so io bisogna che ci sia pure una condizione che dica se il nodo che passi ricorsivamente sia foglia oppure no ( la cond. "&&" ), ovvero il "caso base", che ritorna zero se arrivi alla fine.(quindi il metodo iniziale non penso funzioni..per ora non l'ho provato)
Prova con un albero binario di solo 4 nodi e vedi il meccanismo che viene eseguito ricorsivamente...(non è difficile)
Alcune chiamate ricorsive vengono eseguite anche se successivamente fallisce la condizione ( e questo penso che sia uno svantaggio ) per poi passare alla condizione successiva..che è quella verificata.
Logged

Sorridi anche se il tuo sorriso è triste, perchè più triste di un sorriso triste c'è la tristezza di non saper sorridere.

::Jim Morrison::
Gpeppe69
Apprendista Forumista
**
Offline Offline

Posts: 294



« Reply #4 on: 22-05-2012, 19:12:10 »

ma vorrei capire quando confronti nell'if  perchè non da errore se tu stai confrontando 2 riferimenti è questo quello che mi fa confondere ?
Logged
Carghaez
Matricola
*
Offline Offline

Gender: Male
Posts: 40


"Love is 0."


« Reply #5 on: 22-05-2012, 19:36:46 »

Code:
public int altezza()
{
     return altezza(root);
}

private int altezza(IntBST_Node p)
{
         if(p == null) return -1;
         return Math.max( altezza(p.left), altezza(p.right) ) +1;

}

Questo è il metodo più banale che è stato scritto alla lavagna per calcolare l'altezza di un albero.

Il metodo che hai citato qui, copiato male dalla lavagna, era quello dove si imponeva il passaggio di un albero al posto del classico passaggio del nodo, dove l'assegnamento ad i era:
int i = Math.max( altezza( new BST(nodo destro) ),altezza( new BST(nodo sinistro)) );
return i+1;

Questo per due motivi principalmente: il primo era perchè il proff non aveva niente da fare oltre a complicare l'algoritmo inutilmente xD il secondo perchè noi possiamo riferirci ad ogni nodo come un sottoalbero e quindi possiamo procedere ricorsivamente trasformando (il proff aveva "Mal" suggerito di fare un cast di tipo ad albero o.o) il nodo in un vero e proprio albero temporaneo.

Spero di essere stato chiaro  cry  

ps: la i si può risparmiare scrivendo il tutto nel return.
« Last Edit: 22-05-2012, 19:46:41 by Carghaez » Logged

"non posto per risparmiare spazio sui server del DMI"
{cit.}
Sassofonix
Matricola
*
Offline Offline

Posts: 78


« Reply #6 on: 22-05-2012, 21:25:21 »

Carghaez proprio così!!!:) Gpeppe69 vedi che ti sei confuso tu a copiare la lavagna perchè il metodo giusto è quello scritto da Carghaez!!!
Logged
Sassofonix
Matricola
*
Offline Offline

Posts: 78


« Reply #7 on: 22-05-2012, 21:28:23 »

salve ragazzi ma vorrei sapere una cosa sul metodo di oggi per calcolare l'altezza di un albero

Code:
public int conta_altezza(BSTNodo a)
{

if(a.root==null)return -1;
else
{
int i=Math.max(conta_altezza(a.root.left));
Math.max(conta_altezza(a.root.right));

return 1+i;
}

per me il metodo è sbagliato perchè ogni volta che richiama se stesso crea sempre la i che varrà sempre 1 e poi non capisco perchè ad i non copia il valore della seconda chiamata Huh?


Che poi al Math.pow si passano 2 int no uno!! Se no di cosa fai il massimo di un numero solo???O.o
 
Logged
Carghaez
Matricola
*
Offline Offline

Gender: Male
Posts: 40


"Love is 0."


« Reply #8 on: 22-05-2012, 21:40:51 »

Code:
private int altezza(IntBST_Node p)
{
if(p == null) return -1;
int HL = altezza(p.left);
int HR = altezza(p.right);
return 1 + HR - ((HR-HL) & (HR-HL)>>31);
}

Una chicca per chi non vuole usare condizioni Wink Provatelo e vedrete che funziona!
Logged

"non posto per risparmiare spazio sui server del DMI"
{cit.}
Sassofonix
Matricola
*
Offline Offline

Posts: 78


« Reply #9 on: 22-05-2012, 21:55:36 »

Code:
private int altezza(IntBST_Node p)
{
if(p == null) return -1;
int HL = altezza(p.left);
int HR = altezza(p.right);
return 1 + HR - ((HR-HL) & (HR-HL)>>31);
}

Una chicca per chi non vuole usare condizioni Wink Provatelo e vedrete che funziona!

Non riesco a capire cosa fa nel return 1 + HR - ((HR-HL) & (HR-HL)>>31);  testate
Logged
Carghaez
Matricola
*
Offline Offline

Gender: Male
Posts: 40


"Love is 0."


« Reply #10 on: 22-05-2012, 21:58:03 »

Code:
private int altezza(IntBST_Node p)
{
if(p == null) return -1;
int HL = altezza(p.left);
int HR = altezza(p.right);
return 1 + HR - ((HR-HL) & (HR-HL)>>31);
}

Una chicca per chi non vuole usare condizioni Wink Provatelo e vedrete che funziona!

Non riesco a capire cosa fa nel return 1 + HR - ((HR-HL) & (HR-HL)>>31);  testate

gli operatori  sono l'and logico e lo shift (oltre somma e differenza) e quello che fa non è altro che restituire il massimo tra HR e HL +1 Cheesy
Logged

"non posto per risparmiare spazio sui server del DMI"
{cit.}
Gpeppe69
Apprendista Forumista
**
Offline Offline

Posts: 294



« Reply #11 on: 22-05-2012, 22:03:41 »

per quanto riguarda la copia del metodo hai ragione forse ho copiato male, perchè infatti ho capito subito che mancava un parametro per questo mi sembrava strano cmq per quanto riguarda l'ultimo commento ci Charz.. non ho neanche io cosa fai con quel shift etc.....  se puoi spiegarti molto MEGLIO grazie  cmq grazie a tutti d'avermi risposto
Logged
Nessuno
Apprendista Forumista
**
Offline Offline

Posts: 204



« Reply #12 on: 23-05-2012, 08:48:58 »

ma vorrei capire quando confronti nell'if  perchè non da errore se tu stai confrontando 2 riferimenti è questo quello che mi fa confondere ?

Il confronto nell' if si riferisce alle altezze (interi) ritornate...(poichè l'unica cosa che restituiamo all'uscita da ogni chiamata ricorsiva sono interi)

..spero abbia capito Smiley

P.S. ...cosa intendi con il "metodo del topic", non riesco a trovarlo tra le slides ?..
« Last Edit: 23-05-2012, 09:04:45 by Nessuno » Logged

Sorridi anche se il tuo sorriso è triste, perchè più triste di un sorriso triste c'è la tristezza di non saper sorridere.

::Jim Morrison::
Gpeppe69
Apprendista Forumista
**
Offline Offline

Posts: 294



« Reply #13 on: 23-05-2012, 10:36:42 »

lo so che sono altezze ma alla chiamata ricorsiva tu passi un riferimento !! è non un intero che è diverso almeno in java in C non è così , cmq fammi capire , quando ritorna il riferimento fa un cast ad un intero ? no ?
Logged
Nessuno
Apprendista Forumista
**
Offline Offline

Posts: 204



« Reply #14 on: 23-05-2012, 12:33:21 »

lo so che sono altezze ma alla chiamata ricorsiva tu passi un riferimento !!
...esatto...
-> height (r.getRight() )
Quote
quando ritorna il riferimento fa un cast ad un intero ? no ?

-> return (1+ height (r.getRight() ) );
...quando torna un riferimento fa un cast?.allora, il metodo + interno r.getRight(), si torna un riferimento..che poi + esternamente si ha: height(riferimento)...questo poi torna un intero (che sarebbe l'altezza del nodo "riferito"...) che poi a seguire + esternamente è:
 return (1+altezza(riferimento del nodo) )...
dov'è che dovrebbe esserci il cast ad un intero? ..forse non sto capendo io :O
« Last Edit: 23-05-2012, 12:35:07 by Nessuno » Logged

Sorridi anche se il tuo sorriso è triste, perchè più triste di un sorriso triste c'è la tristezza di non saper sorridere.

::Jim Morrison::
Pages: [1] 2   Go Up
Print
Jump to: