Forum Informatica Unict

LAUREA TRIENNALE (D.M. 270/04) => Programmazione 2, 9 CFU => Topic started by: Alex_47 on 09-05-2009, 16:30:57



Title: come si implementa "isRoot"?
Post by: Alex_47 on 09-05-2009, 16:30:57
Qualcuno sa suggerirmi qualcosa su come implementabi i metodoi isRoot e isLeaf? Inoltre vede essere implementato nella classe nodo oppure albero?


Title: Re:come si implementa "isRoot"?
Post by: Alex_47 on 09-05-2009, 16:58:15
Come non detto , sono riuscito a farli da solo e vi posto anche le soluzioni...

Code:
public boolean isLeaf(int val)
{
Nodo p = root;
while(p != null)
{
if(val == p.key)
{
return isLeaf(p);
}
else
{
if (val < p.key) p = p.left;
else
    {
    p = p.right;
    }
}
}
return false;

}

public boolean isLeaf(Nodo p)
{
return ((p.right==null)&&(p.left==null));
}





public boolean isRoot(int val)
{
Nodo p = root;
while(p != null)
{
if(val == p.key)
{
return isRoot(p);
}
else
{
if (val < p.key) p = p.left;
else
    {
    p = p.right;
    }
}
}
return false;
}

public boolean isRoot(Nodo p)
{
return (p==root);

}




mentre qua vi public parent()

Code:
public Nodo parent(int val)
{
Nodo p = root;
Nodo q = root;
while(p != null)
{
if(val == p.key)
{
if(p==root)
{
return null;
}
else
{
return q;
}
}
else
{
if (val < p.key)
{
q = p;
p = p.left;
}
else
    {
    q = p;
    p = p.right;
    }
}
}
return null;
}


Title: Re:come si implementa "isRoot"?
Post by: ɹǝǝuıƃuǝsɹǝʌǝɹ on 09-05-2009, 17:02:40
Visto che prima che tu postassi da te la risposta avevo scritto un po' e non mi va di buttare un messaggio esplicativo interessante, riporto comunque la mia risposta:

Come suggerisce già Giovi89 in quest'altro post (http://forum.sdai.unict.it/index.php?topic=2619.msg19883#msg19883) (ma tu non potevi averlo letto perché è stato postato solo 1 minuto dopo, d'oh!  :boh), i metodo isLeaf e isRoot si applicano sicuramente ai nodi, ma rispetto ad un albero.

Cioè il soggetto delle domande "è una foglia" e "è la radice" è sicuramente "il nodo".
Tuttavia il nodo in sé non trasporta alcuna informazione di questo tipo riguardo sè stesso.

Bisogna chiedere ad un albero, se, per tale dato albero, il soggetto "nodo" è una foglia oppure una radice.

Tendenzialmente, inserirei tali metodi nella classe Albero, ma potrebbero, seguendo un'altra logica equivalente ma da un altro punto di vista, essere inseriti nella classe Nodo.

È chiaro che in entrambi i casi, bisogna passare al metodo un riferimento all'oggetto di tipo diverso:
  • se inserisco i metodi nella classe Albero, dovrò passare un nodo nel metodo;
  • se inserisco i metodi nella classe Nodo, dovrò passare un Albero nel metodo;

Inoltre possiamo fare alcune considerazioni collaterali:
  • un nodo è sempre sicuramente radice di un albero: basta considerare un albero in cui la radice sia questo nodo (anche se tale albero potrebbe non esistere come istanza indipendente);
  • un nodo è foglia se non ha figli (quindi non serve propriamente il riferimento ad Albero): tuttavia non è detto che un nodo (foglia o meno) faccia parte di un albero istanziato indipendentemente;

 .ciaociao