Binary tree problem (searching)

[Bruno Desthuilliers]

pyguy at 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
>