Com S 228 --- Introduction to Data Structures

			     HOMEWORK 13:
                                Trees
		 (File $Date: 1995/04/23 16:31:26 $)

Due: problem 2, at the beginning of lecture, May 1.

(In discussion sections the week of April 27, you will go over the last test,
and will discuss the problem 2 below.  So it would be wise to look at that
problem before discussion sections.)

In this homework, you will learn about trees (the data structure).

PLEASE NOTE: For each programming problem, hand in a printout of
your code files, and your transcript of testing.
Your code must only use standard features of C++,
and your transcript must demonstrate that it would work on the Com S machines.
We recommend testing on the Com S department machines to ensure this
(use the Unix command ``script'').
Your transcript and *each* file you print should have the file name
and your information (your ~/.me file as in HW0) at the top as comments.
You must use comments as we are doing in class
(see /home/cs228/public/assertion-notation.txt for details).
We are grading on these comments now.

For additional practice, we suggest that for at least some of the problems,
you write out a solution on paper first.  This is more like what the test
will be.  When you are happy with your paper version, try it on the
computer.  (Note that you must hand in a printout and a transcript, however.)


HEADINGTON & RILEY: 13

1. (suggested practice)
   Do some of the exercises in Headington and Riley's book for chapter 13
   (pp. 651-654).  I suggest at least exercises 13.1(a,b), 13.2(a,b,c,e,j,l,m),
   13.4(a), 13.5(c), 13.6(a), 13.7-10(parts a), 13.11(a,c,e),
   and 13.12-13(parts a and c).
   Do what parts seem useful to you, then look at the answers,
   which are at the end of the book in page A-186-7 for these problems.


2. (80 points)
   Solve programming problem 13.8 (twenty questions) on page 658 of
   Headington and Riley's book.  Your program should start with the
   initial tree given on page 660, so that it firsts asks the question
   "Does it have two legs?".

   For this problem, you must use a binary tree of some kind
   in an essential way in your implementation.

   Run the sample test input from the file
	/home/cs228/public/homework/hw13data.txt
   and any additional test cases you think are necessary.