|
|
Comp202: Principles of Object-Oriented Programming II
Fall 2007 -- Lab
#8: TreeN and The Generalized Visitor
|
In this lab, you will get to write a few visitors for the
TreeN structure used in the Self-Balancing Tree algorithms.
Click here
to download the source code for TreeN:
- Write a visitor, called CountNodes, for TreeN, to count the number of
nodes in the host tree. Be sure to write your own JUnit test.
- Write a visitor, called CountElements, for TreeN, to count the number of
data elements in the host tree. Be sure to write your own JUnit
test.
- Write a visitor, called CountLeaves, for TreeN, to count the number of
leaf nodes in the host tree. Be sure to write your own JUnit
test.
- Write a visitor, called GetHeight, for TreeN to compute the height of host
tree. The height of an empty tree is 0. The height of a
one-node tree is 1. What is the height of a tree with more than one
node? Be sure to write your own JUnit test.
- Write a visitor, called GetWidth, for a TreeN, to compute the width of the
host tree. The width of an empty tree is 0. The width of a
non-empty tree is the larger of the width of the parent node and the sum of
the widths of the children subtrees. Be sure to write your own JUnit
test..
- Write a visitor, called FuseTree, for a TreeN, that takes another TreeN as
input parameter and "fuses" it with the host tree in the following
manner.
- When the host is empty then the host simply becomes the input tree.
- When the input tree is empty then the host stays the same and the
input tree becomes the host.
- When both host and input are not empty, then the host root node and
the input root node get concatenated together, and the rightmost subtree
of the host fuses with the leftmost subtree of the input tree.
Be sure to write your own JUnit test.
Last Revised
Monday, 25-Jan-2010 16:14:03 CST
©2007 Stephen Wong and Dung Nguyen
