1. Refer to program p3-1-BinarySearchTree.cs
a. Write code to build a Binary Search Tree with the following nodes: 55, 29, 80, 22, 41, 72, 35, 78,44, 90, 18, 88, 25, 60. Print screen shot of the run.
b. Add one operation in your program that finds the height of BST. Find the height of the BST you build in a) by calling this method in the Main method
c. Draw the tree (on paper, preferably using MS-Word).
d. Draw the tree after deleting node 90
e. Draw the tree after deleting node 80 (from the original tree, not from after d))
f. Draw the tree after deleting node 55 (from the original tree, not from after d) and e))
g. Draw the tree after inserting a node whose key is 43 to the original BST.
2. In a BST with n nodes, how many comparisons are needed for searching, insertion, and deletion in worst case, respectively? How many comparisons are needed for these operation in average case, respectively?
3. Write a class of BST of Employee records (Employee empIDis used as key). The class must contain the following operations:
• Search a node (given anemployee's empID), and print the record when it is found.
• Insert a node (given a new employee record)
• Delete a node (given anemployee's empID)
• Print out of all employee records in the BST in in-ordertraversal.
Write the Main method to test your program as follows:
• Create an empty BST.
• Insert 10 Employee records into the BST in the following order:
empID Name Salary
1055 name1 Random 40k-90k
1029 name2 Random 40k-90k
1080 name3 Random 40k-90k
1022 name4 Random 40k-90k
1041 name5 Random 40k-90k
1072 name6 Random 40k-90k
1035 name7 Random 40k-90k
1078 name8 Random 40k-90k
1044 name9 Random 40k-90k
1090 name10 Random 40k-90k
and print the BST in in-order to confirm 10 records are inserted correctly.
• Search an employee record (given anemployee's empID), and print the employee record if the empIDis found.
• Delete an employee record (given anemployee's empID), and print the BST in in-order to confirm that the record is deleted.
The Employee class is given as follow:
classEmployee
{
publicstring name;
publicintempID;
publicdouble salary;
publicvoid Input()
{
Console.Write("Name: ");
name = Console.ReadLine();
Console.Write("ID: ");
empID = int.Parse(Console.ReadLine());
Console.Write("Salary: ");
salary = double.Parse(Console.ReadLine());
}
publicOutput()
{
Console.WriteLine("[{0}|{1}|{2:C}]", name, empID, salary);
}
publicoverridestringToString()
{
returnstring.Format("({0}|{1}|{2:C})", name, empID, salary);
}
}
Attachment:- p3-1_binarysearchtree.rar