我如何在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,则可以获得大约diddly-quat。但是,嘿,OP说yield是“令人生畏的”(我想知道在OP的判断中,有多少Python 2.6的其他30个关键字值得这些吓人的话??)所以我希望print不是!

这完全超出了实际问题,在代表 BST的问题上:该问题完全在__init__中得到了回答– payload属性用于保存节点的有效负载,leftright属性来保存任一None(这意味着该节点没有后代)在那一侧)或Node(在相应一侧的后代子树的顶部)。当然,BST约束是每个节点(如果有的话)的每个左后代的有效载荷都小于或等于所讨论节点的有效载荷,每个右边的后代(如果有的话)具有更大的有效载荷-我添加了insert只是为了说明维护该约束是多么的琐碎,walk(现在是sillywalk)说明了使所有节点按有效负载的递增顺序变得多么琐碎。同样,总体思路与使用任何一种使用引用而不是指针的语言表示BST的方式相同,例如C#和Java。

关于python - 代表python中的二进制搜索树,我们在Stack Overflow上找到一个类似的问题:https://stackoverflow.com/questions/3058665/

10-11 22:37
查看更多