represent binary search trees in python

问题:

how do i represent binary search trees in python?

回答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()

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

Edit:

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)

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!

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.