SDSU CS 535 Object-Oriented Programming & Design
Fall Semester, 2001
Assignment 4
    Assignment Index        
© 2001, All Rights Reserved, SDSU & Roger Whitney
San Diego State University -- This page last updated 10-Oct-01
Assignment 4

Due October 25

1. Implement a method called 'positives". Add this method to a class in the collection hierarchy so both the Array class and the OrderedCollection class inherit the method. The method is to be sent to collection objects that contain numbers. It returns the number of elements in the collection that are greater than zero.

2. Implement a binary search tree. The each node of the tree is to contain a key and a value. The nodes are ordered in the tree by the keys. So all the nodes in the left subtree of the root node have keys less than the root node. Assume that the keys in the tree are all of the same type. For example all the keys in one tree might be integers and in another tree all the keys might be strings. A binary search tree must have the following methods:

size
Returns the number of nodes in the tree
at: aKey
Returns the value in the node that has the given key
at: aKey put: aValue
If the tree has a node with the given key, replace the node's value with aValue. This means a key can not be repeated in a tree. If no node has the given key then add a new node in the binary search tree with the given key and value. There is no need to balance the tree.

do: aBlock
aBlock is to have one parameter. aBlock is evaluated for each node in the tree with the block's parameter the nodes value.
detect: aBlock
Returns the first value in the tree found to make aBlock evaluate to true. The order of searching the tree is an implementation detail.

Other methods can be added if needed or desired.

Some textbooks show how to implement a binary search tree using an array. Do no use such implementations in this assignment. Implement the tree with nodes and links.

3. Provide unit tests for problem 1 & 2.

You might find this assignment a bit harder than the previous assignments. So you might want to start on it early.

Copyright ©, All rights reserved.
2000 SDSU & Roger Whitney, 5500 Campanile Drive, San Diego, CA 92182-7700 USA.
OpenContent license defines the copyright on this document.
    visitors since 10-Oct-01