Pages: [1]   Go Down
Print
Author Topic: Esercizi  (Read 732 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« on: 15-05-2009, 10:27:48 »

Salve ragazzi sto facendo un di esercizi dell'esercitazione alberi e ho fatto quello che faceva vedere se l'albero era bilanciato oppure no, qua c'è il codice...

Code:
public boolean isBalanced(int k)
{
Nodo q = root;
Nodo p = root;
int sn=0;
int dn=0;

while((p!= null)&&(q!= null))
{
if(q.left != null)
{
q = q.left;
sn++;
}
else
{
if(sn>0)
{
q=q.right;
sn++;
}
}

if(p.right != null)
{
p = p.right;
dn++;
}
else
{
if(dn >0)
{
p=p.left;
dn++;
}
}

if(((sn-dn) == k)||((sn-dn) == 0 )) return true;
}

return false;



}

anche se l'ho fatto in maniera diversa dall'esercizio originale ovvero
Code:
 Esercizio 15 - Estendere la classe BSTree
aggiungendo il metodo
public boolean isBalanced ( int k )
che restituisce true se l'albero è k-bilanciato, cioè
ogni nodo n, detti sn
e dn
le profondità rispettivamente
del sottoalbero sinistro e destro, vale | sn
-
dn| <= k.

cosa vuole dire con k nodi bilanciati?
Logged
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


File reality.sys corrupted, Reboot Universe? Y/N


« Reply #1 on: 17-05-2009, 10:05:35 »

Quote
cosa vuole dire con k nodi bilanciati?
è spiegato nel testo dell'esercizio!!significa che per ogni nodo la differenza di profondità tra il sottoalbero destro e il sottoalbero sinistro non deve superare k!
io l'ho fatto così!
Code:
public boolean iskBalanced(int k)
{
return iskBalanced(k,root);
}
private boolean iskBalanced(int k,NodoBT p)
{
if(p==null)
return true;
else
return (iskBalanced(k,p.left)&&iskBalanced(k,p.right)&&(Math.abs(getHeight(p.left)-getHeight(p.right))<=k));
}
Logged

L'odrine delle lttere dnetro una praorla non è ipmortatne, la sloa cosa ipmortatne è che la pmria e l'utlima ltteera sinao nel potso giutso. Il rseto può essree in un dsiodrine più totlae e voi ptoerte smerpe lggeree sneza porblmea.
Pages: [1]   Go Up
Print
Jump to: