halloween tree

CS230 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 4 2012
  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/Lab9 directory contains the following files:

  • Tree.java code file you are familiar with
  • TreeOps.java which contains definitions for several methods on Trees. You worked with them in lecture.
  • MakeTestTrees.java file which contains some sample trees that you can copy and paste into your code as you need.
Download lab9 into your working directory.

Define 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.

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. This was generated via a separate LabTreeOpsTest.java class (you can make your own testing class). Most of the trees used in this testing file are included in the MakeTestTrees file in the lab9 download folder. Use this only as a guideline -- there are many more tests that ought to be done.

So, you are having a back pain...

Binary Trees are a natural fit to arrange information that is related by simple Yes or No responses. Your task is to write (almost from scratch) a simple "expert system", which will produce a medical diagnosis for a back pain. The diagnosis will be based on the user's answers to some questions, each of which has a Yes/No answer. Answering the Yes/No questions effectively guides the user's path from the root of the tree to the node containing the answer.

Start with the BackPainExpert.java file in the lab9directory you downloaded.

Here is a sample transcript: