CS 162 Spring 2000 Assignment 10 – Binary Trees – The Beginning 100 points

Assigned: 04/25/2000

Due: 05/01/2000 at the start of class.

Pairs: You may work in pairs if you want. Note, during the course of the semester, you cannot pair with any one person more than twice. If you work in a pair, turn in ONE copy that is the work of both of you, with both of your names on it. Each member of the pair will receive the same grade for that lab.

Main Assignment:

A partial implementation of simple binary trees has been developed (SimpleTreeNode.h) as a template class. Your mission is to: 1) Write functions to add to the template class: Includes, FindMax, and CountNodes; 2) Write a main which sets up the tree and tests your functions, as displayed below. We will use Cards as our element type (but you could just as easily use any class that defines the operators == > < etc. I have put an updated card.cpp file out on my WWW page (under review and under assignments) that breaks ties between cards of the same rank using the suit. SimpleTreeNode.h is also out there, along with card.h, deck.h, and deck.cpp (no changes needed – old versions are fine).

Details:

1) Includes should take one parameter an object of the type that the tree is made up of, and return a) how deep in the tree the node was found – if it was found (root is 1) or b) if the node was not found return a negative number indicating how deep the search went (e.g. if searched to leaf 3 deep and didn’t find value, return –3; Thus testing the return value.vs 0 will indicate whether the value was found.

  1. FindMax takes no parameters and returns the value that is the largest found
  2. CountNodes takes no parameters and returns an integer specifying how many nodes were in the tree. Hint, it may be easiest to do this with a recursive function.
  3. Stop every so often so that we can see what is happening without it all streaming past wildly on the screen.
  4. You MUST write the functions described. Solving the problem by keeping track of largest and count in main and simply updating them as cards are drawn does not count as a solution.

Hand-in:

1) Listing of the program

  1. Disk with all relevant .h and .cpp files, plus your .exe file. NAME YOUR CLIENT FILE yourlastname10.cpp Name your project yourlastname10 so that the executable will be yourlastname10.exe. If you are working in pairs, use both last names (e.g. redmondsmith10.cpp)

Miscellaneous:

1) If you have any questions about what should be done, please ask!!

2) MAKE SURE YOUR PROGRAM WORKS! (i.e. more than just removing compile errors).

3) Remember: Indentation, meaningful variable names, symbolic constants, and meaningful comments. Weaknesses in any of these could result in points off. Also make sure you put YOUR NAME(s), section, and e-mail address in comments at the beginning of the program.

Sample Interaction:

new card: Ace of Diamonds

Tree now contains 2 nodes. The largest value is: Ace of Diamonds

Tree:

9 of Diamonds

Ace of Diamonds

WAIT> new card: 9 of Spades

Tree now contains 3 nodes. The largest value is: Ace of Diamonds

Tree:

9 of Diamonds

9 of Spades

Ace of Diamonds

WAIT> new card: 5 of Hearts

Tree now contains 4 nodes. The largest value is: Ace of Diamonds

Tree:

5 of Hearts

9 of Diamonds

9 of Spades

Ace of Diamonds

WAIT> new card: 6 of Clubs

Tree now contains 5 nodes. The largest value is: Ace of Diamonds

Tree:

5 of Hearts

6 of Clubs

9 of Diamonds

9 of Spades

Ace of Diamonds

WAIT> new card: 7 of Diamonds

Tree now contains 6 nodes. The largest value is: Ace of Diamonds

Tree:

5 of Hearts

6 of Clubs

7 of Diamonds

9 of Diamonds

9 of Spades

Ace of Diamonds

WAIT> new card: Ace of Hearts

Tree now contains 7 nodes. The largest value is: Ace of Hearts

Tree:

5 of Hearts

6 of Clubs

7 of Diamonds

9 of Diamonds

9 of Spades

Ace of Diamonds

Ace of Hearts

WAIT> new card: Queen of Spades

Tree now contains 8 nodes. The largest value is: Ace of Hearts

Tree:

5 of Hearts

6 of Clubs

7 of Diamonds

9 of Diamonds

9 of Spades

Queen of Spades

Ace of Diamonds

Ace of Hearts

WAIT> new card: 9 of Hearts

Tree now contains 9 nodes. The largest value is: Ace of Hearts

Tree:

5 of Hearts

6 of Clubs

7 of Diamonds

9 of Diamonds

9 of Hearts

9 of Spades

Queen of Spades

Ace of Diamonds

Ace of Hearts

WAIT> new card: Jack of Clubs

Tree now contains 10 nodes. The largest value is: Ace of Hearts

Tree:

5 of Hearts

6 of Clubs

7 of Diamonds

9 of Diamonds

9 of Hearts

9 of Spades

Jack of Clubs

Queen of Spades

Ace of Diamonds

Ace of Hearts

WAIT> new card: 2 of Spades

Tree now contains 11 nodes. The largest value is: Ace of Hearts

Tree:

2 of Spades

5 of Hearts

6 of Clubs

7 of Diamonds

9 of Diamonds

9 of Hearts

9 of Spades

Jack of Clubs

Queen of Spades

Ace of Diamonds

Ace of Hearts

WAIT> found Ace of Diamonds ? 2

found 9 of Spades ? 3

found 5 of Hearts ? 2

found 6 of Clubs ? 3

found 7 of Diamonds ? 4

found Ace of Hearts ? 3

found Queen of Spades ? 4

found 9 of Hearts ? 4

found Jack of Clubs ? 5

found 2 of Spades ? 3

found King of Clubs ? -4

found 8 of Spades ? -4

found 10 of Diamonds ? -5

found Ace of Spades ? -3

WAIT>