CS 451/651 Homework 0
- Trees and Recursion
Programming languages are inherently highly recursive. (For
example, an "expression" may contain function calls; each
function call can contain arguments, which are expressions; each
expression may contain function calls; each ...)
Compilers, therefore, work with recursive data structures (such as
trees), and contain recursive algorithms.
Bottom line: you'll need to be familiar with recursion in order
to succeed in this course. (Good news: when you're done with this
course, you'll be able to rely on recursion as a tried and tested tool
which you can use again and again in your career.)
Assignment: understand and
extend a simple recursive program (provided on the class web site)
download source
from here
Due: next class
meeting (Sept 14)
Purpose:
- get things underway in finding the class web site, finding
where to submit homeworks, etc.
- make sure you're underway with a working Java system
- review/reinforce recursive programming
- review/reinforce abstract classes, virtual functions etc.
- help you get used to working with programs that have partially
been written by someone else
((none of this should be totally new!))
Details:
I've written a program, SimpleTreeWalk.java. This defines
a Tree made up of TreeNodes, an abstract class, whose concrete
instances are either "branch" or "leaf" nodes. Member functions
in TreeNodes support two activities: printing and finding the
minimum value. The main function creates a tree, prints it, and
finds the minimum value.
The program should compile and run.
- It should correctly print out the tree. (That part is
complete)
(-- though you're always welcome to tweak the code to provide more
information, to experiment etc.)
((You'll notice that I've used a small trick to get "print()" to
indent the tree as it goes down. This is not an essential part of
the assignment.))
- The program that you've downloaded will NOT yet calculate a
minimum value. That's
your job: to
complete the implementation of the findMin() function so that it
correctly
calculates and returns the minimum value contained in its tree or
subtree. (Feel free to add additional println statements to help
you understand what's going on.)
Note: I've used a Java trick,
printing the value of "this" as a simple way to identify each TreeNode
instance. Java prints the hex address of the object: it's
not pretty, but it is a unique identifier and thus sometimes useful in
debugging.