代表蟒蛇二叉搜索树

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-蹲下。但是，哎，OP说yield是“恐吓”（我不知道有多少的Python 2.6的其他30个关键字应该在OP的判断，这种恐慌的话 - ？）！所以我希望print不是

这是一切完全超出了实际问题，在代表 BSTS：是的问题完全回答的__init__ - 一个payload属性保留节点的有效载荷，left和right属性保持任一None（意思是，该节点具有在该侧没有后代）或Node（后代的子树的上相应侧上的顶部）。当然，BST约束是每个节点（如果有的话）的每个左边的后代具有有效载荷小于或大于所讨论的节点，每一个右边的等于（再次，如果有的话）具有更大的有效载荷 - I加入insert只是为了显示它是多么微不足道保持这种约束，walk（现在sillywalk），以显示它是多么微不足道让所有节点增加有效载荷的顺序。再次，一般的想法就是等同于你的代表的方式的任何语言BST它使用的引用，而不是指针一样，例如，C＃和Java。