Guten Tag ,
Wollte mir mal hier noch rat holen.
Folgendes Problem beim Implementieren von einem BinarySearchtree:
Aufbau mit einem Interfacepublic interface BinarySearchTree { mit den Eigenschaften:
public interface BinarySearchTree {
public T[] toArray();
public boolean find( T value );
public void insert( T value );
public void delete( T value );
public Iterator iterator();
public Iterator preOrderIterator();
public Iterator levelOderIterator();
Gehen Sie davon aus dass der Typ T das Interface java.lang.Comparable
implementiert. (Dies tun z.B. Integer und Double). Schränken Sie
den Generic Parameter entsprechend ein.
– das Interface BinarySearchTree implementieren.
– Beim zurückgegebenen Iterator sollen Sie einen java.util.Iterator
zurückgeben.
– Des weiteren sollen beide Bäume das Interface java.lang.Iterable
implementieren.
Die Schwierigkeit in der Aufgabe liegt das ich die Funktionen Suchen Finden Löschen Iterativ anlegen muss damit ich möglichst hohe Werte einsetzen kann , und das programm relativ schnell durchläuft!
Ich habe das Problem das ich noch nichtmal das Grundgerüst erstellt habe, und hoffe auf Vorschläge um eine Funktionsfähigen Code zu erstellen :rolleyes:
fertige Implementierungen findet man doch wie Sand am Meer, etwa
Rekursionen kann mit Zwischenvariablen und vielleicht noch Markierungen an den Knoten halbwegs auch iterativ lösen
‘hohe Werte einsetzen’ klingt komisch und dass Rekursion langsam ist, wäre vor Optimierungen zu beweisen,
wenn es nicht explizit deine Aufgabe ist, warum sich damit abmühen?
[quote=Unregistriert]Gehen Sie davon aus dass der Typ T das Interface java.lang.Comparable
implementiert. (Dies tun z.B. Integer und Double). Schränken Sie
den Generic Parameter entsprechend ein.[/quote]
Das macht man mit sogenannten Bounds. Die sind zunächst irgendwie komisch anzuschauen, aber eigentlich total easy zu verstehen, wenn man kontrete Beispiele, wie dieses hier hat. So geht’s BinarySearchTree<T extends Comparable<T>>
[quote=Unregistriert;89263]– Des weiteren sollen beide Bäume das Interface java.lang.Iterable
implementieren.[/quote]
Das dann auch mit in die Interfacedeklaration und es wird daraus: BinarySearchTree<T extends Comparable<T>> extends Iterable<T>
Hast du zumindest schon einen rekursiven Ansatz, und/oder versucht, den in was iteratives umzuwandeln? (Rekursion ist nicht per se langsam, man muss nur ggf. aufpassen, wenn man einen degenerierten Baum hat, dass man nicht in einen StackOverflowError reinrennt…)
Danke Schonmal, was mich beschäftigt ist nicht die Normale Such Find und delete Funktion sondern das dann nicht Rekursiv sondern Iterativ zu lösen. Das mit den Werten ist z.b das ich 1 Millionen einsetzen könnte ohne das es stunden dauern würde. Aber mir fällt es ja schon schwer das Interface mit den ganzen Implementierung hinzukriegen bzw. ein Gerüst wo wenigstens das Iterative Suchen Löschen Finden geht :verzweifel: Danke aber schon für die Hilfestellung!
*** Edit ***
Und macht man den LvL Order nicht mit einer Que? bzw. was mit einem Stack
Mir ist die Frage nicht ganz klar. Natürlich könnte man jetzt den erstbesten Code Copy+Pasten, aber … darum geht es wohl nicht. Ich nehme übrigens mal an, dass bei den “zwei” Bäumen von denen da die Rede ist genau eine Iterative und eine Rekursive Implementierung gemeint ist, oder? Hast du schon eine von beiden, oder Ansätze für eine, oder noch GAR nichts?
Also da hab ich ausversehen die Aufgabenstellung verdreht, das soll nur bei diesem einen Binären Suchbaum sein nicht " zwei ". Die Funktionen Search delete Insert sollten alle Iterativ sein , nichts Rekursiv. Und die Pre und lvl order , in einem Stack/qeue und das alles mit einem Interface.Das macht das ganze ziemlich kompliziert
und jede Wiederholung von kompliziert macht es noch komplizierter…
im Moment klingt alles danach als könntest du kaum eine Klasse an sich definieren, oder die normalen Methoden,
wobei letztlich mit Abschreiben aus Internet ohne Programmierfähigkeit möglich und eigene Version geradezu eine nicht ganz leichte Aufgabe
irgendwann musst du anfangen, irgendwas zu tun,
auf Details eingehen, in Worte fassen was eine der Methoden nach rekursiven Code eigentlich macht,
Ideen für eine Schleifen-Variante entwickeln usw.
bisher gibts in diesem Thread (letztlich von allen Seiten) nur leere Worte,
vielleicht bis jemand den kompletten Code zur Aufgabe postet, dann wäre wirklich nichts mehr zu besprechen…
Die Main , und in der Mitte noch die anstehenden Iterationen mit Pre+Lvl order
package blabla;
public class MyBinaryTree<E extends Comparable<E>>{
E head;
MyBinaryTree<E> left;
MyBinaryTree<E> right;
MyBinaryTree() {
head = null;
left = null;
right = null;
}
public boolean isEmpty() {
return head == null && left == null && right == null;
}
public boolean add(E item) {
if (isEmpty()) {
head = item;
left = new MyBinaryTree<E>();
right = new MyBinaryTree<E>();
return true;
} else if (head.compareTo(item) == 0) {
// System.out.println("Duplikat gefunden, breche ab.");
return false;
} else if (item.compareTo(head) < 0) {
// System.out.println("Traversiere links.");
left.add(item);
} else {
// System.out.println("Traversiere rechts.");
right.add(item);
}
return false;
}
private class bla<T> implements Iterator<T>{
@Override
public boolean hasNext() {
// TODO Auto-generated method stub
return false;
}
@Override
public T next() {
// TODO Auto-generated method stub
return null;
}
@Override
public void remove() {
// TODO Auto-generated method stub
}
}
public boolean remove(E item) {
if (isEmpty()) {
return false;
}
if (item.compareTo(head) == 0) {
// Fall 1: Knoten ist ein Blatt, entferne direkt
if (left.isEmpty() && right.isEmpty()) {
System.out.println("entferne: " + head);
head = null;
left = null;
right = null;
return true;
// Fall 2: Knoten hat ein Kind, setze Kind an seine Stelle
} else if (!left.isEmpty() & right.isEmpty()) {
head = left.head;
left = left.left;
right = left.right;
return true;
} else if (left.isEmpty() & !right.isEmpty()) {
head = right.head;
left = right.left;
right = right.right;
return true;
// Fall 3: Knoten hat zwei Kinder:
// - setze linkesten Knoten im rechten Teilbaum an seine Stelle
// - oder setze rechtesten Knoten im linken Teilbaum an seine Stelle
// - verbinde eventuelle dran hängende Knoten mit dem vorherigen
} else if (!left.isEmpty() & !right.isEmpty()) {
// TODO
}
}
return left.remove(item) & right.remove(item);
}
public int nodeCount() {
if (isEmpty()) {
return 0;
}
return left.nodeCount() + right.nodeCount() + 1;
}
public int deepest() {
return deepest(0);
}
public int deepest(int i) {
if (isEmpty()) {
return 0;
}
int L = left.deepest()+1;
int R = right.deepest()+1;
if (L > R) {
return L;
} else {
return R;
}
}
}
Testklasse welche noch nicht viel kann
public static void main(String[] args) {
MyBinaryTree<String> a = new MyBinaryTree<String>();
a.add("z");
a.add("b");
a.add("c");
a.add("a");
a.add("d");
```
Interface:Das aber auch noch nicht mit den anderen dingen zusammen spielt.
```public interface BinarySearchTree {
public T[] toArray();
public boolean find( T value );
public void insert( T value );
public void delete( T value );
public Iterator<T> iterator();
public Iterator<T> preOrderIterator();
public Iterator<T> levelOderIterator();
}
Ein erster Schritt könnte schonmal sein
public class MyBinaryTree<E extends Comparable> implements BinarySearchTree
zu schreiben und die IDE die fehlenden Methoden erzeugen zu lassen. Einige müssen auch nicht neu erzeugt, sondern lediglich umbenannt werden: “add” muss eben “insert” heißen, aber soll (so wie ich das sehe) das gleiche machen.
Dann kannst du mal schauen, die “einfacheren” Methoden iterativ zu implementieren (was ja, falls ich das richtig verstanden habe, gefordert ist). Z.B. bei “insert” wäre das nicht soo schwierig
public void add(E item)
{
if (isEmpty()) {
head = item;
left = new MyBinaryTree<E>();
right = new MyBinaryTree<E>();
return;
}
MyBinaryTree<E> current = this;
while (true)
{
if (...) {
current.head = item;
return;
}
if (...compare...) {
current = left;
} else {
current = right;
}
}
}
Uh STIMMT, habe nun die Inserts in der Main und im Interface verbessert! Eine Frage zu den MyBinaryTree<E ,
ab der Zeile 11-21 ist das der Ansatz für Iterativ? welche ich dann durch den unteren Teil der insert (add) Methode ersetzen kann?
Ja, der Ansatz für eine iterative Bearbeitung ist eine Schleife. Nein, du kannst das nicht einfach durch den unteren Teil deiner Methode ersetzen, du musst schon dein Hirn einschalten und das fertigprogrammieren. Im Grunde ist das ganze wirklich keine Hexerei, anstatt die Methode mit anderen Parametern rekursiv neu aufzurufen sorgst du einfach dafür, dass beim nächsten Schleifendurchlauf auf andere Parameter eingegangen wird.
Jaa das klingt so einfach, aber für mich ist das schon eine ziemliche große Hexerei :D. Wenn man soviele Fehler im Code hat und manche schritte nicht versteht wirds bisschen schwierig. Aber bin über die ganzen tipps schon sehr froh
Ja, wie ‘Unregistered’ schon angedeutet hat: Wenn man einen rekursiven Aufruf macht, bedeutet das ja quasi, dass man alle Methodenparameter nochmal “frisch” (ggf. mit neuen Werten) bekommt. Theoretisch (!) kann man eine Rekursion sogar ziemlich mechanisch in eine Iteration umwandeln, aber … es stimmt schon, dass das in manchen Fällen tricky sein kann. Speziell bei den Iteratoren: Da muss man sich genau überlegen, wie man den aktuellen “Zustand” der Iteration im Iterator “konserviert”. Deswegen hatte ich gemeint: Am besten erstmal mit den “einfachsten” Methoden anfangen, dann kriegt man vielleicht ein Gespür dafür. (Und BTW, falls es dich beruhigt: Ich würde so einen Iterator auch nicht aus dem Handgelenk hinschreiben - da muss man (müßte ich) schon ein bißchen überlegen…)