# Trees in Java?



## Ishildur (14. Jul 2008)

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 (14. Jul 2008)

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 (14. Jul 2008)

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


----------



## maki (14. Jul 2008)

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


----------



## Ishildur (14. Jul 2008)

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 (14. Jul 2008)

@maki
Richtig!

@Ishildur
Deswegen selber schreiben, ist doch schnell gemacht!

bye Saxony


----------



## Saxony (14. Jul 2008)

Ishildur hat gesagt.:
			
		

> Das sehe ich anders, [...]



Tja, die JavaEntwickler sahen es aber anders als du! 

bye Saxony


----------



## maki (14. Jul 2008)

Ishildur hat gesagt.:
			
		

> 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 (14. Jul 2008)

Was ist mit TreeMap, TreeSet ?


----------



## maki (14. Jul 2008)

byto hat gesagt.:
			
		

> 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 (14. Jul 2008)

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


----------



## maki (14. Jul 2008)

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 (14. Jul 2008)

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


----------



## byte (14. Jul 2008)

maki hat gesagt.:
			
		

> 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 (14. Jul 2008)

> 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 (14. Jul 2008)

> 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 (14. Jul 2008)

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


----------



## maki (14. Jul 2008)

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


----------

