Project 2 Solution

PROGRAM DESCRIPTION

In this C++ program, you will use concepts from Chapter 4 to implement a splay tree based on the binary search tree class discussed in the textbook. In particular, your program will add two methods, rotate() and splay(), along with necessary modifications, to the original binary search tree class that is provided to implement a fully functioning splay tree

REQUIREMENTS

You will be provided the binary search tree class template code in a file called bstSplay.h along with an exceptions header file dsexceptions.h.
The following changes will be made to the bstSplay.h class header file:
You will add the following two methods to implement the core splay functionality:
void rotate( BinaryNode *t )

{

// fill your code here

}

void splay( BinaryNode *t )

{

// fill your code here

}

The rotate() method takes as input a node t and rotates it with its parent. The splay() method takes as input a node t and splays it all the way up to the root based on the rotations discussed in class – you must use rotate() to implement splay().

Since the splay operation requires the notion of a parent (or grandparent), you will add a BinaryNode member pointer called parent to go along with the left and right member pointers in the BinaryNode struct. This will also require adding the appropriate assignment for the parent member pointer to other parts of the code, such as the constructors, as well as the insert(), contains(), rotate(), and splay() methods.
The printTree() method currently prints out the inorder traversal of the tree. You will add code (either in additional methods or embedded inside the printTree() method) to also print out the preorder and postorder traversal results of the splay tree.
You may require other minor code modifications necessary depending on your implementation, such as adding error checking when removing elements (i.e., cannot remove an element from an empty tree).
1
You will create a project2.cpp implementation file that will support the following:
o Your implementation will support a BinarySearchTree with an int, float, and char data type (i.e., you may instantiate three binary search trees, one of each data type).

o You will prompt the user for and read in the data type for the splay tree – int, float, or char. Then, you will display a menu with the following options in a loop until the user enters the proper value to exit the menu (and the program):

(1)insert <data type into tree
(2)remove <data type from tree
(3)print tree traversals
(4)exit program
All other options will result in an error message followed by the menu choices again. Note that you may have a separate menu for each data type – displaying only the one chosen by the user.

Your code should be well documented in terms of comments. For example, good comments in general consist of a header (with your name, course section, date, and brief description), comments for each variable, and commented blocks of code.
Your program will be graded based largely on whether it works correctly on the CSE machines (e.g., cse01, cse02, …, cse06), so you should make sure that your program compiles and runs on a CSE machine.
You should contact your instructor if there is any question about what is being asked for.
This is an individual programming assignment that must be the sole work of the individual student. Any instance of academic dishonesty will result in a grade of “F” for the course, along with a report filed into the Academic Integrity Database.


•

SAMPLE OUTPUT (input shown in bold green):

$ ./a.out

What splay tree data type (int, float, char)? int

Enter option choice 1 - 4:

insert integer into tree
remove integer from tree
print tree traversals
exit program
5
Invalid choice. Try again.

2
Enter option choice 1 - 4:

insert integer into tree
remove integer from tree
print tree traversals
exit program
1
Enter integer key to insert: 5

Insert complete

Enter option choice 1 - 4:

insert integer into tree
remove integer from tree
print tree traversals
exit program
3
traversal
:
5
inorder
preorder
traversal
:
5
postorder traversal : 5

Print complete

Enter option choice 1 - 4:

insert integer into tree
remove integer from tree
print tree traversals
exit program
1
Enter integer key to insert: 4

Insert complete

Enter option choice 1 - 4:

insert integer into tree
remove integer from tree
print tree traversals
exit program
3
traversal : 4 5
inorder
preorder
traversal : 4
5
postorder traversal : 5
4
Print complete
 
Enter option choice 1 - 4:

insert integer into tree
remove integer from tree
print tree traversals
exit program
1
Enter integer key to insert: 8

Insert complete

Enter option choice 1 - 4:

insert integer into tree
remove integer from tree
print tree traversals
exit program
3
traversal : 4 5 8
inorder
preorder
traversal : 8
5
4
postorder traversal : 4
5
8
Print complete
 
 
Enter option choice 1 - 4:
3
insert integer into tree
remove integer from tree
print tree traversals
exit program
1
Enter integer key to insert: 2

Insert complete

Enter option choice 1 - 4:

insert integer into tree
remove integer from tree
print tree traversals
exit program
3
traversal : 2 4 5
8
inorder
preorder
traversal : 2
8
4
5
postorder traversal : 5
4
8
2
Print complete
 
 
 
Enter option choice 1 - 4:
 
insert integer into tree
remove integer from tree
print tree traversals
exit program
1
Enter integer key to insert: 7

Insert complete

Enter option choice 1 - 4:

insert integer into tree
remove integer from tree
print tree traversals
exit program
3
traversal : 2 4 5
7
8
inorder
preorder
traversal : 7
2
5
4
8
postorder traversal : 4
5
2
8
7
Print complete
 
 
 
 
Enter option choice 1 - 4:
 
 
insert integer into tree
remove integer from tree
print tree traversals
exit program
2
Enter integer key to remove: 5

Remove complete

Enter option choice 1 - 4:

insert integer into tree
remove integer from tree
print tree traversals
exit program
3
traversal : 2
4
7
8
inorder
preorder
traversal : 4
2
7
8
postorder traversal : 2
8
7
4
Print complete
4:
 
 
Enter option choice 1 -
 
 
(1) insert integer into
tree
 
4
remove integer from tree
print tree traversals
exit program
4 Terminating...
$ ./a.out

What splay tree data type (int, float, char)? integer Unknown data type. Terminating...

$ ./a.out

What splay tree data type (int, float, char)? float Enter option choice 1 - 4:

(1) insert floating-point number into tree

(2) remove floating-point number from tree

(3) print tree traversals

(4) exit program

2
Enter floating-point number key to remove: 34.22 Empty tree

Remove complete

Enter option choice 1 - 4:

insert floating-point number into tree
remove floating-point number from tree
print tree traversals
exit program
3
Empty tree

Print complete

Enter option choice 1 - 4:

insert floating-point number into tree
remove floating-point number from tree
print tree traversals
exit program
1
Enter floating-point number key to insert: 34.22 Insert complete

Enter option choice 1 - 4:

insert floating-point number into tree
remove floating-point number from tree
print tree traversals
exit program
3
traversal
:
34.22
inorder
preorder
traversal
:
34.22
postorder traversal : 34.22

Print complete

Enter option choice 1 - 4:

insert floating-point number into tree
remove floating-point number from tree
print tree traversals
exit program
1
Enter floating-point number key to insert: 34.23 Insert complete

Enter option choice 1 - 4:

(1) insert floating-point number into tree

5
remove floating-point number from tree
print tree traversals
exit program
3
traversal : 34.22 34.23
inorder
preorder
traversal : 34.23
34.22
postorder traversal : 34.22
34.23
Print complete
 
Enter option choice 1 - 4:
 
insert floating-point number into tree
remove floating-point number from tree
print tree traversals
exit program
2
Enter floating-point number key to remove: 89.11

89.11 not found

Remove complete

Enter option choice 1 - 4:

insert floating-point number into tree
remove floating-point number from tree
print tree traversals
exit program
3
traversal : 34.22 34.23
inorder
preorder
traversal : 34.23
34.22
postorder traversal : 34.22
34.23
Print complete
 
Enter option choice 1 - 4:
 
insert floating-point number into tree
remove floating-point number from tree
print tree traversals
exit program
4 Terminating...
$ ./a.out

What splay tree data type (int, float, char)? char Enter option choice 1 - 4:

(1) insert character into tree

(2) remove character from tree

(3) print tree traversals

(4) exit program

3
Empty tree

Print complete

Enter option choice 1 - 4:

insert character into tree
remove character from tree
print tree traversals
exit program
1
Enter character key to insert: d

Insert complete

Enter option choice 1 - 4:

insert character into tree
remove character from tree
6
print tree traversals
exit program
1
Enter character key to insert: f

Insert complete

Enter option choice 1 - 4:

insert character into tree
remove character from tree
print tree traversals
exit program
3
traversal
: d
f
inorder
preorder
traversal
: f
d
postorder traversal : d f

Print complete

Enter option choice 1 - 4:

insert character into tree
remove character from tree
print tree traversals
exit program
1
Enter character key to insert: R

Insert complete

Enter option choice 1 - 4:

insert character into tree
remove character from tree
print tree traversals
exit program
3
traversal
: R
d
f
inorder
preorder
traversal
: R
d
f
postorder traversal : f d R

Print complete

Enter option choice 1 - 4:

insert character into tree
remove character from tree
print tree traversals
exit program
2
Enter character key to remove: Q

Q not found

Remove complete

Enter option choice 1 - 4:

insert character into tree
remove character from tree
print tree traversals
exit program
2
Enter character key to remove: f

Remove complete

Enter option choice 1 - 4:

insert character into tree
remove character from tree
print tree traversals
exit program
7

 
 
 
3
traversal : R d
inorder
preorder
traversal : d R
postorder traversal : R d

Print complete

Enter option choice 1 - 4:

insert character into tree
remove character from tree
print tree traversals
exit program
4 Terminating...
SUBMISSION:

You will electronically submit your source code file(s) and a README file where you explain all the information required for the grader to grade your program (i.e., how to compile and run it, an example, how you did it, etc.) to the Project 2 dropbox in Canvas by the due date.
8