代表python中的二叉搜索树 [英] represent binary search trees in python

问题描述

如何在python中表示二叉搜索树？

how do i represent binary search trees in 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＃等）。

etc, etc -- basically like in any other language which uses references rather than pointers (such as Java, C#, etc).

修改：

当然， sillywalk 的存在确实是愚蠢的，因为完全相同的功能是在 walk 之上的单线程外部片段方法：

Of course, the very existence of sillywalk is silly indeed, because exactly the same functionality is a singe-liner external snippet on top of the walk method:

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

和 walk ，您可以获得节点上任何其他功能 - 订单流，而使用 sillywalk ，您可以获得关于diddly-squat。但是，嘿，OP说 yield 是吓倒（我想知道Python 2.6的其他30个关键字中有多少个应该在OP的判断中有这样的吓人的话？）我希望打印不是！

and with walk you can obtain just about any other functionality on the nodes-in-order stream, while, with sillywalk, you can obtain just about diddly-squat. But, hey, the OP says yield is "intimidating" (I wonder how many of Python 2.6's other 30 keywords deserve such scare words in the OP's judgment?-) so I'm hoping print isn't!

这完全超出了实际的问题，在代表 BSTs： 问题在 __ init __ - 一个有效载荷属性保存节点的有效负载， left 和 right 属性可以保存无（意思是，该节点在该方没有后代）或节点（在相应的一侧的后代子树的顶部）。当然，BST约束是每个节点的每个左后裔（如果有的话）的负载小于或等于所讨论的节点的负载，每个右边的（再次，如果有的话）有一个更大的有效载荷 - 我添加了 insert 只是为了显示维护约束的微不足道， walk （现在 sillywalk ）来显示如何平凡地获得所有节点的有效载荷的增加顺序。再次，一般想法与您以任何使用引用而不是指针（例如C＃和Java）的任何语言代表BST的方式完全相同。

This is all completely beyond the actual question, on representing BSTs: that question is entirely answered in the __init__ -- a payload attribute to hold the node's payload, left and right attribute to hold either None (meaning, this node has no descendants on that side) or a Node (the top of the sub-tree of descendants on the appropriate side). Of course, the BST constraint is that every left descendant of each node (if any) has a payload less or equal than that of the node in question, every right one (again, if any) has a greater payload -- I added insert just to show how trivial it is to maintain that constraint, walk (and now sillywalk) to show how trivial it is to get all nodes in increasing order of payloads. Again, the general idea is just identical to the way you'd represent a BST in any language which uses references rather than pointers, like, for example, C# and Java.

这篇关于代表python中的二叉搜索树的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！