Disclaimer: Dieser Thread wurde aus dem alten Forum importiert. Daher werden eventuell nicht alle Formatierungen richtig angezeigt. Der ursprüngliche Thread beginnt im zweiten Post dieses Threads.
11.5 Binärer Suchbaum
Hallo, ein paar kleine Fragen zu der Aufgabe:
-
Können wir davon ausgehen, dass beim Suchbaum die kleineren Elemente immer nach links geschoben werden oder müssen wir beide Fälle betrachten?
-
Können auch Bäume, bei denen zweimal der gleiche Wert vorkommt, Suchbäume/Heaps sein? Also zB bei einem Suchbaum, müssen die Elemente links immer kleiner oder nur kleiner gleich dem momentanen sein?
Danke.
- Um zu prüfen, ob es wirklich ein Suchbaum ist, musst du natürlich auch prüfen, ob im linken Teilbaum nur kleinere und im rechten nur größere Elemente sind. Worin bestünde sonst der Test?
- Voraussetzung bei Suchbäumen: Links ist alles kleiner, rechts ist alles größer.
Bei Heaps: Ein Knoten muss das größte (oder bei minheaps kleinste) Element des Teilbaumes sein, dessen Wurzel er darstellt.
Also nein, nur unterschiedliche Werte ^^
Die Konvention ist glaube ich schon, dass in einem Binären Suchbaum kleinere Werte links einsortiert werden. Man kann einen Binären Suchbaum aber natürlich auch andersherum implementieren. Mein Test ist bisher auf ersteres beschränkt. Ein klärendes Statement wäre hier hilfreich.
- Ich wuerde mich da an die Definitionen in den Folien halten, wonach der linke Teilbaum kleiner sein muss als der rechte.
- In BSTs muessen alle Kinder echt kleiner bzw. echt groesser sein, in Heaps jedoch nicht. Da sind durchaus auch Elemente mit den gleichen Wert wie die Wurzel erlaubt.
Würde es sich bei Teilaufgabe a) anbieten, die Halde als Array abzuspeichern, oder geht es ohne Array besser?
Warum willst du ueberhaupt etwas abspeichern? Du bekommst den Baum, den du ueberpruefen sollst, doch uebergeben?
Da kann man wunderbar rekursiv drueber laufen, um die Haldeneigeschaft fuer jeden Teil-Baum zu ueberpruefen.
Hey, hätte auch noch eine Frage:
bei der isBinarySearchTree() widersprechen sich die Aufgabenstellungen im Quellcode zu denen in der Angabe.
=> muss man oder kann man eine Hilfmethode für die Rekursion machen?
Und wenn man MUSS, was soll diese Hilfsmethode bezwecken?
(meine momentane Implementierung scheint auch zu funktionieren)
MfG
Bist du dir da sicher? Wenn du keine globalen Variablen dafür missbrauchst hast, halte ich das für sehr unwahrscheinlich…
Hast du auch wirklich sichergestellt, dass alle Werte der Teilbäume kleiner bzw. größer als die Wurzel sind?
ja, da die < Relation transitiv ist dürfte ich das gewährleistet haben.
=> ist der linkeKind < als die Wurzel und vom linkenKind der linkeKind < als der linkeKind der Wurzel => der LinkenKindLinkenKind < Wurzel
Und damit habe ich das eigentlich gesichert ^^
alsoooo… MUSS man eine Hilfmethode implementieren?
Bist du dir sicher, dass du bspw. diesen Baum nicht fälschlicherweise als BST klassifizierst:
7
l: null
r: 9
l: 4
r: null
Kann deine Implementierung das hier?
10
/ \
2 23
/
1 15
ahhh jaa… danke XD
Ich sag auch mal Danke 
[quote]
Kann deine Implementierung das hier?
10
/ \
2 23
/
1 15
[/quote] Ich habe noch eine frage zu dem TreeGenerator: jeweils die letzte new Node Anweisung die man dann mit dem return zurückgibt, das ist doch die oberste Wurzel (also auf das Bsp bezogen wäre das die 10) oder ?
Ja
b) neue Methode einführen
Hallo Zusammen,
darf man die neue Methode auch in der Klasse Node implementieren?
11.5 Testfälle
Hallo,
da noch keine Testfälle erstellt worden sind, hier ein kleiner Versuch meinerseits (es wird andgenommen, dass in Heaps gleiche Werte vorkommen dürfen, in BinSearchTrees nicht - das vielleicht als Anmerkung)
Die Testfälle sollten die gröbsten Fehler abdecken, jedoch haben/sind sie keine(!) Garantie auf Korrektheit. Besonders bei den Fehlermeldungen sollte noch einmal geprüft werden, ob die Aussage korrekt ist.
Hierzu einfach den entsprechenden Test-Baum im code ansehen. Also falls jemand noch Ideen hat bzw. Fehler findet oder Kritik äußern will…feel free to submit 
Attachment:
TreeCheckerTest.java: https://fsi.cs.fau.de/unb-attachments/post_137901/TreeCheckerTest.java
1 Like
Du gibst Node doch nicht ab, du lädst schließlich nur TreeChecker.java hoch, demnach kann EST ja gar nicht wissen, was du da in Node implementiert hast.
@imp, danke für die Testfälle!
Ich hätte jedoch noch einmal eine grundsätzliche Frage zu den Binären Suchbäumen. Es gelten ja innerhalb des Baumes viele zusätzliche Bedingungen. Die Kinder eines Teilbaumes müssen auch auf die Eltern des Teilbaumes, die Eltern der Eltern und auch natürlich auf die Größe im Vergleich zur Wurzel geprüft werden. Ich tue mir mit dem Teile und Herrsche Prinzip bei so vielen Bedingungen sehr schwer^^. Zurzeit teste ich nur das Verhältnis zu der Wurzel des betrachteten Teilbaumes und versuche jetzt ein System in den Rest der Bedingungen rein zu bekommen, was mir aber wirklich schwerer fällt als gedacht. Meine Arbeit mit den Übungsblättern der letzten Monate hat mir gezeigt, dass ich immer einen Tag dann damit verschwende 10 Methoden zu konstruieren, versuche alles abzudecken, dabei wird die Rekursion immer iterativer, auch wenn ich das Prinzip des Ablaufen des Baumes durchaus verstanden habe, fällt es mir immer schwer bei dem Teilproblem nicht auf die Informationen zuvor zugreifen zu können. Also zb. ElternDerEltern.getVaule(). Deshalb zerbreche ich mir jetzt den Kopf wie ich in die min max Schlüssel aus der Aufgabenstellung diese Problemstellung reinbekomme. So wie ich das sehe kann ich in der Rekursion doch gar nicht wissen wo genau ich im Baum gerade bin, ob links oder rechts der Wurzel zb. Wie kann ich dann in der Rekursion der Rekursion der Rekursion wissen, welchen max Schlüssel ich gerade benötige, zb. Wurzel.getValue() oder Eltern der Eltern.getValue().
Sorry für den langen Text.^^ Meine Frage bezieht sich darauf, ob bsp. ein Array klug wäre, oder ob es auch simpler geht.
Schönes Wochenende an alle und danke schon mal für die Hilfe 
Um es kurz zu fassen : es geht auch simpler! Im Prinzip ist eine Hilfestellung schon in der Angabe gegeben :
Das hört sich doch schon einmal gut an
Tipp : Zeichne dir einen binären Suchbaum auf und schreibe dir zu jedem Knoten/Blatt die min/max-Werte auf. Hierbei könnte dir etwas auffallen…