stellen binäre Suchbäume in Python

Question

Wie kann ich binäre Suchbäume in Python darstellen?

Answer 1

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.