C++ Program:

You are to write methods to build and maintain a binary sort/search tree without balancing operations. The records to be maintained in the BST are of the form:

Employee ID #, Age, Name

Employee ID # is the primary key.

Your main program should be menu driven and should input and execute any sequence of the four menu options/commands given below. The commands add data into a binary search tree, delete data from a tree, find a given record in the tree, or list the entire tree contents.

Commands in menu:

INSERT

inserts a given record in the tree

DELETE

deletes record with the given key (id)

FIND

search for record with given key and if found, print the name, age, grade.

REPORT

gives a listing of all records in the tree in ascending order of ID numbers, along with the level where each node is stored on the tree.

Notes:

1. You are required to implement the in-order method using iteration and stacks (not recursion).

2. Example of runs:

What would you like to do?

1. Add a node to the tree

2. Delete a node from the tree

3. Find a node in the tree for a given ID#

4. Report the contents of the tree

5. Exit program

Choose:

1

Please enter the ID number, age and name:

700 52 RAO

Node added.

What would you like to do?

1. Add a node to the tree

2. Delete a node from the tree

3. Find a node in the tree for a given ID#

4. Report the contents of the tree

5. Exit program

Choose:

1

Please enter the ID number, age and name:

984 22 JONES

Node added.

What would you like to do?

1. Add a node to the tree

2. Delete a node from the tree

3. Find a node in the tree for a given ID#

4. Report the contents of the tree

5. Exit program

Choose:

1

Please enter the ID number, age and name:

400 36 SMITH

Node added.

What would you like to do?

1. Add a node to the tree

2. Delete a node from the tree

3. Find a node in the tree for a given ID#

4. Report the contents of the tree

5. Exit program

Choose:

4

Contents of tree are:

400 36 SMITH level 1

700 52 RAO level 0

984 22 JONES level 1

What would you like to do?

1. Add a node to the tree

2. Delete a node from the tree

3. Find a node in the tree for a given ID#

4. Report the contents of the tree

5. Exit program

Choose:

3

What is the id number of person?

700

The name is: RAO

The age is: 52

What would you like to do?

1. Add a node to the tree

2. Delete a node from the tree

3. Find a node in the tree for a given ID#

4. Report the contents of the tree

5. Exit program

Choose:

2

What is the id of person to be deleted?

984

What would you like to do?

1. Add a node to the tree

2. Delete a node from the tree

3. Find a node in the tree for a given ID#

4. Report the contents of the tree

5. Exit program

Choose:

4

Contents of tree are:

400 36 SMITH level 1

700 52 RAO level 0

What would you like to do?

1. Add a node to the tree

2. Delete a node from the tree

3. Find a node in the tree for a given ID#

4. Report the contents of the tree

5. Exit program

Choose:

5

Thank you and goodbye