Implementazione albero

[camilla_24]

Ciao a tutti, dopo molte ricerche in rete non sono ancora riuscita a trovare un semplice esempio di implementazione di un albero non binario in java, qualcuno può per favore postarmi una soluzione semplice su cui posso basarmi o dove cercarla?
grazie mille

[bstefano79]

http://download.oracle.com/javase/1....eTreeNode.html

[camilla_24]

la documentazione java relativa l'avevo già letta grazie cmq! Volevo capire come creare una classe di tipo Nodo e una relativa classe Albero molto semplice..mi consigli di fare un extend di quelle esistenti per aggiungere ciò ke mi serve?

[lolide]

Non ho capito la domanda ... cioè non sai creare la classe Albero e Nodo che significa? Che vorresti un esempio di implementazione? Oppure che vorresti un link sulla teoria?
E poi non è molto corretto estendere dalla classe d'esempio che ti hanno linkato sopra. Quella è un esempio di implementazione da cui puoi prendere spunto, ma è riferito piu' che altro al JTree, non ad un piu' generico Albero.

[unomichisiada]

Originariamente inviato da camilla_24
Ciao a tutti, dopo molte ricerche in rete non sono ancora riuscita a trovare un semplice esempio di implementazione di un albero non binario in java, qualcuno può per favore postarmi una soluzione semplice su cui posso basarmi o dove cercarla?
grazie mille

Devi implementare un ambero n-ario quindi? Cioè un albero i cui nodi possono avere da zero a n-figli? Se si allora leggiti questo , si suggeriscono un paio di implementazioni possibili , proprio in java per altro...
La mia domanda nasce dal fatto che "non binario" non vuol dire molto...devi specificare meglio.

[camilla_24]

Scusate mi sono spiegata male, il discorso è che dovrei costruire un un albero i cui nodi possono avere n figli e questo albero è completo in quanto le foglie di questo sono tutte allo stesso livello..,il mio problema è che i nodi devo essere di 4 tipi diversi(basterebbe un attributo) e che si possa risalire al padre ai suoi figli o foglie per esigenze di progetto,volevo capire se mi era più conveniente scrivere io due classi con relativi metodi per l'implementazione dell'albero.

[unomichisiada]

Originariamente inviato da camilla_24
Scusate mi sono spiegata male, il discorso è che dovrei costruire un un albero i cui nodi possono avere n figli e questo albero è completo in quanto le foglie di questo sono tutte allo stesso livello..,il mio problema è che i nodi devo essere di 4 tipi diversi(basterebbe un attributo) e che si possa risalire al padre ai suoi figli o foglie per esigenze di progetto,volevo capire se mi era più conveniente scrivere io due classi con relativi metodi per l'implementazione dell'albero.

Direi decisamente che ti conviene scrivere tu "due classi con relativi metodi" . La proprietà di completezza direi che la devi garantire in fase di inserimento e cancellazione. Per il resto ti serve una variante di albero n-ario (leggi il link che ti ho postato in cuii ci sono delle implementazioni) con puntatori al padre (da popolare in fase di inserimento).
Posta il codice e se hai problemi si vede. Ciao

[lolide]

Originariamente inviato da camilla_24
Scusate mi sono spiegata male, il discorso è che dovrei costruire un un albero i cui nodi possono avere n figli e questo albero è completo in quanto le foglie di questo sono tutte allo stesso livello..,il mio problema è che i nodi devo essere di 4 tipi diversi(basterebbe un attributo) e che si possa risalire al padre ai suoi figli o foglie per esigenze di progetto,volevo capire se mi era più conveniente scrivere io due classi con relativi metodi per l'implementazione dell'albero.

Uhm.. è come la struttura dei documenti XML. Sono tutti nodi, e il root node non ha parent. Se il tuo intento è quello di parsare un documento XML, allora ti basta usare la libreria DOM. Altrimenti, potresti studiarti il meccanismo che usa sempre quella libreria, cioè un Document (che estende Node, in quanto anch'esso è un nodo ma senza nodi child) root, con vari Node.
Una struttura tipo appunto può essere

public class Nodo {
    protected Collection<Nodo> childCollection;
    protected Nodo parent;
}

public class Tree extends Nodo {
    public Tree () {
        parent = null;
    }
}

[camilla_24]

Scusate ma vorrei un consiglio su come realizzare un metodo che sia in grado di restituirmi il nodo padre di un nodo figlio creato in questo albero..ecco le tre classi che ho implementato..
grazie

import java.util.*;


@SuppressWarnings("unused")
public abstract class Node {
private final int data;
private final String type;


public Node(int data, String type) {
this.data = data;
this.type=type;
}

public String getType(){
return type;
}

public int getData(){
return data;
}

public int size(){
return 1;
}

public boolean contains (int i){
return data == i;
}
}


@SuppressWarnings("unused")
public class Leaf extends Node{

public Leaf(int data, String type){
super(data,type);

}

public String type(){
return super.getType();
}

public int size(){
return super.size();
}

public boolean contains(int i){
return super.contains(i);
}

@Override public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(getData()).append(" " );
return sb.toString();
}

@Override public boolean equals(Object o){
if(!(o instanceof Leaf))
return false;
Leaf l = (Leaf)o;
return getData() == l.getData();
}
}

import java.util.*;
public class InternalNode extends Node{
private final List<Node> children;

public InternalNode(int data,String type, List<Node> children){
super(data, type);
this.children = children;
}

public List<Node> getChildren(){
return children;
}

public String getType(){
return super.getType();
}

@Override public int size(){
int size = 1;
for(Node n : children){

size += n.size();
}
return size;
}

@Override public boolean contains(int i){
if(getData() == i)
return true;
boolean ret = false;
int j = 0;
while(!ret && j < children.size()){
ret = children.get(j++).contains(i);
}
return ret;
}

@Override public String toString(){
StringBuilder sb = new StringBuilder();
sb.append(getData()).append(" " ).append(children.toString());
return sb.toString();
}

@Override public boolean equals(Object o){
boolean ret = false;
if(!(o instanceof InternalNode))
return ret;
InternalNode n = (InternalNode)o;
return (getData() == n.getData() && children.equals(n.children));
}
}

import java.util.*;
@SuppressWarnings("unused")
public class Tree {
private final Node root;

public Tree(Node root){
this.root = root;

}
public String toString() {
return root.toString();
}

public String getType(){
return root.getType();
}
public int size() {
return root.size();
}

public boolean contains(int i) {
return root.contains(i);
}

public boolean equals(Object o) {
return root.equals(o);
}
}