Hoffe jemand kann mir ein paar Tips geben:binärer Suchbaum

[Susanne85]

Hallo,
ich habe dieses Semester mein Studium begonnen, aber bin in Java noch nicht so fit und habe jetzt ne super schwere Hausaufgabe bekommen bei der ich nicht so recht weiter komme.

Es soll in Java ein Binärer Suchbaum von über die Tastatur eingegebenen integer-keys angelegt werden, der in der Reihenfolge der Eingaben aufgebaut wird. An diesem Baum soll die Suche nach beliebigen integer-Keys möglich sein, indem über die Tastatur ein solcher key eingegeben wird und der gefunde Wert auf dem Bildschirm ausgegeben wird bzw. die Mitteilung erfolgt, das kein solcher Wert gefunden wurde. Weiterhin soll es möglich sein, jederzeit neue Elemente hinzuzufügen oder zu entfernen.

Wäre lieb wenn Ihr mir helfen könntet, weil ich im Moment noch nicht so recht weiß wie ich das ganze programmieren soll. Liebe Grüsse, Susanne.

[bischi]

Naja - die Aufgabe lösen werd ich dir jetzt nicht (sonst wär ja der ganze Spass weg ;) )

Ich würde das ganze grundsätzlich so aufteilen:

Klassen: Knoten, Baum (mit root-Knoten) und dein Programm

Vielleicht kannst du aber auch konkret sagen, was genau du kannst, dann kann man konkret Tipps geben.

Weisst du:
- Eingaben abfangen?
- Ausgaben machen?
- Wie eine Klasse schreiben?
- Wie ein binärer Suchbaum funktioniert? Aufbau/Suchen?
- Unterschied zwischen "Pointern" und Werten?
- Werte auf Korrektheit prüfen (bzw: ist die eingegebene Zahl ein int)

MfG Bischi

PS: Rein zum Thema Java findest du bei mir auf der HP jede Menge toller Bücher (www.walfisch.ch.vu --> Tuts und Bücher --> Java). Besonders empfehlenswert ist meiner Meinung nach das www.javabuch.de - die rein Sprachtechnischen Probleme sollten sich damit lösen lassen

[Susanne85]

Danke für die schnelle Antwort,
wie ein binärer Suchbaum aussieht und wie er grundsätzlich Funktioniert weiss ich, auch wie ich eine Ein/Ausgabe unter Java mache und eine Klasse erstelle, aber mir fehlt eher der Zusammenhang für das Gesamte, deshalb wäre es super ein konkretes quelltext-Beispiel zu haben damit ich es nachvollziehen kann :-(

[bischi]

Also abstrakt irgendwie so was:


Klasse: Node[
void Node() //Konstruktor - macht nichts
void setNode(int value) //gebe dem Knoten einen Wert
void setLeftFollower(Node left) //Speichere einen "Pointer" auf den linken Folgeknoten
void setRightFollower(Node right) //analog

int getValue() //Gibt Knotenwert zurück
Node getLeft() //Gibt eine Referenz auf den Linken Folgeknoten
Node getRight() //analog
]


Klasse: Tree[
private Node root;

void Tree(int value) //Erstelle einen neuen Baum mit einem Rootknoten mit Wert value. Dabei den root-Knoten initialisieren
void insert(int value) //Füge einen neuen Knoten hinzu, indem du schaust, ob kleiner/grösser als aktueller Wert. Danach entweder selben Vorgang rekursiv bei weiterem Knoten an gewünschter Stelle und wenn da kein Knoten vorhanden, diesen neu erstellen und verlinken über setLeft /setRight

void search(int value) // Rekursives suchen - sollte selbsterklärend sein
]

Klasse: Programm[
main:{
starten;
einlesen--> Baum erstellen;
while(neueElemente): einlesen, Baum vergrössern;
suchen und ausgabe auswerten;
}
]


Jetzt hast du zumindest mal ne Struktur für das ganze (es gäbe wohl noch weitere Varianten). Ich würde vorschlagen, dass du mal ausprobierst, wie weit du mit dem kommst (Achtung: Quellcode immer gleich sauber kommentieren!) und falls Fragen auftauchen, einfach wieder melden.

MfG Bischi

[Susanne85]

Danke schön, das hilft mir schon mal weiter :-)
Zum einfügen und löschen von Werten habe ich mir folgendes Zusammengebaut, was aber erstmal nur ein pseudocode ist, weil ich auch schon etwas c-programmierung habe :confused:

zum Einfügen eines Knotens in einen binären Suchbaum:
baumEinfügen(k,x):
vater := null;
sohn := k.root;
while not (sohn = null)
do vater := sohn;
if x.key < sohn.key
then sohn := sohn.left
else sohn := sohn.right
endif
od
if vater = null
then k.root := x
else if x.key < vater.key
then vater.left := x
else vater.right := x
endif
whileend

zum Löschen eines Knotens in einem binären Suchbaum:
baumLöschen(k,z):
knoten y; /* der zu entfernende Knoten */
knoten x; /* der eventuell hochzuziehende Knoten */
if z.left = null or z.right = null
then y := z
else y := baumNextSuche(k,z)
endif
if y.left null
then x := y.left
else x := y.right
endif

if x null
then x.parent := y.parent
endif

if y.parent = null
then k.root := x
else if y = y.parent.left
then y.parent.left := x
else y.parent.right := x
endif
endif

if y z
then z.key := y.key;
endif

[bischi]

1) Zum Einfügen NUR den Wert übergeben (und den neuen Knoten dann in der Funktion erstellen und als Nachfolgeknoten des Vorgängers definieren)

Ist mir gerade dazu aufgefallen.

MfG Bischi

[Kai__]

Waere nicht Rekursion angebrachter?

Macht die Sache gleich viel leichter zu programmieren und zu verstehen.