SDSU CS 635 Advanced Object-Oriented Design & Programming
Spring Semester, 2001
Assignment 1
    Assignment Index        
© 2001, All Rights Reserved, SDSU & Roger Whitney
San Diego State University -- This page last updated 23-Feb-01
Due March 20


In this assignment you will implement a few patterns that use a binary search trees. The uses of the patterns may not be optimal. The goal is to get some experience implementing a pattern, not to show the best use of the pattern.

You can use C++, Java or Smalltalk for this assignment. The intent of this assignment is for you to implement some of the patterns, not to find code or libraries to already do it for you.

1. Implement a binary search tree. The binary search tree is to be implemented using links, not with the nodes stored in an array. Each node in the tree contains a key and a value. The keys will be integers. The values will be strings. You should be able to add nodes to the tree. The tree does not have to be balanced.

2. Implement two iterators on the tree that iterate over the values in the tree. The iterators can be either active or passive. The first iterator is to traverse the tree in preorder. A preorder traversal first visits the root of the tree, then the left subtree in preorder, then the right subtree in preorder. The second iterator is to use an inorder traversal. An inorder traversal first visits the left subtree, then the root then the right subtree. Use the iterators to print out the values in the tree. Your iterators should not be hard coded to print out the values.

3. Implement a visitor that traverses the tree in preorder. At each node it visits the visitor reverses the string value in each node and prepends the visit ordered of the node. That is "1" is prepended to the value in the first node visited, "2" is prepended to the value in the second node visited, etc. The visitor can not use the iterator from 2 to traverse the tree.

4. Modify the visitor in 3 to use the strategy pattern to vary the order it traverses the tree. Provide inorder and preorder traversals.

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