Home Original page

Pls Help! Need binary search tree module

Greg Jorgensen gregj at pobox.com
Mon Feb 19 02:07:02 EST 2001 
On Sun, 18 Feb 2001 21:38:54 GMT, "Steve Mak" <stevemak at softhome.net>
wrote:

>I was wondering if anyone had a simple 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. And it is required that one of the data structure is a
>binary search tree.
>
> Eg: if the inputs is:
>
>"How are you. How are you. How are you."
>
>the output is:
>
>are 3
>how 3
>you 3

If you are working on an assignment and must use a binary search tree,
I refer you to Sedgewick's book "Algorithms." Translating
pointer-based trees to Python will challenge your Python skills. Hint:
a Python list can contain ANY kind of object reference, including
references to other lists. I implemented Sedgewick's algorithms in
Python (from his C versions) in about 30 minutes.

The typical Python way to do what you describe uses a dictionary with
the words as keys as a counter as the value. For example:

# insert/count words using dictionary
words = ['your', 'list', 'of', 'words']
wc = {}
for w in words:
    if wc.has_key(w):
        wc[w] += 1
    else:
        wc[w] = 1

# show counts by word in alpha order
words = wc.keys()
words.sort()
for w in words:
    print "%s: %d" % (w, wc[w])


Greg Jorgensen
Deschooling Society
Portland, Oregon USA
More information about the Python-list mailing list