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()
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.