PDA

View Full Version : [java]banale problema di alberi...


dnarod
15-03-2006, 18:38
...che pero non riesco a risolvere...ho una classe albero e una nodo interna ad albero per farci delle cosette, una fra queste è un costruttore che preso un array di interi come parametro, monti l albero cosi: se un nodo contiene array[x] il figlio left avra array[2x+1] ed il figlio right deve contenere array[2x+2] (se uno di questi due elementi non esiste -> null); il tutto ricorsivo ed e ormai consolidata la mia stupidaggine in campo ricorsivo; non ci ho sclerato ancora moltissimo, solo un pomeriggio, ma intravedo che potrebbe farmi dannare parecchio...

dnarod
16-03-2006, 10:26
nessuno?

Angus
16-03-2006, 11:18
nessuno?

Sinceramente credo di non essere l'unico a non aver capito cosa vuoi fare... :confused:

sottovento
16-03-2006, 11:24
/**
* This is an example on implementing tree
*
* @author Sottovento
**/

class MyTreeNode
{
private int datum;
private MyTreeNode left;
private MyTreeNode right;

/**
* Constructor
**/
public MyTreeNode ()
{
this.datum = -1;
this.left = null;
this.right = null;
}

/**
* Constructor
* @param datum information to be stored in node
**/
public MyTreeNode (int datum)
{
this.datum = datum;
this.left = null;
this.right = null;
}

/** Getters **/
public int getDatum () { return datum; }
public MyTreeNode getLeft() { return left; }
public MyTreeNode getRight() { return right; }

/**
* Build up the required tree
* @param data array of integers to be fitted in tree;
* @param startIndex Index of fitting element
* @return the required tree, or null if something goes wrong
**/
public static MyTreeNode buildUp (int[] data, int startIndex)
{
// Check for bounds
if (data == null || data.length <= 0)
return null;

// I make two different tests only 'cause I'm lazy
if (startIndex < 0 || startIndex >= data.length)
return null;

MyTreeNode node = new MyTreeNode (data[startIndex]);
node.left = buildUp (data, 2 * startIndex + 1);
node.right = buildUp (data, 2 * startIndex + 2);
return node;
}

/**
* Prints in preorder
**/
public static void printPreorderTree (MyTreeNode node)
{
if (node != null)
{
System.out.print (" " + node.getDatum ());
printPreorderTree (node.getLeft());
printPreorderTree (node.getRight());
}
}

/**
* Prints in symmetrical order
**/
public static void printSymmetricalTree (MyTreeNode node)
{
if (node != null)
{
printSymmetricalTree (node.getLeft());
System.out.print (" " + node.getDatum ());
printSymmetricalTree (node.getRight());
}
}
}

public class MyTree
{
public static void main (String[] args)
{
int[] vect = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 };

MyTreeNode tree = MyTreeNode.buildUp (vect, 0);

System.out.println ("Print tree in preorder:");
MyTreeNode.printPreorderTree (tree);
System.out.println ();

System.out.println ("Print tree in symmetric:");
MyTreeNode.printSymmetricalTree (tree);
System.out.println ();
}
}

Metti questo codice nel file MyTree.java

Se lo fai girare, ottieni:
Print tree in preorder:
0 1 3 7 8 4 9 2 5 6
Print tree in symmetric:
7 3 8 1 9 4 0 5 2 6
il quale corrisponde all'albero che ti serve


High Flying
Sottovento

Angus
16-03-2006, 11:26
Sinceramente credo di non essere l'unico a non aver capito cosa vuoi fare... :confused:

Ritiro quel che ho detto :fagiano:

rdefalco
16-03-2006, 12:51
...che pero non riesco a risolvere...ho una classe albero e una nodo interna ad albero per farci delle cosette, una fra queste è un costruttore che preso un array di interi come parametro, monti l albero cosi: se un nodo contiene array[x] il figlio left avra array[2x+1] ed il figlio right deve contenere array[2x+2] (se uno di questi due elementi non esiste -> null); il tutto ricorsivo ed e ormai consolidata la mia stupidaggine in campo ricorsivo; non ci ho sclerato ancora moltissimo, solo un pomeriggio, ma intravedo che potrebbe farmi dannare parecchio...

Credo che l'approccio con l'array sia errato: 0 dovrebbe avere come figli 1 e 2, 1 dovrebbe avere 3 e 4

quindi padre = A[x], figlio sinistro A[((x+1)*2)-1], figlio destro A[((x+1)*2]

dnarod
16-03-2006, 13:24
purtroppo non sono io a decidere come fare, altrimenti mai avrei pensato l arzigogolata via dell implementare alberi con array...il problema è che quello che mi serve fare è un costruttore dell albero, ricorsivo, che accetti solo l array di interi come parametro, e che costruisca l albero con left 2i+1 e right 2i+2....grazie sottovento, ho gia capito un po di piu grazie al tuo esempio, ma non è propriamente cio che mi è stato chiesto...cmq basta che in qualche modo adatti il metodo buildup ad essere il metodo d appoggio per la ricorsione, dopodiche lo chiamo nel costruttore e dovrebbe fungere...vi aggiornero :)