Binary tree problem (searching)

[pyguy@speakeasy.net]

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:
[color=blue]
>python -i trees.py[/color]
*************** *************** *************** *************** **********
File "trees.py", line 70, in __main__.Binary Tree.find
Failed example:
t.find('Leo')
Expected:
-1
Got nothing
*************** *************** *************** *************** **********
File "trees.py", line 72, in __main__.Binary Tree.find
Failed example:
t.find('Cancer' )
Expected:
1
Got nothing
*************** *************** *************** *************** **********
1 items had failures:
2 of 7 in __main__.Binary Tree.find
***Test Failed*** 2 failures.[color=blue][color=green][color=darkred]
>>>[/color][/color][/color]


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,ke y):
if key < self.key:
if self.left:
self.left.addNo de(key)
else:
self.left = BinaryTree(key)
elif key > self.key:
if self.right:
self.right.addN ode(key)
else:
self.right = BinaryTree(key)

def printTree(self) :
"""[color=blue][color=green][color=darkred]
>>> t=BinaryTree('C apricorn')
>>> t.addNode('Aqua rius')
>>> t.addNode('Pice s')
>>> t.addNode('Canc er')
>>> t.printTree()[/color][/color][/color]
Capricorn
Aquarius
Cancer
Pices
"""
print self.key
if self.left:
self.left.print Tree()
if self.right:
self.right.prin tTree()

def printSortedTree (self):
"""[color=blue][color=green][color=darkred]
>>> t=BinaryTree('C apricorn')
>>> t.addNode('Aqua rius')
>>> t.addNode('Pice s')
>>> t.addNode('Canc er')
>>> t.printSortedTr ee()[/color][/color][/color]
Aquarius
Cancer
Capricorn
Pices
"""
if self.left:
self.left.print SortedTree()
print self.key
if self.right:
self.right.prin tSortedTree()




def find(self, key, child=None):
"""[color=blue][color=green][color=darkred]
>>> t=BinaryTree('C apricorn')
>>> t.addNode('Aqua rius')
>>> t.addNode('Pice s')
>>> t.addNode('Canc er')
>>> t.find('Caprico rn')[/color][/color][/color]
1[color=blue][color=green][color=darkred]
>>> t.find('Leo')[/color][/color][/color]
-1[color=blue][color=green][color=darkred]
>>> t.find('Cancer' )[/color][/color][/color]
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()

[Bruno Desthuilliers]

Re: Binary tree problem (searching)

pyguy@speakeasy .net a écrit :[color=blue]
> 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:
>
>[color=green]
>>python -i trees.py[/color]
>
> *************** *************** *************** *************** **********
> File "trees.py", line 70, in __main__.Binary Tree.find
> Failed example:
> t.find('Leo')
> Expected:
> -1
> Got nothing
> *************** *************** *************** *************** **********
> File "trees.py", line 72, in __main__.Binary Tree.find
> Failed example:
> t.find('Cancer' )
> Expected:
> 1
> Got nothing
> *************** *************** *************** *************** **********
> 1 items had failures:
> 2 of 7 in __main__.Binary Tree.find
> ***Test Failed*** 2 failures.
>[color=green][color=darkred]
>>>>[/color][/color][/color]

(snip)

You forgot to return the result of calls to self.left.find( ) and
self.right.find ()
[color=blue]
>
> def find(self, key, child=None):
> """[color=green][color=darkred]
> >>> t=BinaryTree('C apricorn')
> >>> t.addNode('Aqua rius')
> >>> t.addNode('Pice s')
> >>> t.addNode('Canc er')
> >>> t.find('Caprico rn')[/color][/color]
> 1[color=green][color=darkred]
> >>> t.find('Leo')[/color][/color]
> -1[color=green][color=darkred]
> >>> t.find('Cancer' )[/color][/color]
> 1
> """
> if self.key == key:
> return 1
> elif key < self.key:
> if self.left:[/color]
#self.left.find (key)
return self.left.find( key)[color=blue]
> else:
> return -1
> elif key > self.key:
> if self.right:[/color]
#self.right.fin d(key)
return self.right.find (key)[color=blue]
> else:
> return -1
>[/color]

[akameswaran@gmail.com]

Re: Binary tree problem (searching)

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)