表示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,您可以获得关于diddly-squat的信息.但是,嘿,OP说yield是"令人生畏"(我想知道有多少Python 2.6的其他30个关键词在OP的判断中应该得到这样的恐吓？ - )所以我希望print不是!

这完全超出了实际问题,代表 BST:这个问题完全回答__init__- 一个payload保存节点有效载荷的属性,left以及right属性保持None(意味着,这个节点在那一侧没有后代)或一个Node(在适当的一侧的后代的子树的顶部).当然,BST约束是每个节点的每个左后代(如果有的话)的有效载荷小于或等于有问题的节点的有效载荷,每个右边的(再次,如果有的话)有更大的有效载荷 - 我添加insert了显示维持这种约束是多么微不足道walk(现在sillywalk)显示使所有节点按有效载荷递增顺序是多么微不足道.同样,一般的想法与您在任何使用引用而不是指针的语言中表示 BST 的方式完全相同,例如C#和Java.