binary search trees using classes

[Ype Kingma]

Christy,

christy johnson wrote:
> 
> Hi,
> I was wondering if anyone had a binary search tree
> module I could use? I need to write a program that
> counts the number of occurrences of each word in a
> file, and outputs the word and corresponding counts
> alphabetically. For example, if input is
> 
> Have a nice day. Have a nice day.
> Have a nice day.
> Have a nice day.
> 
> the output is
> 
> a 4
> day 4
> have 4
> nice 4
> 
> The code has to be modular based on classes. I'm
> thinking of making a
> tree node that looks like this
> 
> bintree[ [key, data], left, right] ,
> 
> where I can traverse the tree by simply incrementing
> the current root
> to the appropriate child.
> 
> temp = bintree.root
> temp = temp[1]        #move to the left child.
> temp = temp[2]        #move to the right child.
> 
> but I don't know how to implement it correctly using
> classes. (i.e
> using def __init__(self), etc)
> 

You might consider an alternative:

Counting words is better done using a dictionary.
This will use hashing for lookups, which is normally faster than 
using a binary tree.
Afterwards you can sort the keys of the dictionary and provide
output from that.
Another advantage is that you'll only need standard python
data structures:

counts = {}

# put this in a loop providing the line in lower case and without punctuation:
for word in line.split():
    if counts.has_key(word):
        counts[word] += 1
    else:
        counts[word] = 1

words = counts.keys()
words.sort()
for word in words:
    print word, counts[word]


Regards,
Ype

-- 
email at xs4all.nl