Cosc 2P03 Fall 2011
Assignment#2
(Due date for assignment, Tentative --> Tuesday Oct. 18th
noon., Late date Friday Oct. 21st, noon)
For this assignment you will be exploring a variety of traversals.
In most cases the code has been given in lecture and via the Dave's
Notes resource. You will be building 1 tree only, all operations on
that tree must leave the tree in an un-altered state.
- From the data given, (which contains Strings), build a BST
which is threaded for SOT. The BST will only store unique words,
thus if you parse a second instance of any string, this instance
will be ignored. You will still need to do the comparison during
the insert to verify that case. In the end the BST will only
contain 1 instance of any string.
- The data to use is the very first paragraph of this
assignment, "For this assignment ......". Copy that paragraph
into a text file and use StringTokenizer to break it apart.
Ignore periods and commas.
- Do not edit out duplicates, the insert method of the BST
will do that. In fact do not preprocess the input in any way
via editing. The code you write should do that.
- Give the output of this tree using the standard recursive
PreOrder traversal. Note: you will need to take into account
that there are threads instead of null pointers off of the
leaves.
- Give the PostOrder output using a recursive traversal
- Give the SOT (inorder) output using a recursive traversal
- Give the SOT output using an iterative traversal using the
threads. See the notes.
- Implement the iterative SOT traversal using stacks. See code
in Dave's Notes. I.e. implement the classes as appropriate, you
will need to implement the advance method as appropriate.
- To ensure you have not damaged your tree, run the recursive
SOT once more. Hopefully, it will give the same output as
before.
- Implement the Link Inversion algorithm as described in class,
giving the inorder output (SOT).
- Run the recursive SOT again as a check.
The general rule is that you will only have 1 BST. All traversals
and operations will be done on that one tree. Note, the general
rule, "thou shalt not harm thy data". I.e. be sure your tree is in
good health after every operation.
Some suggestions:
Consider using a multi-class project. Each major traversal, Stack,
Link Inversion can be put into their own class, passing the BST via
the constructor.
Submission Requirements:
- Cover Sheet completely filled out, available
from: "http://www.cosc.brocku.ca/coverpage"
Note: your assignment will not be marked unless one is submitted
with the assignment on the assignment due date.
- Commented and properly documented source code
listing.
- Listing of any input you used to test your program.
- Listing of your output. Be sure to adequately show that the
input, operations and output show the marker that your program
is working. Don't be afraid to tell the marking if something is
not working correctly.
- Source code is to be Java.
- Disk, CD containing source, input, output and executables.
- Electronic submission, run the script "submit2p03" from
sandcastle.
- Statement on coversheet with following information.
- Platform, e.g. Mac PP6100, PC, Commodor 64, my Java enabled
wrist watch.
- Compiler Version, e.g. Java 1.5, Java 1.6 e.g.
Good Luck