Pythonのバイナリ検索ツリーを表します

Question

Pythonでバイナリ検索ツリーを表現するにはどうすればよいですか？

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

など - 基本的には、ポインター（Java、C＃など）ではなく参照を使用する他の言語のように。

編集:

もちろん、そのまさに存在 sillywalk まったく同じ機能は、の上にシングライナーの外部スニペットであるため、確かに愚かです。 walk 方法：

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

と walk ノードインオーダーストリームでほぼすべての機能を取得できますが、 sillywalk, 、ほぼ一四半期を取得できます。しかし、ちょっと、OPは言います yield 「威圧的」ですか（Python 2.6の他の30のキーワードの何人がOPの判断にそのような恐ろしい言葉に値するのだろうか？ - ） print そうではありません！

これはすべて、実際の質問を完全に超えています。 表現 BSTS： それ 質問は完全に答えられます __init__ - a payload ノードのペイロードを保持するための属性、 left と right どちらかを保持する属性 None （つまり、このノードにはその側に子孫がいません）または Node （適切な側面の子孫のサブツリーの上部）。もちろん、BSTの制約は、各ノード（もしあれば）のすべての左の子孫が、問題のノードのペイロードよりも少ないか等しいペイロードを持っていることです。 insert その制約を維持することがどれほど些細なことであるかを示すために、 walk （そして今 sillywalk）ペイロードの順序を増やすことですべてのノードを取得することがどれほど些細なことであるかを示す。繰り返しますが、一般的なアイデアはあなたがする方法と同じです 代表する たとえば、C＃やJavaなど、ポインターではなく参照を使用するあらゆる言語のBST。