-----BEGIN PGP SIGNED MESSAGE----- Hash: SHA1
On Sat, Jul 29, 2017 at 09:49:21AM +0200, Urs Liska wrote:
Am 29.07.2017 um 09:15 schrieb tomas@tuxteam.de:
On Sat, Jul 29, 2017 at 12:28:26AM +0200, Urs Liska wrote:
Am 28.07.2017 um 23:31 schrieb tomas@tuxteam.de:
[...]
Der Rückgabewert der rekursiven Funktion ist eine Liste mit den Randwerten der linken und rechten Kinder und dem aktuellen Knoten in der Mitte. "Natürlicher" wäre die Rückgabe von "left + [index] + right",
OK. Darauf wäre ich allerdings nicht gekommen, zumal is_bst einem das Hirn schon auf ein boolean "polt" (is this thing a binary search tree?).
Grrr, das muss ich zugeben. Die Funktion sollte anders heißen. Im Wesentlichen ist es so, dass der Baum in seiner natürlichen Ordnung durchlaufen wird. Sofern eine Fehlerbedingung festgestellt wird, bricht sie ab, andernfalls läuft sie durch und gibt "irgendwas" zurück - dann ist der Baum korrekt.
Semantisch richtig wäre wohl
def main(): tree = TreeOrders() if len(tree.nodes) == 0: print("CORRECT") tree.traverse() print("CORRECT")
Das verführt einem dazu, sich diese "Frage" rekursiv vorzustellen
is_bst(tree): return tree.left.val < tree.val \ and tree.val < tree.right.var \ and is_bst(tree.left) \ and is_bst(tree.right)
(das ist natürlich salopp formuliert, bei Deiner Darstellung des Baums müssen eher solche Dinge stehen wie
self.value(self.left(index)) < self.value(index) ...bzw.
is_bst(self.left(index))...... you get the idea. Man muss natürlich damit klarkommen, dass diese Methoden manchmal None liefern, was den Ausdruck etwas unübersichtlich macht (bei den Vergleichen).
Ich glaube nicht, dass das funktionierten würde. Wenn ich an einem gegebenen Knoten für links und rechts nur einen Boolean-Wert zurückbekomme, kann ich nicht mit dem aktuellen Knoten vergleichen (wie du unten auch schreibst). Daher muss die rekursive Funktion schon die Knoten-Werte des Subtrees zurückgeben.
Ich glaube, ich verstehe, was Du meinst... mein Ansatz würde (vorsicht, ASCII-Grafik):
4 / \ 3 5 / \ 1 6
durchgehen lassen, weil der Teilbaum an 3 "OK" sagen würde, der an 5 auch und 3-4-5 auch ganz manierlich aussieht. Hast recht :)
Ja, natürlich. Am gegebenen Knoten muss ich prüfen, ob der höchste Wert des linken Teilbaums kleiner als und der niedrigste Wert des rechten Teilbaums größer als der aktuelle Wert ist [...]
Sehr richtig. Dann kann Deine Funktion/Methode z.B. "range" heissen, und sie liefert (lo, hi) die gesamte Spannweite des Baums -- das ist ja im wesentlichen, was Du gemacht hast.
Im Moment sind es zwei unterschiedlich geartete Fragen:
Na, was für den Abend. Jetzt habe ich bald Kochdienst :-)
lg - -- tomás