представление бинарных деревьев поиска в python

Как я представляю бинарные деревья поиска в python?

1 5
python binary-tree data-structures binary-search-tree

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

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

Edit:

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

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

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

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

11