repräsentieren binäre Suchbäume in Python

Question

Wie stelle ich binäre Suchbäume in Python dar?

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 ist in der Tat dumm, 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-Order-Stream erhalten, während mit sillywalk, können Sie nur über Diddly-Kniebeugen erhalten. Aber, hey, das OP sagt yield ist "einschüchternd" (Ich frage mich, wie viele von Pythons 2.6 anderen 30 Keywords verdienen solche Angst Worte in der OP-Urteil?) Ich hoffe also print ist nicht!

Das alles komplett über die eigentliche Frage ist, auf darstellt BSTs: dass Frage ganz im __init__ beantwortet wird - ein payload Attribut des Knotens Nutzlast zu halten, left und right Attribut zu halten entweder None (was bedeutet, , dieser Knoten hat keine Nachkommen auf dieser Seite) oder Node (der obere Teil des Unterbaums der Nachkommen auf der entsprechenden Seite). Natürlich besteht die BST-Einschränkung darin, dass jeder linke Nachkomme jedes Knotens (falls vorhanden) eine Nutzlast hat, die kleiner oder gleich ist als die des fraglichen Knotens, wobei jede rechte (wenn wieder irgendeine) eine größere Nutzlast hat - ich fügte insert hinzu nur um zu zeigen, wie trivial es ist, diese Beschränkung aufrechtzuerhalten, walk (und jetzt sillywalk), um zu zeigen, wie trivial es ist, alle Knoten in ansteigender Reihenfolge der Nutzdaten zu erhalten. Wiederum ist die allgemeine Idee identisch mit der Art und Weise, wie Sie eine BST in einer beliebigen Sprache darstellen, die Referenzen statt Zeiger, wie zum Beispiel C# und Java verwendet.