Lab 05 Solution

Purpose:




The purpose of this lab is to implement a binary search tree in C++.




General Requirements:




In this lab, you are required to implement a binary search tree using a pointer implementation only (do not use an array). Each node of tree will have a key and left and right pointers, where the left pointer will point to its left child, and the right pointer will point to its right child. You are to read in a collection of numbers from a data file called data.txt. Duplicate keys are allowed in the binary search tree. You may hard code the file name if you wish. After building the structure, your program should ask the user to choose one of the options below:




‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐




Please choose one of the following commands:

1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax




6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit




The binary search tree should be implemented with an appropriate constructor and destructor.




The rest of the methods should be implemented as follows:




IsEmpty() – should return true if the tree is empty, i.e., if the root node is null.




Insert(x) – Insert a number x into the tree at its appropriate position. Note that a node including the root node will have keys with lower priority in its left subtree and higher priority keys in its right subtree.




Delete(x) – should delete the key x from BST if a key is present, else throw a message. FindMin() – Retrieve the smallest number from the tree.




FindMax() – Retrieve the largest number from the tree. Find(x) – Find the number if present in the tree.

Preorder () – Traverse the tree in preorder and print all the elements. Postorder() – Traverse the tree in postorder and print all the elements.

Inorder() – Traverse the tree in inorder and print all the elements.




Levelorder() – Traverse the tree in level order and print all the elements.







Expected Results:




data.txt: 53 22 7 90 34 76 92 22 8 81




We will insert these keys, in the given order, into an initially empty BST.



















53
53
53


53


22
22
22
90
















7
7











….










53




22 90










7
34
76
92
8
22


81













Please note that you are not expected to show tree graphically in your output. This is just for your reference.




Now that you have built the BST, these are the expected results of performing the various




options on BST.

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:

1‐ Insert




2‐ Delete

3‐ Find

4‐ FindMin




5‐ FindMax

6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

6




532278342290768192




‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐




Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find




4‐ FindMin

5‐ FindMax

6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit




7

782222345376819092

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find




4‐ FindMin

5‐ FindMax

6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

9‐ Exit

8




872234228176929053

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete




3‐ Find

4‐ FindMin

5‐ FindMax




6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

9

532290734769282281




‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax




6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

1

Enter number to be inserted:




81

Insert was successful.

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert




2‐ Delete




3‐ Find

4‐ FindMin

5‐ FindMax

6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit




1

Enter a number to be inserted:

2

Insert was successful







53




22 90












7
34
76
92
2
8
22


81












81






Please note that you are not expected to show tree graphically in your output. This is just for




your reference.




‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:

1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax




6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

6

532272834229076818192




‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:

1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax

6‐ Preorder




7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

7




278222234537681819092

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax

6‐ Preorder

7‐ Inorder




8‐ Postorder

9‐ Levelorder

10‐ Exit

8

287223422818176929053

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax

6‐ Preorder

7‐ Inorder




8‐ Postorder

9‐ Levelorder

10‐ Exit

9

532290734769228228181

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax

6‐ Preorder

7‐ Inorder

8‐ Postorder




9‐ Levelorder

10‐ Exit

2

Enter a number to be deleted:

9




Delete failed. Number is not present in tree.




‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐




Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax

6‐ Preorder




7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

2

Enter a number to be deleted:

8




Delete was successful




‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐




Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find




4‐ FindMin

5‐ FindMax

6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit




2

Enter a number to be deleted:

22

Delete was successful

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete




3‐ Find

4‐ FindMin

5‐ FindMax

6‐ Preorder

7‐ Inorder




8‐ Postorder

9‐ Levelorder

10‐ Exit




2

Enter a number to be deleted:

53

Delete was successful













76




22 90







7 34 81 92













2 81










Please note you are not expected to show tree graphically in your output. This is just for your




reference.




‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:

1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax




6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

3

Enter number to be found

81




Number is present in tree.

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:

1‐ Insert

2‐ Delete




3‐ Find

4‐ FindMin

5‐ FindMax




6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

3

Enter number to be found




11

Number is not present in tree.

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find




4‐ FindMin

5‐ FindMax

6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit




4

Minimum number: 2

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find




4‐ FindMin

5‐ FindMax

6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

5




Maximum number: 92

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete




3‐ Find

4‐ FindMin

5‐ FindMax




6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

6

7622723490818192




‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax




6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

7

2722347681819092




‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax




6‐ Preorder

7‐ Inorder

8‐ Postorder

9‐ Levelorder

10‐ Exit

8

2734228181929076

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐




Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin




5‐ FindMax

6‐ Preorder

7‐ Inorder




8‐ Postorder

9‐ Levelorder

10‐ Exit

9

7622907348192281

‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐‐

Please choose one of the following commands:




1‐ Insert

2‐ Delete

3‐ Find

4‐ FindMin

5‐ FindMax

6‐ Preorder

7‐ Inorder




8‐ Postorder

9‐ Levelorder

10‐ Exit

10




Done!







Submission:




Follow the conventions below to facilitate grading:




Source Code




Place all your source files (*.cpp, *.hpp) and input files in a single folder with no subfolders.




Name your folder using the convention Lastname_LabX (e.g., Smith_Lab05).




Include a functioning Makefile inside the folder. (The makefile should also include the clean command.)

Verify that your code runs on the Linux machines in the lab.




Compressed File




Compress using .zip, .rar, or .tar.gz.




Name your file using the convention Lastname_LabX (e.g., Smith_Lab05.zip)

Email




Use the following subject for your email: Lastname_LabX (e.g., Smith_Lab05). Send you code to l290w868@ku.edu if you are in one of Lei’s sections or, to

dhwanipandya1401@ku.edu if you are in one of Dhwani’s sections.




Anytime you have a question about the lab, put the word question in the subject of the email.