[JAVA] Albero binario e metodo ricorsivo preordine

[Tallid]

Data un' interfaccia:

public interface AlberoBinario<T> {
   AlberoBinario<T> getLeft();
   AlberoBinario<T> getRigth();
   T getInfo();
   boolean isEmpty();
   List<T> preordine();
 }

e una classe :

public class AlberoBinarioImpl<T> implements AlberoBinario<T> {
    private T info;
    private AlberoBinario<T> left;
    private AlberoBinario<T> right;
    public AlberoBinarioImpl(T info,AlberoBinario<T> left,AlberoBinario<T> right){
        this.info=info;
        this.left=left;
        this.right=right;
    }
   public AlberoBinario<T> getLeft() {return left;}
   public AlberoBinario<T> getRigth() {return right;}
   public T getInfo() {return info;}
   public boolean isEmpty() {
        if(info==null && left==null && right==null)return true;
        return false;
   }
   public List<T> preordine() {...}
}

Implementare il metodo ricorsivo preordine che ritorna una lista con le informazioni
dell’albero in preordine.

Ho fatto vari tentativi ma non ci riesco, il metodo non riceve in ingersso nessun parametro di tipo AlberoBinario, quindi è impossibile scorrere l'albero ricorsivamente secondo me!

Qulcuno ha qualche dritta da darmi? Grazie.

[alka]

Originariamente inviato da Tallid
Ho fatto vari tentativi ma non ci riesco

Posta il codice che hai scritto, così gli utenti possono suggerire migliorie e/o correzioni.

[andbin]

Originariamente inviato da Tallid
il metodo non riceve in ingersso nessun parametro di tipo AlberoBinario, quindi è impossibile scorrere l'albero ricorsivamente secondo me!

Tecnicamente nessuno ti vieta (se non ti è stato proibito per qualche motivo) di mettere in AlberoBinarioImpl un metodo "privato" a cui delegare la scansione ricorsiva (e lo dichiari come vuoi).

Dall'esterno (e per soddisfare la interfaccia AlberoBinario) è solo necessario che ci sia metodo List<T> preordine(). Poi cosa AlberoBinarioImpl faccia all'interno, di nascosto, non conta per il "resto del mondo".

Tuttavia non ci sarebbe nemmeno bisogno di un metodo privato. A te basta invocare preordine() sul left e poi sul right. Hai 2 liste come risultato e con il info corrente componi tu una unica lista da restituire. Il left farà la stessa cosa, il right idem, il left del left idem, ecc....

[Tallid]

Originariamente inviato da alka
Posta il codice che hai scritto, così gli utenti possono suggerire migliorie e/o correzioni.

Il codice che ho scritto è l'implementazione della classe AlberoBinarioImpl, mi sono espresso male.

Originariamente inviato da andbin
Tuttavia non ci sarebbe nemmeno bisogno di un metodo privato. A te basta invocare preordine() sul left e poi sul right. Hai 2 liste come risultato e con il info corrente componi tu una unica lista da restituire. Il left farà la stessa cosa, il right idem, il left del left idem, ecc....

Si mi sono posto come vincolo l'uso di quella firma senza mascherane altre,
Grazie del consiglio ho provato a scrivere questo:

public List<T> preordine() {
       if(isEmpty())return null;
       //aggiungo radice alla lista
       if(left!=null)left.preordine();//ricorsione su albero sx
       if(right!=null)right.preordine();//ricorsione su albero dx
       //se arrivo qui è una foglia quindi ritorno la lista
    }

Il problema è come fare ad aggiungere un elemento, se non ho un oggetto lista.
La soluzione è forse quella di definire un campo privato List<T> visita all'interno della classe?

[andbin]

Originariamente inviato da Tallid
Il problema è come fare ad aggiungere un elemento, se non ho un oggetto lista.
La soluzione è forse quella di definire un campo privato List<T> visita all'interno della classe?

No, in preordine() istanzi un ArrayList<T>. Ci aggiungi l'info, se c'è, ci aggiungi ciò che proviene dal left, se c'è, ci aggiungi ciò che proviene dal right, se c'è e restituisci.
Ogni invocazione di un preordine() insomma crea una lista che poi restituisce .... non è il massimo della efficienza, lo so, ma è il "prezzo" da pagare per una tale implementazione.

[Tallid]

Ah credo di aver finalmente compreso...questo codice esegue correttamente, era quello che intendevi?

public List<T> preordine() { 
      List<T> visita=new ArrayList<T>(); 
      if(isEmpty())return null; 
      visita.add(info); 
      if(left!=null){ 
         List<T>visitaSx=left.preordine(); 
         visita.addAll(visitaSx); 
      } 
      if(right!=null){ 
         List<T>visitaDx=right.preordine(); 
         visita.addAll(visitaDx); 
      } 
      return visita; 
}

[andbin]

Originariamente inviato da Tallid
Ah credo di aver finalmente compreso...questo codice esegue correttamente, era quello che intendevi?

public List<T> preordine() { 
      List<T> visita=new ArrayList<T>(); 
      if(isEmpty())return null; 
      visita.add(info); 
      if(left!=null){ 
         List<T>visitaSx=left.preordine(); 
         visita.addAll(visitaSx); 
      } 
      if(right!=null){ 
         List<T>visitaDx=right.preordine(); 
         visita.addAll(visitaDx); 
      } 
      return visita; 
}

Sì, con solo una piccola nota: io personalmente non restituirei un null ma al massimo una lista "vuota".
Perché se è empty ad un livello sotto ti restituirebbe null e tu lo aggiungeresti alla lista al livello di sopra.

[Tallid]

ok,capito grazie mille!