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__.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.
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) :
""" t=BinaryTree('C apricorn') t.addNode('Aqua rius') t.addNode('Pice s') t.addNode('Canc er') t.printTree()
Capricorn
Aquarius
Cancer
Pices
"""
print self.key
if self.left:
self.left.print Tree()
if self.right:
self.right.prin tTree()
def printSortedTree (self):
""" t=BinaryTree('C apricorn') t.addNode('Aqua rius') t.addNode('Pice s') t.addNode('Canc er') t.printSortedTr ee()
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):
""" t=BinaryTree('C apricorn') t.addNode('Aqua rius') t.addNode('Pice s') t.addNode('Canc er') t.find('Caprico rn')
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() 2 1792 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__.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.
(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('C apricorn') >>> t.addNode('Aqua rius') >>> t.addNode('Pice s') >>> t.addNode('Canc er') >>> t.find('Caprico rn') 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.fin d(key)
return self.right.find (key) else: return -1
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) This thread has been closed and replies have been disabled. Please start a new discussion. Similar topics |
by: Max |
last post by:
Hi guys, did some searching on the topic, but can't find much more then
just basic info on binary trees. I need to write a binary tree
implementation so that it is always complete. In other words operations
such as add and delete will not cause the completeness to break.
Re-adding all of the elements to a brand new tree and wiping out the old
one is not an option, so any sorting that I do must be in place.
Does anyone know of a good...
|
by: tsunami |
last post by:
hi all;
I have an array and want to insert all the elements from this array to
a binary search tree.That array is an object of the class of a
stringtype which includes overloaded "< > = ==" functions and every
other thing it needs.
void InsertElementFromArray(StringType Array,int first element,int
last element);
|
by: Tarique Jawed |
last post by:
Alright I needed some help regarding a removal of a binary search
tree. Yes its for a class, and yes I have tried working on it on my
own, so no patronizing please. I have most of the code working, even
the removal, I just don't know how to keep track of the parent, so
that I can set its child to the child of the node to be removed.
IE - if I had
C
/ \
B D
|
by: Foodbank |
last post by:
Hi all,
I'm trying to do a binary search and collect some stats from a text
file in order to compare the processing times of this program (binary
searching) versus an old program using linked lists. I'm totally new
to binary searches by the way. Can anyone help me with the commented
sections below? Much of the code such as functions and printfs has
already been completed. Any help is greatly appreciated.
Thanks,
|
by: Andrew |
last post by:
Hi, im trying to create a small function which can create a binary tree
from the entries in a text file and after that we can perform all the
usual operations like search, insert and delete etc. Now i have entries
something like this
IPaddress Phone No
192.168.2.1 2223447689
192.168.2.2 3334449898
192.168.2.3 5667869089
| |
by: free2cric |
last post by:
Hi,
I have a single link list which is sorted.
structure of which is like
typedef struct mylist
{
int num;
struct mylist *next;
|
by: JDT |
last post by:
Hi,
The last statement at the end of this post is to delete a set member
7.7. I set a break point inside ltstr::operator(). I found out that
STL binary-seach the set twice. How come? I have another problem that
a member in a set cannot be deleted. I think I may be able to solve
that problem if I can figure out the problem posted here. Thanks for
your help.
The sequence of (f1, f2) STL goes through is (7.7, 4.4), (7.7, 6.6),
|
by: fdmfdmfdm |
last post by:
This might not be the best place to post this topic, but I assume most
of the experts in C shall know this.
This is an interview question. My answer is:
hash table gives you O(1) searching but according to your hash
function you might take more memory than binary tree. On the contrary,
binary tree gives you O(logN) searching but less memory.
Am I right?
|
by: Vinodh |
last post by:
Started reading about Binary Trees and got the following questions in
mind. Please help.
Definition of a Binary Tree from "Data Structures using C and C++ by
Tanenbaum" goes like this,
"A binary tree is a finite set of elements that is either empty or is
partitioned into three disjoint subsets. The first subset contains a
single element called the 'Root' of the tree. The other two subsets
are themselves binary trees, called the 'Left'...
|
by: marktang |
last post by:
ONU (Optical Network Unit) is one of the key components for providing high-speed Internet services. Its primary function is to act as an endpoint device located at the user's premises. However, people are often confused as to whether an ONU can Work As a Router. In this blog post, we’ll explore What is ONU, What Is Router, ONU & Router’s main usage, and What is the difference between ONU and Router. Let’s take a closer look !
Part I. Meaning of...
|
by: Hystou |
last post by:
Most computers default to English, but sometimes we require a different language, especially when relocating. Forgot to request a specific language before your computer shipped? No problem! You can effortlessly switch the default language on Windows 10 without reinstalling. I'll walk you through it.
First, let's disable language synchronization. With a Microsoft account, language settings sync across devices. To prevent any complications,...
| |
by: jinu1996 |
last post by:
In today's digital age, having a compelling online presence is paramount for businesses aiming to thrive in a competitive landscape. At the heart of this digital strategy lies an intricately woven tapestry of website design and digital marketing. It's not merely about having a website; it's about crafting an immersive digital experience that captivates audiences and drives business growth.
The Art of Business Website Design
Your website is...
|
by: Hystou |
last post by:
Overview:
Windows 11 and 10 have less user interface control over operating system update behaviour than previous versions of Windows. In Windows 11 and 10, there is no way to turn off the Windows Update option using the Control Panel or Settings app; it automatically checks for updates and installs any it finds, whether you like it or not. For most users, this new feature is actually very convenient. If you want to control the update process,...
|
by: conductexam |
last post by:
I have .net C# application in which I am extracting data from word file and save it in database particularly. To store word all data as it is I am converting the whole word file firstly in HTML and then checking html paragraph one by one.
At the time of converting from word file to html my equations which are in the word document file was convert into image.
Globals.ThisAddIn.Application.ActiveDocument.Select();...
|
by: TSSRALBI |
last post by:
Hello
I'm a network technician in training and I need your help.
I am currently learning how to create and manage the different types of VPNs and I have a question about LAN-to-LAN VPNs.
The last exercise I practiced was to create a LAN-to-LAN VPN between two Pfsense firewalls, by using IPSEC protocols.
I succeeded, with both firewalls in the same network. But I'm wondering if it's possible to do the same thing, with 2 Pfsense firewalls...
|
by: adsilva |
last post by:
A Windows Forms form does not have the event Unload, like VB6. What one acts like?
|
by: muto222 |
last post by:
How can i add a mobile payment intergratation into php mysql website.
| |
by: bsmnconsultancy |
last post by:
In today's digital era, a well-designed website is crucial for businesses looking to succeed. Whether you're a small business owner or a large corporation in Toronto, having a strong online presence can significantly impact your brand's success. BSMN Consultancy, a leader in Website Development in Toronto offers valuable insights into creating effective websites that not only look great but also perform exceptionally well. In this comprehensive...
| |