python - 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取得できます。しかし、ねえ、OPyieldは「威圧的」だと言っています（Python 2.6の他の30個のキーワードのうち、OPの判断でそのような恐ろしい言葉に値するものはいくつあるのだろうか-）ので、そうでprintはないことを願っています!

これはすべて、BSTを表す実際の質問を完全に超えています。その質問は、ノードのペイロードを保持する属性、__init__および保持する属性(つまり、このノードにはその側に子孫がないことを意味します) または(適切な側の子孫のサブツリーの上部)。もちろん、BST の制約は、各ノード (存在する場合) のすべての左の子孫が問題のノードのペイロード以下のペイロードを持ち、すべての右の子孫 (存在する場合) がより大きなペイロードを持つことです-私はちょうど追加しましたその制約を維持することがいかに簡単かを示すために(そして今ではpayloadleftrightNoneNodeinsertwalksillywalk) ペイロードの昇順ですべてのノードを取得することがいかに簡単かを示します。繰り返しますが、一般的な考え方は、C# や Java など、ポインターではなく参照を使用する言語で BST を表す方法とまったく同じです。