Assignment #6 binary tree Solution

You are required to turn in the following source file(s) in C++:

Assignment6.cpp <assignment6/Assignment6.cpp (No need to be modified)
BinarySearchTree.h <assignment6/BinarySearchTree.h (More code need to
be added)

*/_ _/*



Objectives:


-This is to practice making binary search trees.


Program Description

This is a programming assignment. You will develop a binary tree with
some of its operations.



1. You need to implement a data structure to represent a node. Each node
should have data fields containing course number and course title. (its
key will be course number), its parent node called "parent", its left child node called "left", and its right child node called "right".

2. Using the nodes above, you need to implement a binary search tree
using their keys.

3. When you compare two nodes, compare their course numbers in
alphabetical order (each character's ASCII number).

4. Your binary search tree needs to have operations "inorderTreeWalk",
"preorderTreeWalk", and "postorderTreeWalk"
that will print all node keys in a certain order (see the lecture
notes/textbook.)

5. Your binary search tree needs to have operations "treeInsert",
"rightRotate", "leftRotate", "treeSearch", "treeMinimum", "treeMaximum",
"treeSuccessor", and "treePredecessor".
(see the lecture notes/textbook for those operations.)

6. BinarySeachTree class should have a constructor that initializes its
root to be NULL, and a destructor that will delete all nodes in the tree
and perform garbage collections. The destructor should also print “The
number of nodes deleted: X” where X is the number of nodes deleted and
it should be called when a user chooses to exit the program.

7. You should implement a driver class with a main method which takes
the following commands (A, B, C, D, E, F, G, H, I, J, K, Q) from the
keyboard:

A --- In-order print command, it should print all keys in the tree using
the in-order, using the following format, by placing a carriage return
between keys:

Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE310, Course Title: Data Structures and Algorithms

It should print "tree is empty" if the tree is empty.



B --- Pre-order print command, it should print all keys in the tree
using the pre-order, using the following format, by placing a carriage
return between keys:

Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE310, Course Title: Data Structures and Algorithms

It should print "tree is empty" if the tree is empty.



C --- Post-order print command, it should print all keys in the tree
using the post-order, using the following format, by placing a carriage
return between keys:

Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: ASU101, Course Title: The ASU Experience

It should print "tree is empty" if the tree is empty.



D --- Tree Minimum command, it should call "treeMinimum" and print the
minimum value as " The first course is Course Number: XXX, Course Title:
YYY "
where XXX is the course number of the first course and YYY is the course
title of the first course in the tree.
It should print "tree is empty" if the tree is empty.



E --- Tree Maximum command, it should call "treeMaximum" and print the
maximum value as " The last course is Course Number: XXX, Course Title:
YYY "
where XXX is the course number of the last course and YYY is the course
title of the last course in the tree.
It should print "tree is empty" if the tree is empty.



F --- Tree Predecessor command, it should prompt “Please enter a course
number to find its predecessor:\n”, and read in the input. It should
call "treePredecessor" and print the predecessor as " The predecessor of
XXXX is Course Number: AAAA, Course Title: BBBB " where XXXX is the
course number entered by a user and AAAA and BBBB are the course name
and course title of the predecessor of XXXX. If it does not have any
predecessor, print “XXXX does not have any predecessor”.
It should print "tree is empty" if the tree is empty.



G --- Tree Successor command, it should prompt “Please enter a course
number to find its successor:\n”, and read in the input. It should call
"treeSuccessor" and print the successor as "The successor of XXXX is
Course Number: AAAA, Course Title: BBBB" where XXXX is the course number
entered by a user and AAAA and BBBB are the course name and course title
of the successor of XXXX. If it does not have any successor, print “XXXX
does not have any successor”.
It should print "tree is empty" if the tree is empty.



H --- Search command, it should ask user “Please enter a course number
to search:\n”.
Then you should call "treeSearch" operation to search the value.
Then the program should print "XXXX has course title: YYYY" if it is
found, and print "XXXX not found", otherwise, where XXXX is the course
number entered by a user, and YYYY is its title.



I --- Insert command, it should ask user “"Please enter a
courseNumber/courseTitle to insert:\n”.
Then you should call "treeInsert" operation to insert this value.

Then the program should print "XXX with course title: YYY inserted" if
the same course number does not exist in the tree, and it is inserted
successfully, and print "XXX with course title: YYY not inserted",
otherwise (i.e., the same course number already exists in the tree),
where XXX and YYY are the course number and course title entered by a user.



J --- Right Rotate command, it should ask user “Please enter a
courseNumber to right-rotate:\n”.
Then you should call "rightRotate" operation to search its node and
right-rotate around the tree around the node.

Then the program should print "Right Rotation around XXX is successful"
if the course number exists in the tree, its left child exits, and its
it is right-rotated successfully, and print "Right Rotation cannot be
performed around XXX", otherwise, where XXX is the course number entered
by a user.



K ---Left Rotate command, it should ask user “Please enter a
courseNumber to left-rotate:\n”.
Then you should call "leftRotate" operation to search its node and
left-rotate around the tree around the node.

Then the program should print "Left Rotation around XXX is successful"
if the course number exists in the tree, its right child exits, and its
it is left-rotated successfully, and print "Left Rotation cannot be
performed around XXX", otherwise, where XXX is the course number entered
by a user.



Q -- Quit the program and exit. The binary search tree object should be
deleted, and it should print how many nodes are deleted.



The following is an example run.



Sample Output: (the user enters the string shown in bold)

-------------------------------------

Choice Action
------ ------
A Inorder Print
B Preorder Print
C Postorder Print
D Tree Minimum
E Tree Maximum
F Tree Predecessor
G Tree Successor
H Tree Search
I Tree Insert
J Right Rotation
K Left Rotation
Q Quit
? Display Help

What action would you like to perform?
*I *
Please enter a courseNumber/courseTitle to insert:
Enter a course number
*CSE310*
Enter a course title
*Data Structures and Algorithms*
CSE310 with course title: Data Structures and Algorithms inserted
What action would you like to perform?
*I*
Please enter a courseNumber/courseTitle to insert:
Enter a course number
*CSE240*
Enter a course title
*Intro to Programming Languages*
CSE240 with course title: Intro to Programming Languages inserted
What action would you like to perform?
*I*
Please enter a courseNumber/courseTitle to insert:
Enter a course number
*CSE220*
Enter a course title
*Programming for Computer Engineering*
CSE220 with course title: Programming for Computer Engineering inserted
What action would you like to perform?
*I*
Please enter a courseNumber/courseTitle to insert:
Enter a course number
*MAT243*
Enter a course title
*Discrete Math Structures*
MAT243 with course title: Discrete Math Structures inserted
What action would you like to perform?
*I*
Please enter a courseNumber/courseTitle to insert:
Enter a course number
*EEE120*
Enter a course title
*Digital Design Fundamentals*
EEE120 with course title: Digital Design Fundamentals inserted
What action would you like to perform?
*I*
Please enter a courseNumber/courseTitle to insert:
Enter a course number
*PHY101*
Enter a course title
*Introduction To Physics*
PHY101 with course title: Introduction To Physics inserted
What action would you like to perform?
*I*
Please enter a courseNumber/courseTitle to insert:
Enter a course number
*ASU101*
Enter a course title
*The ASU Experience*
ASU101 with course title: The ASU Experience inserted
What action would you like to perform?
*A*

Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: CSE240, Course Title: Intro to Programming Languages
Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: PHY101, Course Title: Introduction To Physics

What action would you like to perform?
*B*

Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: CSE240, Course Title: Intro to Programming Languages
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: ASU101, Course Title: The ASU Experience
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: PHY101, Course Title: Introduction To Physics

What action would you like to perform?
*C*

Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: CSE240, Course Title: Intro to Programming Languages
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: PHY101, Course Title: Introduction To Physics
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: CSE310, Course Title: Data Structures and Algorithms

What action would you like to perform?
*F*
Please enter a course number to find its predecessor:
*CSE240*
The predecessor of CSE240 is Course Number: CSE220, Course Title:
Programming for Computer Engineering

What action would you like to perform?
*G*
Please enter a course number to find its successor:
*PHY101*
PHY101 does not have any successor
What action would you like to perform?
*D*
The first course is Course Number: ASU101, Course Title: The ASU Experience

What action would you like to perform?
*E*
The last course is Course Number: PHY101, Course Title: Introduction To
Physics

What action would you like to perform?
*H*
Please enter a course number to search:
*CSE220*
CSE220 has course title: Programming for Computer Engineering
What action would you like to perform?
*H*
Please enter a course number to search:
*EEE120*
EEE120 has course title: Digital Design Fundamentals
What action would you like to perform?
*I*
Please enter a courseNumber/courseTitle to insert:
Enter a course number
*FSE100*
Enter a course title
*Introduction to Engineering*
FSE100 with course title: Introduction to Engineering inserted
What action would you like to perform?
*I*
Please enter a courseNumber/courseTitle to insert:
Enter a course number
*ENG200*
Enter a course title
*Critical Reading & Writing About Literature*
ENG200 with course title: Critical Reading & Writing About Literature
inserted
What action would you like to perform?
*H*
Please enter a course number to search:
*FSE100*
FSE100 has course title: Introduction to Engineering
What action would you like to perform?
*J*
Please enter a courseNumber to right-rotate:
*CSE310*
Right Rotation around CSE310 is successful
What action would you like to perform?
*A*

Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: CSE240, Course Title: Intro to Programming Languages
Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: ENG200, Course Title: Critical Reading & Writing About
Literature
Course Number: FSE100, Course Title: Introduction to Engineering
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: PHY101, Course Title: Introduction To Physics

What action would you like to perform?
*B*

Course Number: CSE240, Course Title: Intro to Programming Languages
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: FSE100, Course Title: Introduction to Engineering
Course Number: ENG200, Course Title: Critical Reading & Writing About
Literature
Course Number: PHY101, Course Title: Introduction To Physics

What action would you like to perform?
*C*

Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: ENG200, Course Title: Critical Reading & Writing About
Literature
Course Number: FSE100, Course Title: Introduction to Engineering
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: PHY101, Course Title: Introduction To Physics
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: CSE240, Course Title: Intro to Programming Languages

What action would you like to perform?
*K*
Please enter a courseNumber to left-rotate:
*EEE120*
Left Rotation around EEE120 is successful
What action would you like to perform?
*A*

Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: CSE240, Course Title: Intro to Programming Languages
Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: ENG200, Course Title: Critical Reading & Writing About
Literature
Course Number: FSE100, Course Title: Introduction to Engineering
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: PHY101, Course Title: Introduction To Physics

What action would you like to perform?
*B*

Course Number: CSE240, Course Title: Intro to Programming Languages
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: FSE100, Course Title: Introduction to Engineering
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: ENG200, Course Title: Critical Reading & Writing About
Literature
Course Number: PHY101, Course Title: Introduction To Physics

What action would you like to perform?
*C*

Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: ENG200, Course Title: Critical Reading & Writing About
Literature
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: FSE100, Course Title: Introduction to Engineering
Course Number: PHY101, Course Title: Introduction To Physics
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: CSE240, Course Title: Intro to Programming Languages

What action would you like to perform?
*F*
Please enter a course number to find its predecessor:
*PHY102*
PHY102 does not have any predecessor
What action would you like to perform?
*G*
Please enter a course number to find its successor:
*CSE310*
The successor of CSE310 is Course Number: EEE120, Course Title: Digital
Design Fundamentals

What action would you like to perform?
*D*
The first course is Course Number: ASU101, Course Title: The ASU Experience

What action would you like to perform?
*E*
The last course is Course Number: PHY101, Course Title: Introduction To
Physics

What action would you like to perform?
*A*

Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: CSE240, Course Title: Intro to Programming Languages
Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: ENG200, Course Title: Critical Reading & Writing About
Literature
Course Number: FSE100, Course Title: Introduction to Engineering
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: PHY101, Course Title: Introduction To Physics

What action would you like to perform?
*B*

Course Number: CSE240, Course Title: Intro to Programming Languages
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: FSE100, Course Title: Introduction to Engineering
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: ENG200, Course Title: Critical Reading & Writing About
Literature
Course Number: PHY101, Course Title: Introduction To Physics

What action would you like to perform?
*C*

Course Number: ASU101, Course Title: The ASU Experience
Course Number: CSE220, Course Title: Programming for Computer Engineering
Course Number: ENG200, Course Title: Critical Reading & Writing About
Literature
Course Number: EEE120, Course Title: Digital Design Fundamentals
Course Number: FSE100, Course Title: Introduction to Engineering
Course Number: PHY101, Course Title: Introduction To Physics
Course Number: MAT243, Course Title: Discrete Math Structures
Course Number: CSE310, Course Title: Data Structures and Algorithms
Course Number: CSE240, Course Title: Intro to Programming Languages

What action would you like to perform?
*Q*
The number nodes deleted: 9

----------------------------------------------



*Implementation/Documentation Requirements:*

* You need to implement this program using C++ and it has to read from
the standard input (from a keyboard).
* Your program needs to compile and execute in general.asu.edu.
* Your code should be well documented and commented.
* You must use the provided data sets.
* Also you are not allowed to use any predefined data structures (such
as ones in the library in C++, etc.), you need to build your own
data structures and operations associated with them (such as Insert
or Search).
* Copying any codes from other people's programs is considered to be
cheating and will lead to a report to the Dean and you will be
penalized.



*What to turn in:*

You must turn in C++ source code using the following submission site:

http://courses.eas.asu.edu/cse310/

First, you need to login, and click on the *Submission* page. You need
to select the correct assignment number. The types of files that you can
submit are .cpp, or .h files. They have to compile and execute in
*/general.asu.edu/* server. (You can access general.asu.edu by SSH, and
login using your ASU UserID and password.)

For C++, the files need to compile and execute with the commands:

/ /

/g//++ *.cpp/

/ /

/./a.out/



You program should be well commented and documented, make sure the first
few lines of your program contain your name, your ASU email address, and
a description of each file. While you will not be graded on style
technique ("i++" or "i = i + 1") or indenting by 4 spaces or tables, you
should use indentation, good variable names, and clear, easy to read,
and specific comments. (You will be graded on comments.)





Input

The following files are sample test cases that will be used as input for
your program (Right-click and use "Save As"):

Test Case #1 <assignment6/input1.txt
Test Case #2 <assignment6/input2.txt
Test Case #3 <assignment6/input3.txt

Sample output for the input1.txt

Test Case #1 <assignment6/output1.txt

You can test your program as follows:

For a C++ program, after compiling your files, one way is:

/./a.out//< input1.txt/

or you can replace a.out with whichever your executable is.


Error Handling

Your program will be tested with other input besides the ones above,
thus is expected to be robust.