Trees in Java?

[Ishildur]

Hallo zusammen
Ich benötige eine simple Tree Datenstruktur in Java? Gibts da nichts in der Klassenbibliothek? Ich meinen nicht einen grafischen Tree wie der von Swing, sondern lediglich eine logische Datenstruktur, um einen Spielbaum zu erstellen! Lg Ishildur

 

[Saxony]

Hiho,

ein einfacher Baum sieht so aus:

public class Tree {

    private TreeNode root;

    public Tree(TreeNode aRoot) {

        this.root = aRoot;
    }
}

public class TreeNode {

    private ArrayList<TreeNode> children = new ArrayList<TreeNode>();    
    private Object data;

    public TreeNode(Object aData) {
        
        this.data = aData;
    }

    public void addChild(TreeNode aNode) {
        
        this.children.add(aNode);
    }

    usw. ...
}

bye Saxony

 

[Ishildur]

Hehe, mir ist schon klar, wie man einen Baum erstellt, ich wunder mich nur, dass Java hier nichts natives anbietet!

 

[maki]

Trees sind nix allgemeines wie Listen, sind schon sehr speziell.

 

[Ishildur]

Das sehe ich anders, denn der ADT eines Trees lässt sich sehr einfach und unkompliziert umschreiben! Das einzig spezielle ist der Node, aber dafür gäbe es ja die Möglichkeit zur generischen Programmierung! Aber ich möchte mich nicht streiten, wenn Java keine Trees in der Klassenbibliothek enthält, dann implementiere ich halt selbst eine!

Mfg Ishildur

 

[Saxony]

@maki
Richtig!

@Ishildur
Deswegen selber schreiben, ist doch schnell gemacht!

bye Saxony

 

[Saxony]

Das sehe ich anders, [...]

Tja, die JavaEntwickler sahen es aber anders als du!

bye Saxony

 

[maki]

Das sehe ich anders, denn der ADT eines Trees lässt sich sehr einfach und unkompliziert umschreiben! Das einzig spezielle ist der Node, aber dafür gäbe es ja die Möglichkeit zur generischen Programmierung! Aber ich möchte mich nicht streiten, wenn Java keine Trees in der Klassenbibliothek enthält, dann implementiere ich halt selbst eine!

Mfg Ishildur

N-äre Trees sind eine Sache, ein Tree mit belibieg vielen Child-Nodes unter einer Node ist wieder etwas ganz anderes.

Die Node an sich ist eigentlich immer ziemlich gleich
Sie sollte auf jedenfall einen Referenz auf ein Datenobjekt haben, so trennt man Struktur (nodes) von Inhalt, gleichzeitig stellt man sicher, das man kein rekurives Netzwerk hat, selbst wenn diesleben Daten öfters im Tree vorkommen, ist einfacher mit umzugehen als wenn eine Node öfters vorkommen kann (ungerichterer Graph).

 

[byte]

Was ist mit TreeMap, TreeSet ?

 

[maki]

Was ist mit TreeMap, TreeSet ?

In beiden geht es nur um die reihenfolge (Ordering), hat nix mit "echten" trees zu tun.
Sollten beide übrigens nicht mit Hibernate verwendet werden

 

[byte]

Was ist denn ein "echter" Baum? Gehts bei Bäumen nicht eh nur um die Ordnung?

 

[maki]

Ordnung ist wichtig, speziell beim traversieren ("Durchschreiten") gibt es prinzipiell 3 Möglichekiten:
- Pre Order
- In Order
- Post Order

Das ist die Reihenfolge in welcher die einzelnen Knoten "abgeschritten" werden.

Ein Set ist einfach nur eine Collection, in der jedes Element nur ein einziges mal vorkommen darf, ein TreeSet stellt nur die Reihenfolge der Elemente sicher wenn man drüberiteriert, bei einer TreeMap ist es ähnlich.

In einem "echten" Tree will ich zB. einen neuen Knoten anhängen (neuer Child node), so das aus dieser Struktur:
(1)
so etwas wird:

   (1)
  /   
(2)

bzw. etwas komplexer:

   (1)
  /   \
(2)   (3)
     /   \
  (4)    (5)

Die Nummer entspürechen übrigens der Reihenfolge beim sog. "Pre Order Traversieren".

 

[AlArenal]

Du kannst das TreeModel überall verwenden, ganz unabhängig vom JTree oder irgendwelchem Swing-Geraffel.

 

[byte]

ein TreeSet stellt nur die Reihenfolge der Elemente sicher wenn man drüberiteriert, bei einer TreeMap ist es ähnlich.

Ja, aber die Reihenfolge und die daraus resultierende schnelle Laufzeit von log(n) wird ja eben genau dadurch erreicht, dass die interne Struktur ein Baum ist (TreeMap: Red-Black tree based implementation of the SortedMap interface.).

In einem "echten" Tree will ich zB. einen neuen Knoten anhängen (neuer Child node), so das aus dieser Struktur: ...

Was Du da so schön grafisch veranschaulichst, ist aber gerade nichts anderes als die Reihenfolge der Knoten.


Es ging mir im Grunde nur darum, dass behauptet wurde, dass Java keinen Tree als Datenstruktur mitliefert. Diese Aussage ist halt falsch.

 

[maki]

Was Du da so schön grafisch veranschaulichst, ist aber gerade nichts anderes als die Reihenfolge der Knoten.

Ach ja?
Dann gib füge doch mal in einem Tree/Map/Set zwei Kinderknoten an (2) an, dann sage mir alle Kinder von (2) und nur die *g*

Welche Javaklasse sollte das können?

Ja, aber die Reihenfolge und die daraus resultierende schnelle Laufzeit von log(n) wird ja eben genau dadurch erreicht, dass die interne Struktur ein Baum ist (TreeMap: Red-Black tree based implementation of the SortedMap interface.).

Es ging mir im Grunde nur darum, dass behauptet wurde, dass Java keinen Tree als Datenstruktur mitliefert. Diese Aussage ist halt falsch. icon_wink.gif

Intern mögen ja Bäume verwendet werden, aber diese internen Datentypen kann ich nicht nutzen in Java, deswegen braucht man seine eigenen Implementierung -> keine Tree-Datenstruktur in der Standard API

Wie gesagt, TreeMap/TreeSet haben zwar "Tree" im Namen, mehr als sortieren tuen sie aber nicht, d.h. alles was die Struktur betrift fehlt...

Ein sog. "Kompositium" kommt einem echten Tree schon viel näher, ich implmentiere alle meine eigenen Trees so.

 

[byte]

Dann gib füge doch mal in einem Tree/Map/Set zwei Kinderknoten an (2) an, dann sage mir alle Kinder von (2) und nur die *g*

TreeMap ist ja wie gesagt kein beliebiger Baum sondern ein Red-Black-Tree, also ein Binary-Search-Tree. Warum sollte ich da genau an (2) irgendwas einfügen?

OK, Du hast natürlich insofern recht, dass man bei TreeMap/TreeSet nicht beliebig auf den Baum zugreifen kann. Nichts desto trotz ist Sinn und Zweck eines Binary Search Trees das Laufzeitverhalten. Ich möchte Objekte speichern und schnell wiederfinden. Genau das erreiche ich mit TreeMap/TreeSet. Ich finde Objekte in O(log n) wieder.


Ich glaube aber, meine Argumentation geht an dem Thread vorbei, da es ja offenbar um beliebige Baumstrukturen geht. :roll:

 

[AlArenal]

Darf ich fragen, was euch an TreeModel nicht gefällt, dass ihr es so scham- und wortlos übergeht?

 

[maki]

Persönlich kann ich mit dem Interface nix anfangen, mir fehlen da eigentlich alle interessanten Methoden... mit so etwas schon eher: http://sujitpal.blogspot.com/2006/05/java-data-structure-generic-tree.html