Pages: 1 [2]   Go Down
Print
Author Topic: Alberi e metodi  (Read 6741 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Giovi89
Apprendista Forumista
**
Offline Offline

Posts: 273


« Reply #15 on: 09-05-2009, 12:43:34 »

Salve Ragazzi ho provato a implementare sia la cancellazione per fusione che per sostituzione, vi posto entrambe però non mi riesce la seconda....nn so perchè mi stampa 2 volte il nodo del predecessore, qualcuno potrebbe correggermelo? Grazie in anticipo...
Code:
//CANCELLAZIONE PER FUSIONE
public void canc1(int a) throws Exception
{
if(search(a)==null)
throw new Exception("nodo con valore inesistente!");
else if(IsLeaf(search(a)))
{
if(getParent(a).getInfo()<a)
getParent(a).setRight(null);
else
getParent(a).setLeft(null);
}
else if(search(a).getLeft()!=null&&search(a).getRight()==null)
{
if(getParent(a).getInfo()>(search(a).getLeft()).getInfo())
getParent(a).setLeft(search(a).getLeft());
else
getParent(a).setRight(search(a).getLeft());
}
else if(search(a).getLeft()==null&&search(a).getRight()!=null)
{
if(getParent(a).getInfo()>(search(a).getRight()).getInfo())
getParent(a).setLeft(search(a).getRight());
else
getParent(a).setRight(search(a).getRight());
}
else if(search(a).getLeft()!=null&&search(a).getRight()!=null)//PER FUSIONE
{
BTNode aux2=getPredecessore(a);
aux2.setRight(search(a).getRight());
if((getParent(a).getInfo())>(search(a).getLeft()).getInfo())
getParent(a).setLeft(search(a).getLeft());
else
getParent(a).setRight(search(a).getLeft());
}
}
//CANCELLAZIONE PER SOSTITUZIONE
public void canc2(int a) throws Exception
{
if(search(a)==null)
throw new Exception("nodo con valore inesistente!");
else if(IsLeaf(search(a)))
{
if(getParent(a).getInfo()<a)
getParent(a).setRight(null);
else
getParent(a).setLeft(null);
}
else if(search(a).getLeft()!=null&&search(a).getRight()==null)
{
if(getParent(a).getInfo()>(search(a).getLeft()).getInfo())
getParent(a).setLeft(search(a).getLeft());
else
getParent(a).setRight(search(a).getLeft());
}
else if(search(a).getLeft()==null&&search(a).getRight()!=null)
{
if(getParent(a).getInfo()>(search(a).getRight()).getInfo())
getParent(a).setLeft(search(a).getRight());
else
getParent(a).setRight(search(a).getRight());
}
else if(search(a).getLeft()!=null&&search(a).getRight()!=null)//PER SOSTITUZIONE
{
//1.Si sostituisca la chiave col suo predecessore
BTNode aux2=getPredecessore(a);
search(a).setInfo(aux2.getInfo());
//2.Se il nodo che conteneva il predecessore è una foglia, si
//esegua il passo 1 dell’algoritmo di cancellazione
if(IsLeaf(aux2.getInfo()))
{
if(getParent(aux2.getInfo()).getInfo()<a)
getParent(aux2.getInfo()).setRight(null);
else
getParent(aux2.getInfo()).setLeft(null);
}
//3.Se il nodo che conteneva il predecessore ha un sottoalbero,
//si esegua il passo 2 dell’algoritmo di cancellaz.
else if(aux2.getLeft()!=null&&aux2.getRight()==null)
{
if(getParent(aux2.getInfo()).getInfo()>(aux2.getLeft()).getInfo())
getParent(aux2.getInfo()).setLeft(aux2.getLeft());
else
getParent(aux2.getInfo()).setRight(aux2.getLeft());
}
else if(aux2.getLeft()==null&&aux2.getRight()!=null)
{
if(aux2.getInfo()>(aux2.getRight()).getInfo())
getParent(aux2.getInfo()).setLeft(aux2.getRight());
else
getParent(aux2.getInfo()).setRight(aux2.getRight());
}
}
}
P.S. ho seguito i punti delle slide del prof...
Logged
Alex_47
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 409


The spiral's King


« Reply #16 on: 09-05-2009, 15:54:47 »

scusate la domanda ma

isLeaf() e isRoot() sono dei metodi da implementare nella classe nodo o nella classe albero?
Logged
MiKKu
Apprendista Forumista
**
Offline Offline

Posts: 152



WWW
« Reply #17 on: 09-05-2009, 15:56:19 »

Ma non c'è un metodo ricorsivo?
Logged

Soltanto l'ardente pazienza porterà al raggiungimento di una splendida felicità. - www.ilmercatinoitaliano.it
Giovi89
Apprendista Forumista
**
Offline Offline

Posts: 273


« Reply #18 on: 09-05-2009, 16:31:49 »

la cancellazione si puo fare in tutti e due i modi sia ricorsiva che iterativa...cmq nessuno può correggermi la cancellazione con sostituzione?
P.S. i metodi isLeaf() e IsRoot() si implementano nella classe albero, se si implementassero nella classe nodo come sarebbe possibile risalire alla radice oppure a una foglia dell'albero?
Logged
MiKKu
Apprendista Forumista
**
Offline Offline

Posts: 152



WWW
« Reply #19 on: 09-05-2009, 19:01:19 »

Chiedevo per il metodo ricorsivo perkè nelle slide del prof c'è solo quella iterativa...Non vorrei che nn fosse valida cmq...
Logged

Soltanto l'ardente pazienza porterà al raggiungimento di una splendida felicità. - www.ilmercatinoitaliano.it
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


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


« Reply #20 on: 11-05-2009, 11:04:11 »

implementando i metodi così come sono fatti dal prof nelle slide, ho confrontato gli attraversamenti ricorsivi e iterativi ma ho problemi con il postorder e l'inorder ricorsivo e non capisco perchè...oppure il problema è un altro e non lo sto capendo io...perchè danno un ordine diverso....e poi in base a quanti nodi inserisco il postorder iterativo a volte mi attraversa meno nodi di quanti ce ne sono effettivamente nell'albero..posto il codice dei metodi sia iterativi che ricorsivi spero che qualcuno possa darmi una mano!
Code:
public void preorder()
{
preorder(root);
}
private void preorder(NodoBT n)
{
if(n!=null)
{
n.visit();
preorder(n.left);
preorder(n.right);
}
}
public void inorder()
{
inorder(root);
}
private void inorder(NodoBT n)
{
if(n!=null)
{
preorder(n.left);
n.visit();
preorder(n.right);
}
}
public void postorder()
{
postorder(root);
}
private void postorder(NodoBT n)
{
if(n!=null)
{
preorder(n.left);
preorder(n.right);
n.visit();
}
}
public void iterpreorder()
{
NodoBT p=root;
Pila aiuto=new Pila();
if(p!=null)
{
aiuto.push(p);
while(!aiuto.isEmpty())
{
p=(NodoBT) aiuto.pop();
p.visit();
if(p.right!=null)
aiuto.push(p.right);
if(p.left!=null)
aiuto.push(p.left);
}
}
}
public void iterinorder()
{
NodoBT p=root;
Pila aiuto=new Pila();
while(p!=null)
{
while(p!=null)
{
aiuto.push(p);
p=p.left;
}
do
{
p=(NodoBT) aiuto.pop();
p.visit();
p=p.right;
}while(p==null&&!aiuto.isEmpty());
}
}
public void iterpostorder()
{
NodoBT p=root,q=root;
Pila aiuto=new Pila();
while(p!=null)
{
while(p!=null)
{
aiuto.push(p);
if(p.right!=null)
aiuto.push(p.right);
p=p.left;
}
do
{
p=(NodoBT) aiuto.pop();
if(isLeaf(p)||p.right==null||p.right==q)
{
p.visit();
q=p;
p=null;
}
}while(p==null&&!aiuto.isEmpty());
}
}
« Last Edit: 11-05-2009, 11:06:21 by Vivynz » 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.
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


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


« Reply #21 on: 13-05-2009, 10:06:16 »

nessuno può aiutarmi??
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.
Aigor
Forumista Esperto
****
Offline Offline

Gender: Male
Posts: 1.184


"Il destino non è una catena, ma un volo."[A.B.]


« Reply #22 on: 13-05-2009, 13:55:09 »


Ragazzi entro la fine di questa settimana posto il codice funzionante per i BST per quanto riguarda inorder,postorder,preorder ( iterativi e ricorsivi ) e della cancellazione ( solo iterativa ).

P.S. se vi serve codice per gli alberi n-ari ditelo così faccio tutto in una volta!!
Logged

"Era d'altronde uno di quegli uomini che amano assistere alla propria vita, ritenendo impropria qualsiasi ambizione a viverla.
Si sarà notato che essi osservano il loro destino nel modo in cui, i più, sono soliti osservare una giornata di pioggia." - Seta,Baricco
MiKKu
Apprendista Forumista
**
Offline Offline

Posts: 152



WWW
« Reply #23 on: 13-05-2009, 14:13:23 »

Se puoi anke gli n-ari faresti un favore a tutti credo ok
Logged

Soltanto l'ardente pazienza porterà al raggiungimento di una splendida felicità. - www.ilmercatinoitaliano.it
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


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


« Reply #24 on: 13-05-2009, 14:20:09 »

grazie Aigor!!!magari anche l'inserimento [Emoticon] Asd
« Last Edit: 13-05-2009, 14:29:21 by Vivynz » 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.
rox
Forumista
***
Offline Offline

Posts: 633


« Reply #25 on: 13-05-2009, 15:40:14 »

grazie Aigor!!!magari anche l'inserimento [Emoticon] Asd
Logged

Una macchina è in grado di lavorare come cinquanta uomini comuni, ma nessuna macchina può svolgere il lavoro di un uomo straordinario.
Vivynz
Forumista Eroico
*****
Offline Offline

Gender: Female
Posts: 2.033


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


« Reply #26 on: 15-05-2009, 14:38:59 »

posto la mia classe albero binario con tutti i metodi..nelle varie versioni. sia funzionante ma se la provate e trovate qualche errore fatemi sapere...
Code:
public class BT
{
protected NodoBT root;
public BT(NodoBT r)
{
root=r;
}
public BT()
{
this(null);
}
public NodoBT getRoot()
{
return root;
}
public boolean isEmpty()
{
return (root==null);
}
public void insert(Comparable c)
{
root=insert(c,root);
}
private NodoBT insert(Comparable c,NodoBT n)
{
if(n==null)
n=new NodoBT(c);
else if(c.compareTo(n.info)<0)
n.left=insert(c,n.left);
else if(c.compareTo(n.info)>0)
n.right=insert(c,n.right);
else;
return n;
}
public void iterInsert(Comparable c)
{
if(root==null)
root=new NodoBT(c);
else
{
NodoBT p=root,q=null;
while(p!=null)
{
if(c.compareTo(p.info)==0)
return;
q=p;
if(c.compareTo(p.info)<0)
p=p.left;
else p=p.right;
}
if(c.compareTo(q.info)<0)
q.left=new NodoBT(c);
else
q.right=new NodoBT(c);
}
}
public void preorder()
{
preorder(root);
System.out.println();
}
private void preorder(NodoBT n)
{
if(n!=null)
{
n.visit();
preorder(n.left);
preorder(n.right);
}
}
public void inorder()
{
inorder(root);
System.out.println();
}
private void inorder(NodoBT n)
{
if(n!=null)
{
inorder(n.left);
n.visit();
inorder(n.right);
}
}
public void postorder()
{
postorder(root);
System.out.println();
}
private void postorder(NodoBT n)
{
if(n!=null)
{
postorder(n.left);
postorder(n.right);
n.visit();
}
}
public void iterPreorder()
{
NodoBT p=root;
Pila aux=new Pila();
if(p!=null)
aux.push(p);
while(!aux.isEmpty())
{
p=(NodoBT) aux.pop();
p.visit();
if(p.right!=null)
aux.push(p.right);
if(p.left!=null)
aux.push(p.left);
}
System.out.println();
}
public void iterInorder()
{
NodoBT p=root;
Pila aux=new Pila();
while(p!=null)
{
while(p!=null)
{
aux.push(p);
p=p.left;
}
do
{
p=(NodoBT) aux.pop();
p.visit();
p=p.right;
}while(p==null&&!aux.isEmpty());
}
System.out.println();
}
public void iterPostorder()
{
NodoBT p=root,q=root;
Pila aux=new Pila();
while(p!=null)
{
while(p.left!=null)
{
aux.push(p);
p=p.left;
}
while(p!=null&&(p.right==null||p.right==q))
{
p.visit();
q=p;
if(aux.isEmpty())
{
System.out.println();
return;
}
p=(NodoBT) aux.pop();
}
aux.push(p);
p=p.right;
}
}
public void livellorder()
{
NodoBT p=root;
Coda aux=new Coda();
if(p!=null)
{
aux.enqueque(p);
while(!aux.isEmpty())
{
p=(NodoBT) aux.dequeque();
p.visit();
if(p.left!=null)
aux.enqueque(p.left);
if(p.right!=null)
aux.enqueque(p.right);
}
System.out.println();
}
}
public Comparable deleteByMerging(Comparable c)
{
NodoBT n,restituisci, p=root, q=null;
while(p!=null&&c.compareTo(p.info)!=0)
{
q=p;
if(c.compareTo(p.info)<0)
p=p.left;
else
p=p.right;
}
n=p;
if(p!=null&&c.compareTo(p.info)==0)
{
if(n.right==null)
n=n.left;
else if(n.left==null)
n=n.right;
else
{
NodoBT tmp=n.left;
while(tmp.right!=null)
tmp=tmp.right;
tmp.right=n.right;
n=n.left;
}
if(p==root)
root=n;
else if(q.left==p)
q.left=n;
else
q.right=n;
return c;
}
return null;

}
public Comparable deleteByCopying(Comparable c)
{
NodoBT n,restituisci, p=root, q=null;
while(p!=null&&c.compareTo(p.info)!=0)
{
q=p;
if(c.compareTo(p.info)<0)
p=p.left;
else
p=p.right;
}
n=p;
if(p!=null&&c.compareTo(p.info)==0)
{
if(n.right==null)
n=n.left;
else if(n.left==null)
n=n.right;
else
{
NodoBT tmp=n.left, t=n;
while(tmp.right!=null)
{
t=tmp;
tmp=tmp.right;
}
n.info=tmp.info;
if(t==n)
t.left=tmp.left;
else
t.right=tmp.left;
}
if(p==root)
root=n;
else if(q.left==p)
q.left=n;
else
q.right=n;
return c;
}
return null;

}
public NodoBT search(Comparable c)
{
return search(c,root);
}
private NodoBT search(Comparable c,NodoBT p)
{
if(p!=null)
{
if(c.compareTo(p.info)<0)
return search(c,p.left);
else if (c.compareTo(p.info)>0)
return search(c,p.right);
else
return p;
}
return null;
}
public NodoBT iterSearch(Comparable c)
{
NodoBT p=root;
while(p!=null)
{
if(c.compareTo(p.info)<0)
p=p.left;
else if(c.compareTo(p.info)>0)
p=p.right;
else
return p;
}
return null;
}
public int getHeight()
{
if(isEmpty())
return -1;
return getHeight(root);
}
private int getHeight(NodoBT p)
{
if(p==null||(p.left==null&&p.right==null))
return 0;
else
return 1+Math.max(getHeight(p.left),getHeight(p.right));
}
public int getLevel(Comparable c)
{
return getLevel(search(c),root);
}
private int getLevel(NodoBT p,NodoBT r)
{
if(p==null)
return -1;
else
{
if(p==r)
return 0;
if(((Comparable)p.info).compareTo(r.info)<0)
return 1+getLevel(p,r.left);
else if(((Comparable)p.info).compareTo(r.info)>0)
return 1+getLevel(p,r.right);
else return 1;
}
}
public NodoBT getBrother(NodoBT p)
{
return getBrother(p,root);
}
private NodoBT getBrother(NodoBT p,NodoBT r)
{
if(r!=null)
{
if(r.left==p)
return r.right;
if(r.right==p)
return r.left;
NodoBT temp=getBrother(p,r.left);
if(temp==null)
return getBrother(p,r.right);
else return temp;
}
return null;
}
}
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.
leviadragon
Apprendista Forumista
**
Offline Offline

Posts: 217


WWW
« Reply #27 on: 15-05-2009, 16:22:16 »

salve ragazzi , ho un problema logico[penso] sul metodo di cancellazione che ho provato a fare da me , spero che qualcuno magari riesca ad individuarlo poichè sto uscendo pazzo  testate  il codice non implementa ancora la sostituzione e la fusione... grazie in anticipo!

Code:
public boolean deleteKey(int val)
{
if (isEmpty())return false;
aNodo aux=root;
aNodo prev=null;

while((aux!=null) && (aux.getInfo()!=val))
{
prev=aux;
if (aux.getInfo()> val)aux=aux.getRight();
else aux=aux.getLeft();
}
if (aux==null)return false;
if((aux.getRight()==null)&&(aux.getLeft()==null))
{
if (prev.getLeft()==aux)prev.setLeft(null);
else prev.setRight(null);
}

if ((aux.getLeft()!=null) && (aux.getRight() ==null))
{
if (prev.getLeft()==aux)prev.setLeft(aux.getLeft());
else prev.setRight(aux.getLeft());
}
if ((aux.getRight()!=null)&&(aux.getLeft()==null))
{
if (prev.getLeft()==aux)prev.setLeft(aux.getRight());
else prev.setRight(aux.getRight());
}
if ((aux.getRight()!=null)&&(aux.getLeft()!=null))
{
//da inserire la sostituzione
}
return true;
}
« Last Edit: 15-05-2009, 16:23:55 by leviadragon » Logged

www.darkzero.altervista.org <-- se vi piace mettetela come homepage

Link Immagine


--gratuitamente ricevete,gratuitamente date--
leviadragon
Apprendista Forumista
**
Offline Offline

Posts: 217


WWW
« Reply #28 on: 16-05-2009, 10:56:20 »

ehm nessuno?help!
Logged

www.darkzero.altervista.org <-- se vi piace mettetela come homepage

Link Immagine


--gratuitamente ricevete,gratuitamente date--
Pages: 1 [2]   Go Up
Print
Jump to: