By using this site, you agree to our updated Privacy Policy and our Terms of Use. Manage your Cookies Settings.
448,966 Members | 1,520 Online
Bytes IT Community
+ Ask a Question
Need help? Post your question and get tips & solutions from a community of 448,966 IT Pros & Developers. It's quick & easy.

Binary tree problem (searching)

P: n/a
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 isso, 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()


Apr 4 '06 #1
Share this Question
Share on Google+
2 Replies


P: n/a
py***@speakeasy.net a écrit :
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.

(snip)

You forgot to return the result of calls to self.left.find() and
self.right.find()

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)
return self.left.find(key) else:
return -1
elif key > self.key:
if self.right: #self.right.find(key)
return self.right.find(key) else:
return -1

Apr 4 '06 #2

P: n/a
This took a moment
I spent a lot of time stupidly thinking about right/left sorting, is it
looping? no that's not it...doh Then the light

then realized this

if self.key == key:
return 1
elif key < self.key:
if self.left:
self.left.find(key)
else:
return -1
you need to RETURN on the child call -

if self.left:
self.left.find(key)

becomes
if self.left:
return self.left.find(key)

Apr 4 '06 #3

This discussion thread is closed

Replies have been disabled for this discussion.