views:

120

answers:

1

how do i represent binary search trees in python?

+7  A: 
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.

Alex Martelli
You should space this out a bit, it's quite hard to read all together like that.
detly
@Alex Yield !!!! :| i am sure there's a less intimidating solution than this for a newbie like me.
Bunny Rabbit
@Bunny, Python has very few keywords indeed (31, as of 2.6) -- which ones out of this tiny number do you find "intimidating"? Anyway, I'm going to add a completely silly and pointless walk-like method (working essentially just like `walk` but in an insanely restricted way) if that makes you happy (and add whitespace to make @detly happy too) -- editing the A accordingly.
Alex Martelli
@Bunny - don't be thinking `yield` is hard just because it's not common amongst other languages. Write maybe a couple of DIY examples and I'm sure it'll become much clearer.
detly
+1 for a very pythonic method name (sillywalk)
jellybean
@Alex: Any particular reason for using `0` instead of `None` in the __init__()?
John Machin
@John, none in particular -- any "falsish" value (0, None, False) would do just as well (as I'm later testing with simple `if self.left:` etc).
Alex Martelli