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

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 вы можете получить почти неуклюже -присед. Но, эй, ОП говорит, что yield «пугает» (интересно, сколько Python 2.Остальные 30 ключевых слов 6 заслуживают таких пугающих слов по мнению ОП? -) так что я надеюсь print нет!

Все это полностью выходит за рамки фактического вопроса на , представляющем BST: на этот вопрос полностью дан ответ в __ init __ - полезной нагрузке для хранения полезной нагрузки узла, левый и правый атрибут для хранения либо None (это означает, что этот узел не имеет потомков на этой стороне) или Узел (вершина поддерева потомков на соответствующей стороне). Конечно, ограничение BST заключается в том, что каждый левый потомок каждого узла (если есть) имеет полезную нагрузку меньше или равную, чем у рассматриваемого узла, каждый правый (опять же, если есть) имеет большую полезную нагрузку - я добавил вставьте просто для того, чтобы показать, насколько тривиально поддерживать это ограничение, пройдите (а теперь глупо ), чтобы показать, насколько тривиально расположить все узлы в порядке возрастания полезные нагрузки. Опять же, общая идея полностью идентична тому, как вы представляете BST на любом языке, который использует ссылки, а не указатели, как, например, C # и Java.