Lab 9: Trees

Linux/Emacs Tip(s) of the Day

1. who [linux] Lists other users logged onto your machine.
2. date [linux] Prints the date and time.
3. cal [linux] Prints calendar for given month and year, e.g. cal 10 2008
4. M-x calendar [emacs] Displays a calendar (C-x < or C-x > to scroll)
5. C-x 2 [emacs] Splits window horizontally
6. C-x 3 [emacs] Splits window vertically
7. C-x o (oh, not zero) [emacs] Switch between windows
8. C-x f [emacs] Find the file for your newly opened window
9. C-x 1 (one) [emacs] Revert to a single window

New Tree Methods

In this lab, you will complete the definitions of some methods that operate on binary trees. The /home/cs230/download/LabTrees directory contains the following files:

• Tree.java code file you are familiar with, and
• LabTreeOps.java file where you will add the definitions of the new methods. This file already contains abbreviations for the class methods in Tree.java so that you can invoke these methods without having to specify the Tree class name.

In your labTreeOps.java file, work on the definition of the following methods:

1. The compareTrees() method has two input trees named t1 and t2, and should return true if the two trees have the same shape, i.e. the same number of nodes with the same geometric arrangement of the nodes. The content of the nodes does not matter. If the two input trees do not have the same shape, this method should return false.
2. The replaceOccurrences() method has three inputs: a tree t and two strings oldString and newString. This method should replace all occurrences of oldString in t with newString by altering the content of nodes in the input tree.
3. The printLevel() method has two inputs, a tree t and an integer level. This method should print out all the strings contained in nodes of the tree that occur at the input level. Recall that the level of a tree node is the number of nodes on the path from the root of the tree down to this node. So the level of the root of the tree is 1, the level of the root's children is 2, the level of the root's grandchildren is 3, and so on.
4. The printPreOrder() method has one input, a tree t. This method prints out all the strings contained in nodes of the tree, as the tree is traversed in PreOrder traversal (root, left, right).
5. The printPostOrder() method has one input, a tree t. This method prints out all the strings contained in nodes of the tree, as the tree is traversed in PostOrder traversal (left, right, root).
6. The printInOrder() method has one input, a tree t. This method prints out all the strings contained in nodes of the tree, as the tree is traversed in InOrder traversal (left, root, right).

Test your code:

Add testing code to test each method as you define it. Think carefully when constructing the trees you use for testing your methods. Here is some of our sample output. Use this only as a guideline -- there are many more tests that ought to be done.