Creare un metodo ricorsivo che clona un albero binario

[goldroger83]

Salve a tutti questo è il mio problema:

Scrivere un metodo RICORSIVO
BinaryTree Copia (Position p)
che invocato su un albero binario T fornisca in output (costruisca) un albero binario che è la copia (clone) del sottoalbero di T radicato nel nodo di posizione p. Occorre usare i metodi dell’interfaccia BinaryTree.

I metodi dell'interfaccia BinaryTree sono:

package tree;
import list.*;
import iterator.*;
public class LinkedBinaryTree implements BinaryTree{

private Position root;
private int size;

public LinkedBinaryTree(){
root=null;
size=0;
}

public int size(){
return size;
}

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

//ritorna true se il nodo v ha almeno un figlio destro o un figlio sinistro
public boolean isInternal(Position v)throws InvalidPositionException{
checkPosition(v);
return (hasLeft(v)||hasRight(v));
}

//ritorna true se il nodo non è un nodo interno
public boolean isExternal(Position v)throws InvalidPositionException{
return !isInternal(v);
}


public boolean isRoot(Position v)throws InvalidPositionException{
checkPosition(v);
return(v==root);
}

public boolean hasLeft(Position v)throws InvalidPositionException{
BTPosition vv=checkPosition(v);
return (vv.getLeft()!=null);
}

public boolean hasRight(Position v)throws InvalidPositionException{
BTPosition vv= checkPosition(v);
return (vv.getRight()!=null);
}

public Position root()throws EmptyTreeException{
if(root==null)
throw new EmptyTreeException("L'albero è vuoto, non ha root");
return root;
}

public Position left(Position v)
throws InvalidPositionException, BoundaryViolationException{
if(!hasLeft(v))
throw new BoundaryViolationException("Non ha figlio sinistro");
return((BTPosition)v).getLeft();
}

public Position right(Position v)
throws InvalidPositionException, BoundaryViolationException{
if(!hasRight(v))
throw new BoundaryViolationException("Non ha figlio destro");
return((BTPosition)v).getRight();
}

public Position parent(Position v)
throws InvalidPositionException, BoundaryViolationException{
if(isRoot(v))
throw new BoundaryViolationException("La radice nn ha padre");
return((BTPosition)v).getParent();
}

public Iterator children(Position v)throws InvalidPositionException{
List children = new NodeList();
if(hasLeft(v))children.insertLast(left(v));
if(hasRight(v))children.insertLast(right(v));
return children.elements();
}

public Iterator positions(){
List positions= new NodeList();
if(size!=0)
inorderPositions(root(),positions);
return positions.elements();
}

public Iterator elements()throws InvalidPositionException{
Iterator positer=positions();
List elementi= new NodeList();
while(positer.hasNext())
elementi.insertLast(((Position)positer.next()).ele ment());
return elementi.elements();
}
//controlla se v è una posizione valida per l'albero
protected BTPosition checkPosition(Position v)
throws InvalidPositionException {
if (v == null || !(v instanceof BTPosition))
throw new InvalidPositionException("Position non valida");
return (BTPosition) v;
}

protected void inorderPositions(Position v, List pos)
throws InvalidPositionException {
if (hasLeft(v))
inorderPositions(left(v), pos); // ricorsione su figlio sinistro
pos.insertLast(v);
if (hasRight(v))
inorderPositions(right(v), pos); // ricorsione su figlio destro
}


public Object replace(Position v, Object o)
throws InvalidPositionException {
BTPosition vv = checkPosition(v);
Object temp = v.element();
vv.setElement(o);
return temp;
}

protected BTPosition createNode(Object elem, BTPosition parent, BTPosition left, BTPosition right){
return new BTNode(elem, parent, left, right);
}

public Position insertLeft(Position p, Object o)throws InvalidPositionException{
if(hasLeft(p))throw new InvalidPositionException
("Non puoi inserire un figlio sinistro, c'è già");
BTPosition dato= checkPosition(p);
BTPosition nuovo= createNode(o,dato,null,null);
dato.setLeft(nuovo);
size++;
return nuovo;
}

public Position insertRight(Position p, Object o)throws InvalidPositionException{
if(hasRight(p))throw new InvalidPositionException
("Il nodo ha già un figlio destro");
BTPosition dato= checkPosition(p);
BTPosition nuovo= createNode(o, dato,null, null);
dato.setRight(nuovo);
size++;
return nuovo;
}

public Position addRoot(Object o)throws NotEmptyTreeException{
if(!isEmpty()) throw new NotEmptyTreeException
("L'albero non è vuoto, impossibile inserire la radice");
size=1;
root=createNode(o, null, null, null);
return root;
}

Qualcuno saprebbe aiutarmi gentilmente? grazie anticipatamente

[Pastore12]

Il codice va messo tra i tag [ code][/ code] o [ php][/ php].
Leggi il regolament.

package tree;
import list.*;
import iterator.*;
public class LinkedBinaryTree implements BinaryTree
{

    private Position root;
    private int size;

    public LinkedBinaryTree()
    {
        root=null;
        size=0;
    }

    public int size()
    {
        return size;
    }

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

    //ritorna true se il nodo v ha almeno un figlio destro o un figlio sinistro
    public boolean isInternal(Position v)throws InvalidPositionException
    {
        checkPosition(v);
        return (hasLeft(v)||hasRight(v));
    }

    //ritorna true se il nodo non è un nodo interno
    public boolean isExternal(Position v)throws InvalidPositionException
    {
        return !isInternal(v);
    }


    public boolean isRoot(Position v)throws InvalidPositionException
    {
        checkPosition(v);
        return(v==root);
    }

    public boolean hasLeft(Position v)throws InvalidPositionException
    {
        BTPosition vv=checkPosition(v);
        return (vv.getLeft()!=null);
    }

    public boolean hasRight(Position v)throws InvalidPositionException
    {
        BTPosition vv= checkPosition(v);
        return (vv.getRight()!=null);
    }

    public Position root()throws EmptyTreeException
    {
        if(root==null)
            throw new EmptyTreeException("L'albero è vuoto, non ha root");
        return root;
    }

    public Position left(Position v) throws InvalidPositionException, BoundaryViolationException
    {
        if(!hasLeft(v))
            throw new BoundaryViolationException("Non ha figlio sinistro");
        return((BTPosition)v).getLeft();
    }

    public Position right(Position v)    throws InvalidPositionException, BoundaryViolationException
    {
        if(!hasRight(v))
            throw new BoundaryViolationException("Non ha figlio destro");
        return((BTPosition)v).getRight();
    }

    public Position parent(Position v) throws InvalidPositionException, BoundaryViolationException
    {
        if(isRoot(v))
            throw new BoundaryViolationException("La radice nn ha padre");
        return((BTPosition)v).getParent();
    }

    public Iterator children(Position v)throws InvalidPositionException
    {
        List children = new NodeList();
        if(hasLeft(v))
            children.insertLast(left(v));
        if(hasRight(v))
            children.insertLast(right(v));
        return children.elements();
    }

    public Iterator positions()
    {
        List positions= new NodeList();
        if(size!=0)
            inorderPositions(root(),positions);
        return positions.elements();
    }

    public Iterator elements()throws InvalidPositionException
    {
        Iterator positer=positions();
        List elementi= new NodeList();
        while(positer.hasNext())
            elementi.insertLast(((Position)positer.next()).element());
        return elementi.elements();
    }
    //controlla se v è una posizione valida per l'albero
    protected BTPosition checkPosition(Position v) throws InvalidPositionException
    {
        if (v == null || !(v instanceof BTPosition))
            throw new InvalidPositionException("Position non valida");
        return (BTPosition) v;
    }

    protected void inorderPositions(Position v, List pos) throws InvalidPositionException
    {
        if (hasLeft(v))
            inorderPositions(left(v), pos); // ricorsione su figlio sinistro
        pos.insertLast(v);
        if (hasRight(v))
            inorderPositions(right(v), pos); // ricorsione su figlio destro
    }


    public Object replace(Position v, Object o) throws InvalidPositionException
    {
        BTPosition vv = checkPosition(v);
        Object temp = v.element();
        vv.setElement(o);
        return temp;
    }

    protected BTPosition createNode(Object elem, BTPosition parent, BTPosition left, BTPosition right)
    {
        return new BTNode(elem, parent, left, right);
    }

    public Position insertLeft(Position p, Object o)throws InvalidPositionException
    {
        if(hasLeft(p))
            throw new InvalidPositionException("Non puoi inserire un figlio sinistro, c'è già");
        BTPosition dato= checkPosition(p);
        BTPosition nuovo= createNode(o,dato,null,null);
        dato.setLeft(nuovo);
        size++;
        return nuovo;
    }

    public Position insertRight(Position p, Object o)throws InvalidPositionException
    {
        if(hasRight(p))
            throw new InvalidPositionException ("Il nodo ha già un figlio destro");
        BTPosition dato= checkPosition(p);
        BTPosition nuovo= createNode(o, dato,null, null);
        dato.setRight(nuovo);
        size++;
        return nuovo;
    }

    public Position addRoot(Object o)throws NotEmptyTreeException
    {
        if(!isEmpty())
            throw new NotEmptyTreeException ("L'albero non è vuoto, impossibile inserire la radice");
        size=1;
        root=createNode(o, null, null, null);
        return root;
    }
} 

Tu come faresti a clonare un albero? Parti dalla radice. Cloni la radice. Poi a uno a uno cloni tutti i figli della radice e al clone della radice assegni come figli i cloni dei figli della radice.
Poi viaggi di ricorsione fino ad arrivare alle foglie.

[goldroger83]

Scusami per non aver messo il codice tra i tag, il mio problema è che non sono molto pratico con la ricorsione....potresti darmi qualche spunto in più?

[alde90]

Penso che sia una cosa del genere:

Crei un oggetto albero nuovo, con root il nodo che gli passi come parametro
Chiami il metodo aggiungiSinistra(copia(nodoSinistra))
Chiami il metodo aggiungiDestra(copia(nodoDestra))

e così via, la condizione di stop la dai quando non ci sono più nodi

Non è chiarissima come spiegazione, ma penso ti aiuterà un po' ;-)

[goldroger83]

ok sei stato chiaro, ci provo e vedo che riesco a fare grazie ti faccio sapere!

[goldroger83]

Niente non ci riesco....non so utilizzare i metodi ricorsivi....mi servirebbe un esempio svolto almeno per provare ad implementare gli altri esrcizi simili, credo che mi sarebbe molto di aiuto...

[alde90]

Bè il classico esempio è il fattoriale:

public int fattoriale(int n){
    if(n <= 1) return 1;
    return fattoriale(n - 1);
}

Questo esempio va bene se è il metodo a richiamare sè stesso. Nel tuo caso, è leggermente diverso il problema, ma fattibile:

Allora viene passato un nodo come parametro. Questo nodo (in un albero a n-nodi e non binario) si può scorrere tramite ricorsione:

public void stampaAlbero(Nodo nodo){
    if(nodo.hasChildes()){//non è l'ultimo nodo
       ListaNodi n = nodo.getChildes();
       for(Nodo nd : n){
           stampaAlbero(nd);
       }
      System.out.println(n.getProperties());//stampa anche sè stesso
   }else{//è l'ultimo nodo
      System.out.println(n.getProperties());
   }

ok ora specializziamo questo algoritmo un pò generale nel caso specifico del binario, che è anche ordinato (scende a sinistra, torna su, và giù a destra )

public Albero copiaAlbero(Nodo nodo){
    Albero a = new Albero(nodo);//albero con root nodo

    if(nodo.hasLeft()){//non è l'ultimo nodo
       Nodo sinistra = nodo.getLeft();
       a.aggiungiSinistra(nodo, copiaAlbero(sinistra));
       }
   }
   if(nodo.hasRight()){//non è l'ultimo nodo
       Nodo destra = nodo.getRight();
       a.aggiungiDestra(nodo, copiaAlbero(destra));
   }
}

Ancora qualche dubbio???

[goldroger83]

grandissimo è bello sapere che nel web c'è sempre qualcuno disposto ad aiutarti! ;-)
grazie 1000!

[Pastore12]

Un metodo ricorsivo è solo un metodo che richiama se stesso... quindi nulla di complicato!

Immagina di avere un metodo clonaNodo che clona un nodo. Cosa deve fare?
0. creare un nodo vuoto
1. clonare il dato contenuto nel nodo
2. clonare il figlio destro e assegnarlo al clone come figlio destro
3. clonare il figlo sinistro e assegnarlo al clone come figlio sinistro

in realtà il passo 0 e 1 si dovrebbero fare in un colpo solo, ma spero non sia un problema...
Comunque il metodo fa i passi 0 e 1. poi arriva al passo 2 e scopre di dover fare un clone di un nodo. Che fregatura! dirai tu.. se sapessi fare il clone di un nodo non starei a scrivere sto metodo!
E invece qui sta il bello della ricorsione: il metodo che stai facendo un giorno funzionerà! per cui puoi far finta che il metodo per clonare un nodo ci sia. Quindi per creare il clone del nodo di destra chiami di nuovo il metodo clonaNodo (prima chiamata ricorsiva).
Questo metodo restituisce un clone del nodo, no? E allora questo clone lo piazzi come figlio destro che stai clonando ora.
Ripeti il tutto per il figlio sinistro (seconda chiamata ricorsiva) e hai finito.

Ovviamente devi stare attento che se il nodo è null, clonaNodo deve restuituire null.

Se hai capito il concetto vedrai che non è per nulla complicato.

[alde90]

Originariamente inviato da Pastore12
bla bla bla

Direi che ci sta bravo Pastore12!! Spiegazione impeccabile