Hi all,
I am running into a conceptual glitch in implementing a simple binary tree
class. My insertion and printing (sorting) seems to be ok, but when I search
the tree, my find method isn't doing what I thought it should.
Here is the output of running my tests:
>python -i trees.py
**********************************************************************
File "trees.py", line 70, in __main__.BinaryTree.find
Failed example:
t.find('Leo')
Expected:
-1
Got nothing
**********************************************************************
File "trees.py", line 72, in __main__.BinaryTree.find
Failed example:
t.find('Cancer')
Expected:
1
Got nothing
**********************************************************************
1 items had failures:
2 of 7 in __main__.BinaryTree.find
***Test Failed*** 2 failures.
>>>
So it appears my find method is failing to return -1 for a missing key and 1
for any key below the root. If anyone could clue me in on why this is so, I'd
appreciate it.
Here is the code (trees.py):
class BinaryTree:
"""Binary Tree"""
def __init__(self, key, left=None, right=None):
self.key = key
self.left = left
self.right = right
def __str__(self):
return str(self.key)
def addNode(self,key):
if key < self.key:
if self.left:
self.left.addNode(key)
else:
self.left = BinaryTree(key)
elif key > self.key:
if self.right:
self.right.addNode(key)
else:
self.right = BinaryTree(key)
def printTree(self):
"""
>>> t=BinaryTree('Capricorn')
>>> t.addNode('Aquarius')
>>> t.addNode('Pices')
>>> t.addNode('Cancer')
>>> t.printTree()
Capricorn
Aquarius
Cancer
Pices
"""
print self.key
if self.left:
self.left.printTree()
if self.right:
self.right.printTree()
def printSortedTree(self):
"""
>>> t=BinaryTree('Capricorn')
>>> t.addNode('Aquarius')
>>> t.addNode('Pices')
>>> t.addNode('Cancer')
>>> t.printSortedTree()
Aquarius
Cancer
Capricorn
Pices
"""
if self.left:
self.left.printSortedTree()
print self.key
if self.right:
self.right.printSortedTree()
def find(self, key, child=None):
"""
>>> t=BinaryTree('Capricorn')
>>> t.addNode('Aquarius')
>>> t.addNode('Pices')
>>> t.addNode('Cancer')
>>> t.find('Capricorn')
1
>>> t.find('Leo')
-1
>>> t.find('Cancer')
1
"""
if self.key == key:
return 1
elif key < self.key:
if self.left:
self.left.find(key)
else:
return -1
elif key > self.key:
if self.right:
self.right.find(key)
else:
return -1
def _test():
import doctest
doctest.testmod()
if __name__ == '__main__':
_test()
--
http://mail.python.org/mailman/listinfo/python-list
