CS 162 Fall 2001 Assignment 11 – Binary Trees – The Beginning 100 points
Assigned: 12/03/2001
Due: 12/07/2001 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 thoroughly 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 improved 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 improved-card.h, improved-deck.h, and improved-deck.cpp (either rename them or change the includes to use “improved” – other than that no changes needed in these – existing versions are fine).
Details:
1)
You don’t necessarily need to use the deck class, but it
is actually handy for coming up with some cards to use. If you do the
following:
Deck myDeck;
myDeck.shuffle();
Then any
calls to draw, such as shown below will give you a semi-random card
Card nextCard = myDeck.Draw();
2)
The Includes
function 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.
3)
FindMax takes no parameters and returns the value
that is the largest found
4)
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.
5)
Stop every so often
so that we can see what is happening without it all streaming past wildly on
the screen.
6)
I have updated the
DisplayTree function – output will look a little different than shown below.
7)
I think that the
cards used may be different than in my interaction below – depending on what
you do.
8)
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. That is avoiding the task.
Hand-in:
1) Listing of the program
2) Disk with all relevant .h and .cpp files, plus
your .exe file. NAME YOUR CLIENT FILE
yourlastname11.cpp Name your project
yourlastname11 so that the executable will be yourlastname10.exe. If you are
working in pairs, use both last names (e.g. redmondsmith11.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>