python'daki ikili arama ağaçlarını temsil eder

Question

Python'da ikili arama ağaçlarını nasıl gösteririm? Temelde (Java, C#, vb gibi) başvurular ziyade işaretçileri kullanan başka bir dilde böyle - vs, vs

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() 

.

Düzenleme:

for x in tree.walk(): print(x.payload) 

: tam olarak aynı işlevselliği walk yöntemin üstüne bir tüy yolma astar dış pasajı çünkü

Tabii

, sillywalk varlığının gerçekten saçma ve walk ile, sipariş düğümlerinde diğer tüm işlevler hakkında bilgi edinebilirsiniz, sillywalk ile hemen hemen diddly-squat edinebilirsiniz. Ancak, OP, yield'un "korkutucu" olduğunu söylüyor (Python 2.6'nın diğer 30 anahtar kelimesinin kaçının OP'nin kararında bu tür korkutucu kelimeleri hak ettiğini merak ediyorum?). Bu yüzden print'un ummuyor!

Bu

BSTS temsil üzerinde, tamamen gerçek sorunun ötesinde tüm şudur: soru tamamen __init__ cevaplanır o - düğümün yükünü tutmak için bir payload özniteliği left ve right nitelik ya None (anlam tutmak için bu düğümün soyundan gelenleri yoktur, ya da Node (alt taraftaki alt ağaçların üst kısmı uygun taraftadır). Tabii ki, BST kısıtlaması, her düğümün her sol soyundan (eğer varsa), söz konusu düğümün değerinden daha az veya eşit bir yüke sahip olması, her bir doğru (eğer varsa) daha büyük bir yüke sahip olmasıdır - insert ekledim sadece, tüm düğümleri artan yük yükleri sırasına almak için ne kadar önemsiz olduğunu göstermek için bu kısıtlamayı sürdürmenin ne kadar önemsiz olduğunu göstermek için, walk (ve şimdi sillywalk). Yine, genel fikir, 'un'u bir BST ile C# ve Java gibi işaretçiler yerine referanslar kullanan herhangi bir dilde temsil ettiğiyle aynıdır.