Trees
Linux/Emacs Tip(s) of the Day
who [linux] Lists other users logged onto your machine.
-
date [linux] Prints the date and time.
-
cal [linux]
Prints calendar for given month and year, e.g. cal 4 2012
-
M-x calendar [emacs] Displays a calendar (C-x < or C-x > to scroll)
-
C-x 2 [emacs] Splits window horizontally
-
C-x 3 [emacs] Splits window vertically
-
C-x o (oh, not zero) [emacs] Switch between windows
-
C-x f [emacs] Find the file for your newly opened window
-
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:
- 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.
- 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.
- 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:
|