stellen binäre Suchbäume in Python
-
27-09-2019 - |
Frage
Wie kann ich binäre Suchbäume in Python darstellen?
Lösung
class Node(object):
def __init__(self, payload):
self.payload = payload
self.left = self.right = 0
# this concludes the "how to represent" asked in the question. Once you
# represent a BST tree like this, you can of course add a variety of
# methods to modify it, "walk" over it, and so forth, such as:
def insert(self, othernode):
"Insert Node `othernode` under Node `self`."
if self.payload <= othernode.payload:
if self.left: self.left.insert(othernode)
else: self.left = othernode
else:
if self.right: self.right.insert(othernode)
else: self.right = othernode
def inorderwalk(self):
"Yield this Node and all under it in increasing-payload order."
if self.left:
for x in self.left.inorderwalk(): yield x
yield self
if self.right:
for x in self.right.inorderwalk(): yield x
def sillywalk(self):
"Tiny, silly subset of `inorderwalk` functionality as requested."
if self.left:
self.left.sillywalk()
print(self.payload)
if self.right:
self.right.sillywalk()
etc, etc -. Im Grunde wie in einer anderen Sprache, die Verweise eher als Zeiger (wie Java, C #, usw.) verwendet
Bearbeiten :
Natürlich ist die Existenz von sillywalk
albern in die Tat, weil genau die gleiche Funktionalität eine einzelsträngige Liner externe Snippet auf der Oberseite der walk
Methode ist:
for x in tree.walk(): print(x.payload)
und mit walk
können Sie fast jede andere Funktionalität auf dem Knoten-in-Ordnung-Stream erhalten, während bei sillywalk
, können Sie einfach über diddly-Squat erhalten. Aber, hey, sagt der OP yield
ist „einschüchternd“ (Ich frage mich, wie viele von Python 2.6 Die anderen 30 Schlüsselwörter verdienen so erschrecken Worte in dem Urteil des OP -?)! So hoffe ich, print
ist nicht
Das ist alles völlig über die eigentliche Frage, auf darstellen BSTs: , die Frage ganz im __init__
beantwortet wird - ein payload
Attribut des Knotens Nutzlast zu halten, left
und right
Attribut zu halten, entweder None
(das heißt, dieser Knoten keine Abkömmlinge auf der Seite), oder eine Node
(der obere Teil des Zweiges von Nachkommen auf der entsprechenden Seite). Selbstverständlich ist die BST-Einschränkung, dass jeder linker Nachkomme von jedem Knoten (falls vorhanden) weniger eine Nutzlast hat oder gleich ist als die der betreffende Knoten, jedes Recht eines (wieder, falls vorhanden) eine größere Nutzlast aufweist - I hinzugefügt insert
nur um zu zeigen, wie trivial es ist, dass die Einschränkung, walk
(und jetzt sillywalk
) zu halten zu zeigen, wie trivial es ist, alle Knoten in aufsteigender Reihenfolge von Nutzlasten zu erhalten. Auch hier ist die allgemeine Idee auf den Weg gerade identisch würden Sie darstellen ein BST in jeder Sprache, die Referenzen verwendet anstatt Zeiger, wie zum Beispiel C # und Java.