Binärbäume

[rizor]

Hi,

ich hab mal eine Frage.
Gibt es in Java Binärbäume oder muss man sich so eine Klasse selbst schreiben?
Wenn man die selbst schreiben muss, habe ich eine andere Frage.

Ein Baum basiert ja auf einer Wurzel und deren Nachfolgern.
Wie kann ich nun von einem dieser Nachfolger auf die Wurzel zugreifen?

Also meine Klasse sieht so aus:

public class FunctionTree<T> {
    private T                   node;                     //Wurzel dieses Teilbaums
    private FunctionTree<T>     LeftTree;        //Linker Teilbaum
    private FunctionTree<T>     RightTree;      //Rechter Teilbaum
    private int                          NodeDepth     //Tiefe des aktuellen Knotens
}

Nun bruache ich hlat eine Möglichkeit den Baum geordnet zu durchsuchen.

Danke für eure Hilfe.

Gruß
rizor

 

[ARadauer]

Wie kann ich nun von einem dieser Nachfolger auf die Wurzel zugreifen?

je nach dem wie du es implementierst, wenn ein knoten einen sohn knoten erstellt, gibt er sich einfach selbst mit und der sohn kann über diese referenz auf den vater zugreifen.

 

[rizor]

Wie würde das denn vom Code her aussehen?
So gut kenne ich mich mit Java noch nicht aus.

 

[Final_guy]

Hallo rizor,

vielleicht leistet die Klasse java.util.TreeMap der Java (1.5) API das gewünschte? Auszug aus der Beschreibung:

This implementation provides guaranteed log(n) time cost for the containsKey, get, put and remove operations. Algorithms are adaptations of those in Cormen, Leiserson, and Rivest's Introduction to Algorithms.

Also hast Du damit schon mal Zugriffe mit logarithmischem Aufwand. Reicht das schon? Falls Du den Baum selbst implementieren möchtest (auch eine gute Übung, falls Du die Zeit hast) musst du deiner Knotenklasse zusätzlich zu den Referenzen auf die Nachfahren/Kindknoten eben noch eine Referenz auf ihren Vorfahr/Elternknoten im Konstruktor mitgeben.

Ich hoffe, ich konnte Dir damit ein wenig behilflich sein.



[EDIT] @ARadauer: Sorry, unsere Postings haben sich überschnitten. Habe nicht mitbekommen, dass du in der Zwischenzeit auch schon etwas geschrieben hattest.

 

[rizor]

Danke-
Das ist das was ich suche.

Allerdings würde ich trotzdem gerne suchen, wie ich auf die Eltern/Kinder referenziere.
Werde ich bestimmt noch häufiger brauchen.

Danke

 

[0x7F800000]

Warum willst du überhaupt auf die eltern-knoten zugreifen? So wie ich das im Mathe-Subforum mitbekommen hab, willst du doch einen parse-baum für irgendwelche ausdrücke und funktionen schreiben. Beim Parsen brauchst du niemals auf die Eltern zuzugreifen, beim auswerten auch nicht (um den Ausdruck in Klammern auszurechnen braucht man über die umgebung der Klammer gar nichts zu wissen)
Außerdem ist mir nicht klar, was du in diesem Fall mit Generics vorhast: eigentlich reicht simple Polymorphie hier völlig aus.

 

[rizor]

Naja, ich möchte den Baum so allgemein wie möglich halten.
Stimmt, bruach ich wirklich nicht.
Aber es interessiert mich trotzdem wie man sowas mit Eltern/Kind machen würde.

 

[0x7F800000]

wie bei jedem beliebigen Objekt A die eine Referenz auf objekte der klasse B haben soll:

class A{
   B referenceToB;
   public A(B _ref, ...){
        referenceToB=_ref;
   }
}

in diesem konkreten fall stimmen A und B eben überein:

class A{
   A parent;
   
   public A(A _parent,...){
      parent=_parent;
   }
}

 

[rizor]

Danke.