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.