представляют двоичные деревья поиска в Python - PullRequest
Новая
       18

представляют двоичные деревья поиска в Python

6 голосов
/ 17 июня 2010

как мне представить двоичные деревья поиска в python?

1 Ответ

12 голосов
/ 17 июня 2010 
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()

и т. Д. И т. Д. - в основном, как и в любом другом языке, в котором используются ссылки, а не указатели (например, Java, C # и т. Д.).

Редактировать :

Конечно, само существование sillywalk действительно глупо, потому что точно такой же функциональностью является внешний фрагмент одиночной линии поверх метода walk: 

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

и с walk вы можете получить практически любую другую функциональность в потоке узлов в порядке, в то время как с sillywalk вы можете получить почти дидди-присед.Но, эй, OP говорит, что yield "пугающий" (интересно, сколько из других 30 ключевых слов Python 2.6 заслуживают таких страшных слов по мнению OP?), Поэтому я надеюсь, что print нет!

Это все, что выходит за рамки реального вопроса, на , представляющем BST: , на который вопрос полностью отвечает в атрибуте __init__ - payload для храненияполезные данные узла, атрибуты left и right для хранения либо None (имеется в виду, что у этого узла нет потомков на этой стороне), либо Node (вершина поддерева потомков на соответствующей стороне),Конечно, ограничение BST состоит в том, что каждый левый потомок каждого узла (если есть) имеет полезную нагрузку, меньшую или равную полезной нагрузке рассматриваемого узла, каждый правый (опять же, если таковой имеется) имеет большую полезную нагрузку - я добавил insert просто для того, чтобы показать, насколько тривиально поддерживать это ограничение, walk (а теперь sillywalk), чтобы показать, насколько тривиально получить все узлы в порядке возрастания полезных нагрузок.Опять же, общая идея идентична тому, как вы представляете BST на любом языке, который использует ссылки, а не указатели, как, например, C # и Java.

...