esercizio su alberi

[ste9213]

Buongiorno,ho un problema con un programma che mi chiededi copiare in un array tutti i nodi di un albero.io ho provato a farlo solamente che non mi copia nulla nell'array.
vi lascio il codice che ho prvato a scrivere,grazie in anticipo.
il metodo che non funziona è copiadati

public class BinaryTree
{
private BinaryNode root;

public static class BinaryNode
{
private int dato;
private BinaryNode left = null;
private BinaryNode right = null;

public BinaryNode(int dato, BinaryNode left, BinaryNode right)
{
this.dato = dato;
this.left = left;
this.right = right;
}

public BinaryNode(int dato)
{
this(dato, null, null);
}

public BinaryNode(int dato, int left, int right)
{
this(dato, new BinaryNode(left), new BinaryNode(right));
}

public void setDato(int val)
{
dato = val;
}

public int getDato()
{
return dato;
}

public BinaryNode getLeftChild()
{
return left;
}

public void setLeftChild(BinaryNode child)
{
left = child;
}

public BinaryNode getRightChild()
{
return right;
}

public void setRightChild(BinaryNode child)
{
right = child;
}

public int contadati(){

int dati = 0 ;

if(left != null && right != null ||
left == null && right == null)
{
dati = 1 ;
}


if(right != null)
{
dati += right.contadati() ;
}

if(left != null)
{
dati += left.contadati() ;
}


return dati ;
}

public int[] copiadati(){

final int MAX = 100 ;
int[] a = new int[MAX] ;
int i = 0 ;

if(left != null && right != null ||
left == null && right == null)
{

a[i] = dato ;
i = 1 ;


}


if(right != null)
{
right.copiadati() ;
}

if(left != null)
{
left.copiadati() ;
}



return a ;
}

}

public BinaryTree()
{
root = null;
}

public BinaryTree(BinaryNode root)
{
this.root = root;
}

public void setRoot(BinaryNode node)
{
root = node;
}

public BinaryNode getRoot()
{
return root;
}

public void printTree()
{
if (root == null)
System.out.println("albero vuoto");
else
BTreePrinter.printTree(this);
}


public int contadati) {
if(root == null)
return 0 ;

return root.contadati() ;
}

public int[] copiadati(){
if(root == null)
return null ;

return root.copiadati() ;
}

}

[Alex'87]

Indenta il codice e postalo usando il tag CODE, così è illeggibile!

[ste9213]

public class BinaryTree { private BinaryNode root; public static class BinaryNode { private int dato; private BinaryNode left = null; private BinaryNode right = null; public BinaryNode(int dato, BinaryNode left, BinaryNode right) { this.dato = dato; this.left = left; this.right = right; } public BinaryNode(int dato) { this(dato, null, null); } public BinaryNode(int dato, int left, int right) { this(dato, new BinaryNode(left), new BinaryNode(right)); } public void setDato(int val) { dato = val; } public int getDato() { return dato; } public BinaryNode getLeftChild() { return left; } public void setLeftChild(BinaryNode child) { left = child; } public BinaryNode getRightChild() { return right; } public void setRightChild(BinaryNode child) { right = child; } public int contadati(){ int dati = 0 ; if(left != null && right != null || left == null && right == null) { dati = 1 ; } if(right != null) { dati += right.contadati() ; } if(left != null) { dati += left.contadati() ; } return dati ; } public int[] copiadati(){ final int MAX = 100 ; int[] a = new int[MAX] ; int i = 0 ; if(left != null && right != null || left == null && right == null) { a[i] = dato ; } if(right != null) { right.copiadati() ; } if(left != null) { left.copiadati() ; } return a ; } } public BinaryTree() { root = null; } public BinaryTree(BinaryNode root) { this.root = root; } public void setRoot(BinaryNode node) { root = node; } public BinaryNode getRoot() { return root; } public void printTree() { if (root == null) System.out.println("albero vuoto"); else BTreePrinter.printTree(this); } public int contadati() { if(root == null) return 0 ; return root.contadati() ; } public int[] copiadati(){ if(root == null) return null ; return root.copiadati() ; } }

[Alex'87]

Ehm...

Il tag CODE va scritto a mano, il pulsante dell'editor serve a postare una singola riga di codice (lo so, è abbastanza inutile ma funziona così purtroppo...)

[CODE]

tuo codice indentato

[/CODE]

[ste9213]

e ho visto che non sono riuscito a mettere il codice, scusa la mia ignoranza ora faccio come mi hai detto e spero che sia leggibile. grazie

  

public class BinaryTree
{
private BinaryNode root;

public static class BinaryNode
{
	private int dato;
	private BinaryNode left = null;
	private BinaryNode right = null;

	public BinaryNode(int dato, BinaryNode left, BinaryNode right)
	{
		this.dato = dato;
		this.left = left;
		this.right = right;
	}

	public BinaryNode(int dato)
	{
		this(dato, null, null);
	}

	public BinaryNode(int dato, int left, int right)
	{
		this(dato, new BinaryNode(left), new BinaryNode(right));
	}

	public void setDato(int val)
	{
		dato = val;
	}

	public int getDato()
	{
		return dato;
	}

	public BinaryNode getLeftChild()
	{
		return left;
	}

	public void setLeftChild(BinaryNode child)
	{
		left = child;
	}

	public BinaryNode getRightChild()
	{
		return right;
	}

	public void setRightChild(BinaryNode child)
	{
		right = child;
	}

	public int contadati(){

		int dati = 0 ;

		if(left != null && right != null ||
		left == null && right == null)
		{
			dati = 1 ;
		}


		if(right != null)
		{
			dati +=  right.contadati() ;
		}

		if(left != null)
		{
			dati += left.contadati() ;
		}


		return dati ;
	}

   public int[] copiadati(){

	final int MAX = 100 ;
	int[] a = new int[MAX] ;
	int i = 0 ;

		if(left != null && right != null ||
		   left == null && right == null)
		{

				a[i] = dato ;
				i = 1 ;
		}


		if(right != null)
		{
			right.copiadati() ;
		}

		if(left != null)
		{
			left.copiadati() ;
		}
		return a ;
	}

}

	public BinaryTree()
	{
		root = null;
	}

	public BinaryTree(BinaryNode root)
	{
		this.root = root;
	}

	public void setRoot(BinaryNode node)
	{
		root = node;
	}

	public BinaryNode getRoot()
	{
		return root;
	}

	public void printTree()
	{
		if (root == null)
			System.out.println("albero vuoto");
		else
			BTreePrinter.printTree(this);
	}

	 public int aggiornaNodiConNumeroDiFoglia() {
		if(root == null)
		   return 0 ;

		return root.contadati() ;
	}

	public int[] copiadati(){
		if(root == null)
		   return null ;

		return root.copiadati() ;
	}

}

[andbin]

Originariamente inviato da ste9213

  
   public int[] copiadati(){

	final int MAX = 100 ;
	int[] a = new int[MAX] ;
	int i = 0 ;

		if(left != null && right != null ||
		   left == null && right == null)
		{

				a[i] = dato ;
				i = 1 ;
		}


		if(right != null)
		{
			right.copiadati() ;
		}

		if(left != null)
		{
			left.copiadati() ;
		}
		return a ;
	}

Innanzitutto invochi ricorsivamente copiadati ma non usi il valore di ritorno.

Pensa: ad ogni livello di invocazione di copiadati hai: un dato e puoi chiedere ai left/right quello che c'è "sotto". Quanto/cosa c'è sotto i due figli ... non lo sai e infatti copiadati restituisce un int[] apposta.

Quindi o in copiadati "unisci" l'insieme di <dato> + <cosa restituisce left> + <cosa restituisce right> ottenendo un unico array che restituisci (avverrà così ad ogni livello ... è "pesante", lo so ...).

Oppure sfrutti un metodi privato che è quello che entrerebbe nel giro della invocazione ricorsiva e che potrebbe ricevere ad esempio un ArrayList<Integer>. Il copiadati "pubblico" è solo più quello di facciata che fa partire la ricorsione col metodo privato e converte da ArrayList<Integer> a int[].

[ste9213]

ma quindi se usassi il primo metodo che mi hai suggerito dovrei mettere un return davanti ad ogni richiamo ricorsivo e poi dopo, definire il dato da copiare nell array come somma di quello che ritorno sia da destra che da sinistra ??

per il secondo metodo che mi hai detto ho capito se non sbaglio cosa dovrebbe fare ma non riesco ad implementarlo.
scusa non sono cosi ferrato sull argomento ; grazie per l aiuto

[andbin]

Originariamente inviato da ste9213
dovrei mettere un return davanti ad ogni richiamo ricorsivo e poi dopo, definire il dato da copiare nell array come somma di quello che ritorno sia da destra che da sinistra ??

Alla fine di copiadati devi restituire un nuovo array, della "giusta" dimensione, che contiene l'insieme di dato più (se forniti) i valori dal left e dal right.

Originariamente inviato da ste9213
per il secondo metodo che mi hai detto ho capito se non sbaglio cosa dovrebbe fare ma non riesco ad implementarlo.

Il copiadati che hai postato resta quello public di "facciata". Ne avrai un altro private es. copiadatiInterno che riceve un ArrayList<Integer>. L'ArrayList è creato una sola volta dal copiadati e passato ad ogni invocazione (poi ricorsiva) di copiadatiInterno.
In tal modo non devi "restituire" nulla, accodi sempre nell'arraylist e non devi preoccuparti di altro, se non, alla fine di copiadati, di creare un int[] copiando tutti i dati (banale ciclo for).

[ste9213]

scusa ma per "insieme di dato" cosa intendi ? io alla fine del metodo gli restituisco con nel mio caso "return a" l'array e la dimensiona l'ho calcolata tramite il metodo contadati e poi nel main mi da sempre come output un albero che contiene solo 0 ripetuto per la dimensioe dell'rray

[andbin]

Originariamente inviato da ste9213
scusa ma per "insieme di dato" cosa intendi ?

Se parliamo della prima soluzione (non con ArrayList), io dicevo "l'insieme di dato più (se forniti) i valori dal left e dal right".

Che praticamente vuol dire: restituire un nuovo array logicamente composto da:

{ dato, ....<elementi dal left>...., ....<elementi dal right>.... }

P.S. non puoi scriverlo così, ovviamente. Devi determinare lunghezza degli array da left/right (se ci sono), istanziare un nuovo array di lunghezza 1+lenDaLeft+lenDaRight, quindi copiare pedestremente i valori in sequenza.