CS 162 Spring 2000 Assignment 10 – Binary Trees – The Beginning
100 pointsAssigned: 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.Hand-in:
1)
Listing of the programMiscellaneous:
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>