Pages: [1] 2   Go Down
Print
Author Topic: Mi aiutereste in questo esercizio?  (Read 3249 times)
0 Members e 1 Utente non registrato stanno visualizzando questa discussione.
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« on: 25-10-2010, 21:27:53 »

Ho provato a fare l'esercizio sugli alberi iterativi.
Però ho un problema, il programma fa qualcosa, però nella visita in output ho solamente la radice, stampa solo quella, temo ci siano problemi nell'inserimento, non so perchè.
L'esercizio dice:

Code:
Dare un'implementazione della seguente interfaccia, IterativeBST<E>, che rappresenta un
albero binario di ricerca, dove le etichette dei nodi sono di tipo generico E. Il grafo dovrà
essere implementato utilizzando la struttura Parent-Left-Right. Tutte le procedure della
classe dovranno essere procedure iterative.
Fornire in seguito un programma Java che costruisca un albero di coppie di interi
prendendo. Tale programma prenderà come input un file contenente una sequenza di
coppie di interi, una per ogni riga. Si supponga che una coppia sia maggiore di una
seconda coppia se la somma dei valori contenuti nella prima coppia è maggiore della
somma dei valori contenuti nella seconda coppia. Si supponga inoltre che non siano
presenti coppie la cui somma abbia lo stesso valore.
Il Programma dovrà restituire in output un file contenente gli elementi dell'albero come
stampati da una visita post-order.

Allora ho pensato che ogni nodo contiene un oggetto Coppia che implementa il metodo compareTo, solo che non ho saputo usare nelle intestazioni delle classi extends e implements Comparable, perchè non mi compila, mi potreste dire come fareste con l'interfaccia Comparable? Io ho pensato di scrivere che Coppia implementa comparable, ma mi dà errore, dice che non trova l'interfaccia se non ho capito male, oppure devo scrivere che Coppia estende Comparable, e poi nella classe Nodo scrivere qualcosa come:
Code:
TNode<E implements Comparable>
.
.

Dato che il nodo è di tipo coppia che ha il metodo compareTo e lo implementa in effetti, ma ho problemi di compilazione.


Le classi sono queste:

Interfaccia:

Code:
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
}


Nodo:
Code:
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;}


}

Classe coppia:
Code:
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 elemementi è maggiore di quella dell'altra, non posso 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()+")";
}
}


classe Stack:

Code:
public class Stack<E>
{
private E[] stack;
private int size;

public Stack(int CAPACITY)
{
stack=(E[]) new Object[CAPACITY];
size=0;
}

public boolean isEmpty(){ return size==0;}

public int getSize(){return size;}

public void push(E element){

int i=0;
while(stack[i]!=null)
i++;
stack[i]=element;

}

public E pop(){
int i=0;

while(stack[i]!=null)
i++;

E node=stack[i-1];
stack[i-1]=null;
return node;
}

public E top(){
int i=0;
while(stack[i]!=null)
i++;
E node=stack[i-1];
return node;
}
}

classe BStree:

Code:
public class BSTree<E>  implements  IterativeBST<E>
{
private int size;
private TNode<E> root;
private String stampa="";

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 element)
{
return;
}



public E succesor(E x){

TNode<E> tmp=null;

if(((TNode)x).hasRight()){
tmp=((TNode)x).getRight();

while(tmp.hasLeft())
tmp=tmp.getLeft();
}


else {
TNode<E> y=((TNode)x).getParent();

while(y!=null && ((TNode)x).equals(y.getRight())){
x=(E)y;
y=y.getParent();
}
}

  return (E)tmp;
}



public String postorder(){
String s="";
TNode p = root, q = root;
Stack<TNode> aiuto=new Stack<TNode>(size);

while (p != null){
while(p != null){
aiuto.push(p);
if(p.hasRight())
aiuto.push(p.getRight());
p = p.getLeft();
}
do{
p = (TNode)aiuto.pop();
if((p.hasLeft()==false && p.hasRight()==false) || !(p.hasRight()) || p.getRight().equals(q)){
s+=p.getElement().toString()+'\r'+'\n';
q =p;
p = null;
}
     }
     while(p == null && !aiuto.isEmpty());
}
return s;
}

}

E il Main:
Code:
import java.io.*;
import java.util.*;

public class Main
{
FileReader reader=null;
StringTokenizer str;
PrintWriter out=null;
BufferedReader buff=null;

public void Costruiscialbero(String input, String output)
{
try{
reader=new FileReader(input);
buff=new BufferedReader(reader);
out=new PrintWriter(output);

BSTree<TNode> albero=new BSTree<TNode>();

while(buff.ready())
{
//str=new StringTokenizer(buff.readLine(),"(,)");
str=new StringTokenizer(buff.readLine().trim(),"(,)");


int primo=0;
int secondo=0;

while(str.hasMoreElements())
{
primo=(Integer.parseInt(str.nextToken()));
secondo=(Integer.parseInt(str.nextToken()));
}

Coppia coppia=new Coppia(primo, secondo);
TNode<Coppia> nodo=new TNode<Coppia>(coppia);

albero.insert(nodo);

}

out.print(albero.postorder());
      }

catch(FileNotFoundException e1)
{
System.out.println("Error...file not found");
}

catch(IOException e2)
{
System.out.println("Error...input/output");
}

finally{
try{

buff.close();
reader.close();
out.close();
      }
     
      catch(IOException e3){
      System.out.println("Error...it is not possible to close files");
      }
      }
}

public static void main(String [] args)
{
Main main=new Main();
long start=System.currentTimeMillis();
main.Costruiscialbero("input.txt", "output.txt");
long end=System.currentTimeMillis();
System.out.println("Il tempo d'esecuzione è "+(end-start)+" ns");
}
}
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
bluegirl
Apprendista Forumista
**
Offline Offline

Posts: 360



« Reply #1 on: 26-10-2010, 14:48:23 »

Ho dato uno sguardo veloce e, per esempio, il metodo successor mi sembra sbagliato. Devi trovare il valore minimo nel sottoalbero destro...non mi sembra che tu lo faccia.Puoi crearti un metodo, per esempio getMinimo() e richiamarlo nel metodo successor()
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #2 on: 26-10-2010, 22:21:09 »

Hey, grazie della risposta, qualcuno c'è per fortuna 
Ho ricontrollato, cambiato alcune cose, come va secondo te?

Code:
public E succesor(E x){

TNode<E> tmp=null;

if(((TNode)x).hasRight()){
tmp=((TNode)x).getRight();

while(tmp.hasLeft())
tmp=tmp.getLeft();
                                 return tmp;
}


else {
TNode<E> y=((TNode)x).getParent();

while(y!=null && ((TNode)x).equals(y.getRight())){
x=(E)y;
y=x.getParent();   //potrei anche scrivere y=y.getParent()???
}
}

  return y

A parte qualche cast...come va?

Oltre a questo ci sono altre cose che hai notato? Io...non ho ben capito come funzionano le rotazioni, non le so fare.
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Angelo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 274



« Reply #3 on: 27-10-2010, 08:07:05 »

il tempo di sistemare e posto la mia..magari ti potrebbe essere utile..
Logged

..elimindo il ponte pedonale di andrea doria..hanno eliminato una parte di me!..
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #4 on: 27-10-2010, 08:57:36 »

Hey, grazie della risposta, qualcuno c'è per fortuna 
Ho ricontrollato, cambiato alcune cose, come va secondo te?

Code:
public E succesor(E x){

TNode<E> tmp=null;

if(((TNode)x).hasRight()){
tmp=((TNode)x).getRight();

while(tmp.hasLeft())
tmp=tmp.getLeft();
                                 return tmp;
}


else {
TNode<E> y=((TNode)x).getParent();

while(y!=null && ((TNode)x).equals(y.getRight())){
x=(E)y;
y=x.getParent();   //potrei anche scrivere y=y.getParent()???
}
}

  return y

A parte qualche cast...come va?

Oltre a questo ci sono altre cose che hai notato? Io...non ho ben capito come funzionano le rotazioni, non le so fare.

Ho controllato il tuo codice sul successore: io ti consiglio di seguire un'altra strada anche perchè in questo modo ci sono un bel po' di errori...
Innanzitutto cerca di pensare al metodo in questo modo: il metodo successor va a ricercare il successivo nell'albero binario, quindi ti conviene andare a fare una ricerca nel sottoalbero destro; il successore lo trovi andando a richiamare nel sottoalbero considerato il minimo(implementando il metodo minimo() ricorda che deve essere una procedura iterativa) e ti eviti di andare a settare altri nodi.
Non so se sono stato chiaro.
A presto
Logged
Angelo
Apprendista Forumista
**
Offline Offline

Gender: Male
Posts: 274



« Reply #5 on: 27-10-2010, 10:11:15 »

Eccolo..scusa il disordine..ma dovrebbe essere funzionante..credo..
Code:
import java.io.*;
import java.util.*;

public class BSTIterative{
  public static void main (String [] args) throws IOException{
 
   
    Scanner input = new Scanner(new File("input.txt"));
    FileWriter output =  new FileWriter("output2.txt");
   
    String s;
    int a,b;
    BSTI <Coppia> T = new BSTI <Coppia>();
   
    while (input.hasNextLine()){
     
      s= input.nextLine();
      a= Integer.parseInt(""+ s.charAt(1));
      b= Integer.parseInt(""+ s.charAt(3));

      Coppia c = new Coppia (a,b);
      T.insert(c) ;
    }
   
    Coppia c= new Coppia (1,3);
    //T.delete(c);
    T.stampaGrafica();
    //T.postorder();
    //T.stampaGrafica();
    input.close();
    output.close();
  }
}

class Stack<E> {
  private E[] array;
private int top;
private int capacità;

  public Stack(int cap){
    capacità=cap;
    array=(E[]) new Object[capacità];
    top=0;
 
  }
 
 
  public boolean isEmpty(){
    return(top < 0);
  }
  public int getSize(){
    return(top+1);
  }
  public E pop(){
    if (isEmpty()){
      return null;
    }
    else{
      E element = array[top];
      array[top--] = null;
      return element;
    }
  }
  public void push(E element){
    if (getSize() == capacità)
      return ;
    else {
      array[++top] = element;
    }
  }
 public E top(){
    if (isEmpty())
     return null;
    return array[top];
  }
 
}
class Coppia implements Comparable{
  private int a;
  private int b;
  private int somma;
 
 
  public Coppia(int a, int b){
    this.a= a;
    this.b= b;
    somma = a+b;
   
  }
  Object obj= (Object) somma;
 
 
  public String toString(){ return ("("+ a + "," + b + ")");}
  public int getSomma(){return somma;}
 
  public int compareTo(Object obj){
    if (this.somma < ((Coppia)obj).getSomma())
      return -1;
    else if (this.somma > ((Coppia)obj).getSomma())
      return 1;
    else
      return 0;
  }
}

class TNode<E> {
  private TNode<E> parent, left, right;
  private E label;
  private int flag;
 
 
  public TNode ( E label , TNode<E> parent){
    this.label = label;
    this.parent = parent;
    left = right = null;
    flag = 0;
  }
  public int getFlag(){ return flag;}
  public void setFlag(int flag){this.flag=flag;}
  public TNode<E> getParent(){ return parent;}
  public TNode<E> getLeft(){ return left;}
  public TNode<E> getRight(){ return right;}
  public E getlabel(){ return label;}
 
 
  public void setParent(TNode<E> parent){ this.parent=parent;}
  public void setLeft(TNode<E> left){ this.left=left;}
  public void setRight(TNode<E> right){ this.right=right;}
  public void setlabel(E label){this.label=label;}
 
}

class BSTI<E extends Comparable> implements IterativeBST<E>{
  private int size;
  private TNode<E> root;
 
  public BSTI(){
    size=0;
    root=null;
  }
 
  // ritorna il numero di nodi dell'albero
  public int size (){
    return size;
  }
 
  // inserisce un nuovo labelo nell'albero
  public void insert (E x){
    TNode<E> tmp= new TNode<E>(x, null);
    if( root == null ){ //L'albero è vuoto
      root = tmp;
      size++;
      }
      else{
        TNode<E> p = root, parent = null;
        while( p!= null){
          parent=p;
         
          if( tmp.getlabel().compareTo(p.getlabel())< 0)
            p = p.getLeft();
          else if( tmp.getlabel().compareTo(p.getlabel()) > 0)
          p = p.getRight();
        }
       
        if( tmp.getlabel().compareTo(parent.getlabel())< 0){
          parent.setLeft(new TNode<E>(x, parent));
          size++;
          }
        else{
          parent.setRight(new TNode<E>(x, parent));
          size++;
        };
      }
}

  // ritorna true se l'labelo E è contenuto nell'albero
  public boolean search (E x){
    TNode<E> tmp= new TNode<E>(x, null);
    TNode<E> p=root;
    while ( p != null )
      if( tmp.getlabel().compareTo(p.getlabel())< 0)
        p = p.getLeft();
      else if( tmp.getlabel().compareTo(p.getlabel())> 0)
        p = p.getRight();
      else return true;
        return false;
  }
 
  // come il search, tranne che torna il nodo cercato( usato per il right rotate e il succesor)
  public TNode<E> tornaNodo (E x){
    TNode<E> tmp= new TNode<E>(x, null);
    TNode<E> p=root;
    while ( p != null )
      if( tmp.getlabel().compareTo(p.getlabel())< 0)
        p = p.getLeft();
      else if( tmp.getlabel().compareTo(p.getlabel())> 0)
        p = p.getRight();
      else return p;
        return null;
  }
 
   // effettua una rotazione destra sul nodo che contiene x
  public void RightRotate(E x){
    TNode<E> tmp= tornaNodo(x);
    if(tmp == null)
      return;
    if (tmp.getLeft() == null)
      return ;
    TNode<E> y= tmp.getLeft();
    y.setParent(tmp.getParent());
    if (y.getParent() == null)
      root= y;
    else if (tmp.getlabel() == tmp.getParent().getLeft().getlabel())
      y.getParent().setLeft(y) ;
    else
      y.getParent().setRight(y);
    tmp.setParent(y);
    tmp.setLeft(y.getRight());
    if (tmp.getLeft() != null)
      tmp.getLeft().setParent(tmp);
    y.setRight(tmp);
  }
 
  public void LeftRotate(E x){
    TNode<E> tmp= tornaNodo(x);
    if (tmp == null)
      return;
    if (tmp.getRight() == null)
      return;
    TNode<E> y= tmp.getRight();
    y.setParent(tmp.getParent());
    if (y.getParent() == null)
      root=y;
    else if (tmp.getlabel() == tmp.getParent().getRight().getlabel())
      y.getParent().setRight(y);
    else
      y.getParent().setLeft(y);
    tmp.setParent(y);
    tmp.setRight(y.getLeft());
    if (tmp.getRight() != null)
      tmp.getRight().setParent(tmp);
    y.setLeft(tmp);
  }
 
  // ritorna l'labelo successivo di x
  public E succesor(E x){
    TNode<E> tmp = tornaNodo(x) ;
    if (tmp.getRight() == null) return null;
    tmp = tmp.getRight();
    if (tmp.getLeft() == null) return tmp.getlabel();
      while(tmp.getLeft() != null){
        tmp = tmp.getLeft();
      }
    return tmp.getlabel();
  }
 
 
  public void delete(E x){
TNode<E> tmp= tornaNodo(x);
    if(tmp==null) return;
TNode<E> z=tmp.getParent();
   
if(tmp.getLeft()==null && tmp.getRight()==null){ //caso foglia
      System.out.println("entro nel caso foglia");
if (z==null) root=null;
if(tmp==z.getLeft()) z.setLeft(null);
else z.setRight(null);
tmp.setParent(null);
size--;
return;
}
if(tmp.getLeft()!=null && tmp.getRight()==null){ //ha solo figlio sx
System.out.println("entro nel caso figli sx");
      if(z==null){ root=tmp.getLeft();
root.setParent(null);}
else{tmp.getLeft().setParent(z);
if(tmp==z.getLeft()) z.setLeft(tmp.getLeft());
}
size--;
return;
}
if(tmp.getRight()!=null && (tmp.getLeft()==null)){ //ha solo figlio dx
System.out.println("entro nel caso figli dx ");
      if(z==null){ root=tmp.getRight();
root.setParent(null);}
else{ tmp.getRight().setParent(z);
if(tmp==z.getRight()) z.setRight(tmp.getRight());}

size--;
return;
}
if(tmp.getLeft()!=null && tmp.getRight()!=null){//è un nodo interno
System.out.println("sono nel caso nodo interno");
      E e= succesor(tmp.getlabel());
      System.out.println(e);
      TNode<E> v=tornaNodo(e);
delete(v.getlabel());
      tmp.setlabel(v.getlabel());

return;
}
}
 
  public TNode<E>[] postorder(){
    TNode<E>[] array= (TNode<E>[]) new TNode[size];
    int count= 0;
    Stack<E> stack= new Stack<E>(size);
    System.out.println("stack creato");
    TNode<E> x= root;
    System.out.println("x = " + root.getlabel());
    stack.push(x.getlabel());
    System.out.println("pusho: " + x.getlabel());
    while ( !stack.isEmpty()){
      System.out.println("sono dentro il while");
      x.setlabel(stack.top());
      System.out.println("x diventa: " + stack.top());
      if (x.getFlag() == 0){
        System.out.println("se flag 0 di " + x.getlabel());
        stack.push(x.getRight().getlabel());
        System.out.println("pusho il dx: " + x.getRight().getlabel());
        stack.push(x.getLeft().getlabel());
        System.out.println("pusho il sx: " + x.getLeft().getlabel());
        x.setFlag(1);
        System.out.println("setto il flag a 1 di " + x.getlabel());
      }
      else {
        System.out.println("postorder " + x.getlabel());
        TNode<E> n=tornaNodo(stack.pop());
        array[count++]=n;
        System.out.println("poppo");
      }
    }
   
    return array;
  }
 
  //metodo di stampa a video dell'albero
  public void stampaGrafica() {
          TNode p = root; 
          if(p!=null)
                stampaGrafica(p,0);
            else
            System.out.println("albero vuoto");
          }
  protected void stampaGrafica(TNode<E> subroot, int livelloAttuale) {
      if(subroot == null)
          return;
      stampaGrafica(subroot.getRight(),livelloAttuale+1);
      for(int liv = livelloAttuale ; liv > 0 ; liv--)
        System.out.print("\t");
      System.out.println(subroot.getlabel() );
      stampaGrafica(subroot.getLeft(),livelloAttuale+1);
    }
}

non metto interfaccia e txt..usa quelli del pdf..
Logged

..elimindo il ponte pedonale di andrea doria..hanno eliminato una parte di me!..
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #6 on: 27-10-2010, 14:34:39 »

Dico grazie in anticipo ad Angelo, ma vorrei cercare di capire cosa non va nel mio prima, e poi vedere la sua soluzione che sicuramente sarà più elegante della mia  
Intanto conservo la tua versione per vederla dopo, grazie  

Ora, ho cercato di cambiare il metodo della ricerca del successivo, sperando che sia migliore delle precedenti.

Code:
public E getMinimum(TNode<E> node){
if(node==null) return null;

if(node.hasLeft()){                      //se c'è il nodo sinistro cerco il minimo sempre a sinistra
while(node.hasLeft()){
node=node.getLeft();
}
}
return node;                                 
}



public E succesor(E x){
if(x==null) return null;
TNode<E> successor;

if(((TNode)x).getRight()!=null){
successor=(TNode<E>)getMinimum(((TNode)x).getRight());                       //ricerco il successivo nei sottoalberi
return (E)successor;
}
else {                                                                                          //altrimenti salgo finchè non trovo come padre successor con figlio sinistro uguale a x
successor=((TNode)x).getParent();     

while(successor!=null && ((TNode)x).equals(successor.getRight())){
x=(E)successor;
successor=((TNode)x).getParent();
}
}
return (E)successor;
}

Come vi sembra?
« Last Edit: 27-10-2010, 15:02:11 by Daréios » Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #7 on: 27-10-2010, 15:01:03 »

Ora potrebbe anche andare
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #8 on: 27-10-2010, 15:03:05 »

Eh...bene, grazie. Il problema è che il programma di per se non fa quello che deve fare.
Cioè dovrei fare la visita postorder iterativa, ma mi viene stampato sulo un nodo.
Non capisco cosa non va nella visita postorder....credo il problema principale sia lì...
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #9 on: 27-10-2010, 15:29:19 »

Scusami devi ritornare il successivo di un nodo dato giusto? E' normale che ti stampi un solo valore
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #10 on: 27-10-2010, 15:40:16 »

No....io nel main se dai un' occhiata faccio la chiamata alla visita postorder, quindi dovrebbe stamparmi i nodi secondo la visita postorder, però mi dà solamente un nodo, e non va bene.
Temo sia sbagliata la visita postorder, il codice l'ho preso dalle slide del professore pulvirenti, non capisco cosa non vada bene, temo l'errore sia lì, perchè l'esercizio vuole la postorder, ma mi dà solamente un nodo...
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #11 on: 27-10-2010, 15:51:20 »

Prova questa qui come visita postorder e vedi se ti funziona
Code:
public void IterPostorder() throws Exception
    {
        Nodo<E> p = root , q = root;
Pila<Nodo<E>> aiuto = new Pila();
while(p != null)
{
            for(;p.getLeft() != null;p = p.getLeft()) aiuto.push(p);
            while (p != null && (p.getRight() == null || p.getRight() == q))
            {
                p.visit();
q = p;
if (aiuto.isEmpty()) return;
p = (Nodo<E>) aiuto.pop();
            }
            aiuto.push(p);
            p = p.getRight();
        }
    }
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #12 on: 27-10-2010, 17:45:10 »

Ho appena provato, non va nemmeno così, stesso identico risultato, mi stampa solo un nodo....
Mentre mi sembra che l'inserimento lo faccia bene, ho provato a fare, la stampa del successivo della radice, e mi risulta corretto, quindi neanche potrei sospettare che non inserisca gli elementi perchè l'accesso lo ha fatto.....
Strano...

Io faccio stampare una stringa....quindi dimmi se sbaglio da qualche parte:

Code:
public String postorder()
{
String s="";

TNode<E> p = root , q = root;
Stack<TNode<E>> aiuto = new Stack(size);
while(p != null)
{
for(;p.getLeft() != null;p = p.getLeft()) aiuto.push(p);
while (p != null && (p.getRight() == null || p.getRight() == q))
{
s+=p.getElement().toString()+'\r'+'\n';
q = p;
if (aiuto.isEmpty()) return s;
p = (TNode<E>) aiuto.pop();
}
aiuto.push(p);
p = p.getRight();
}

return s;
}
« Last Edit: 27-10-2010, 17:48:11 by Daréios » Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
vincenzo86
Forumista
***
Offline Offline

Gender: Male
Posts: 505



« Reply #13 on: 27-10-2010, 18:48:01 »

Mi hai detto che ti stampa un solo valore vero? A me questo accadeva con il rightrotate.. Quando ho introdotto la ricerca del nodo con valore x  funzionava tutto..
Ti faccio vedere come ho risolto io... Prova a farlo anche tu nel successor.
Comunque ho provato il tuo postorder e funziona da me... Quindi puoi riprovare a modificare qualcosa nel metodo..
Ti posto come esempio ciò che ho fatto io:
Code:
public Nodo<E> Search(E x){
Nodo<E> p = root;
while(p!=null){
int res = ((Comparable)x).compareTo(p.element());
if(res==0)
return p;
else if(res>0)
p=p.getRight();
else
p=p.getLeft();
}
return null;
}
    public void rightRotate(E x)
    {
        Nodo<E> tmp=new Nodo(x);
        Nodo<E> ruota=Search(tmp.element()); //dopo aver fatto questa modifica al mio codice, il postorder non stampava + un singolo valore
        if(ruota==null)
            return;
        if(ruota.left==null)
            return;
        Nodo<E> y=ruota.left;
        y.parent=ruota.parent;
        if(y.parent==null)
            root=y;
        else
        {
            if(x==ruota.parent.left)
                y.parent.left=y;
            else
                y.parent.right=y;

        }
        ruota.parent=y;
        ruota.left=y.right;
        if(ruota.left!=null)
            ruota.left.parent=ruota;
        y.right=ruota;
    }
Logged
Daréios89
Forumista Eroico
*****
Offline Offline

Gender: Male
Posts: 2.679


La musica è la forma d'arte suprema.


« Reply #14 on: 27-10-2010, 19:39:44 »

Darò un' occhiata, ma mi sembra assurdo.
Cioè RightRotate e Successor possono anche essere sbagliate, per dire, ma se io stampo in outpout la postorder, e tu mi hai dato conferma che è corretta, allor aperchè mi stampa un solo nodo?
D'altra parte io non uso proprio nel metodo postorder i metodi successor e RightRotate, quelli sono implementati solo perchè richiesto nell'esercizio ma non li uso nella postorder, quindi come può essere che se anche a te risulta giusta la visita in output non c'è nulla?
Ribadisco che non vengono usati anche se fossero sbagliati.
Controllerò...magari domani e ti farò sapere...stasera sono cotto 

Grazie dell'aiuto!
Logged

"Utilizzare sempre de l'Hôpital.....è come andare a caccia di farfalle con un bazooka".
Pages: [1] 2   Go Up
Print
Jump to: