Allora io ho una classe albero che implementa questa interfaccia:
codice:
public interface IterativeBST<E> {
public int size ();
// ritorna il numero di nodi dell'albero
public void insert (E x);
// inserisce un nuovo elemento nell'albero
public boolean search (E x);
// ritorna true se l'elemento E č contenuto nell'albero
public void RightRotate(E x);
// effettua una rotazione destra sul nodo che contiene x
public E succesor(E x);
// ritorna l'elemento successivo di x
}
Mi hanno detto che non sono corretti nemmeno i metodi RightRotate e successor, a parte questo, sto continuando a scrivere e cancellare, perchč non sto riuscendo a implementare il metodo PostOrder dell'albero iterativo.
Non riesco con i cicli a fare in modo che scenda e stampi figlio sinistro e destro e poi passi alla radice.
Mi ricordo che forse per trasformare un metodo da ricorsivo ad iterativo si doveva utilizzare uno stack, ma non so come....posto il codice ma il metodo postorder č vuoto perchč qualunque cosa scriva non va.
Forse si puņ utilizzare uno stack? Se si...come?
P.S il metodo non č indicato nell'interfaccia ma l'esercizio vuole che si implementi una postorder non ricorsiva:
codice:
public class BSTree<E> implements IterativeBST<E>
{
private int size;
private TNode<E> root;
public BSTree()
{
root=null;
size=0;
}
public void setRoot(TNode<E> nodo){this.root=nodo;}
public TNode<E> getRoot(){return root;}
public int size(){return size;}
public void insert(E node){
if(size()==0){
setRoot((TNode)node);
}
else{
TNode<E> current=getRoot();
boolean inserito=false;
while(!inserito)
{
if(((Coppia)current.getElement()).compareTo(((Coppia)((TNode)node).getElement()))<0)
{
if(!(current.hasRight()))
{
current.setRight((TNode)node);
((TNode)node).setParent(current);
inserito=true;
}
else current=current.getRight();
}
else if(((Coppia)current.getElement()).compareTo(((Coppia)((TNode)node).getElement()))>0)
{
if(!(current.hasLeft()))
{
current.setLeft((TNode)node);
((TNode)node).setParent(current);
inserito=true;
}
else current=current.getLeft();
}
}
}
size++;
}
public boolean search (E node){
assert getRoot()!=null;
TNode<E> current=getRoot();
boolean trovato=false;
while(!trovato && current!=null)
{
if(current.equals((TNode)node)){
trovato=true;}
else if(((Coppia)current.getElement()).compareTo(((Coppia)((TNode)node).getElement()))<0){
current=current.getRight();}
else current=current.getLeft();
}
return trovato;
}
public void RightRotate(E node){
if(node==null) return;
if(((TNode)node).getLeft()==null) return;
TNode<E> y=((TNode)node).getLeft();
y.setParent(((TNode)node).getParent());
}
public E succesor(E node){
TNode<E> toReturn=((TNode)node).getRight();
return (E)toReturn;
}
public String postorder()
{
}
}
codice:
public class Coppia<E>
{
int primo, secondo;
public Coppia(int primo, int secondo)
{
this.primo=primo;
this.secondo=secondo;
}
public int compareTo(Coppia<E> coppia){ //Una coppia č maggiore se la somma degli elementi č maggiore di quella dell'altra coppia, non possono mai essere uguali
int somma1=getPrimo()+getSecondo();
int somma2=coppia.getPrimo()+coppia.getSecondo();
if(somma1<somma2) return -1;
else return 1;
}
public int getPrimo(){return primo;}
public int getSecondo(){return secondo;}
public String toString()
{
return "("+getPrimo()+","+getSecondo()+")";
}
}
codice:
public class TNode<E>
{
private E element;
private TNode<E> parent;
private TNode<E> left;
private TNode<E> right;
public TNode(E element)
{
this.element=element;
parent=null;
left=null;
right=null;
}
public void setElement(E element){this.element=element;}
public E getElement(){return element;}
public void setParent(TNode<E> parent){this.parent=parent;}
public TNode<E> getParent(){return parent;}
public void setLeft(TNode<E> left){this.left=left;}
public TNode<E> getLeft(){return left;}
public void setRight(TNode<E> right){this.right=right;}
public TNode<E> getRight(){return right;}
public boolean hasLeft(){return left!=null;}
public boolean hasRight(){return right!=null;}
}
Permessi di invio
Rispondi quotando