Implement a Binary Search Tree (BST) in C++. The implementation should include the tree structure construction and commo
Posted: Thu Jul 14, 2022 2:18 pm
Implement a Binary Search Tree (BST) in C++. The implementationshould include the tree structure construction and commonoperations such as inserting, removing, and searching for anelement. Skeleton codes provided in the class can be incorporatedinto the implementation.
This is a binary tree after the user enters several elements. Ifthe user enters those numbers in blue in the following order: 44,17, 88, 32, 28, 65, 82, 76, … the tree’s structure will be likethis. Now, your program should allow the user to enter elements ofrandom numbers. These numbers will be stored in such a BinarySearch Tree. The Binary Search Tree stored in the memory "knows"the structure, though you do not plot the tree in the terminal.
Next, if the user wants to search for an element, for example,82, this Binary Search Tree will give the user a path that canreach that number, which is 44->88->65->82, therebycompleting the search operation. If the element that the user wantsto find does not exist, the Binary Search Tree will indicate thatsuch a number does not exist.
You will design the program in the following way. First, theprogram prompts the user to enter some numbers line-by-line (shownin red). When the user enters -1 (as a sentinel value), the programwill stop accepting user’s input and thus finish the tree buildingprocess. Next, the program asks the user to enter a value forsearching. After the user enters a value that exists in this tree,the program will output the path as how it uses the Binary SearchTree structure to find that number. The program should output anerror message or a symbol at the end of the path if such an enterednumber is not found (i.e. the tree is reaching to an external nodebut the entered value is not in the tree). When the user enters -1,the program will exit. Take a look at the following example. Redtexts are user’s inputs.
Enter numbers, one line for each:
44
17
88
32
28
65
82
76
-1
Enter a number you want to search for: 44
44, number is found
Enter a number you want to search for: 28
44, 17, 32, 28, number is found.
Enter a number you want to search for:
29
44, 17, 32, 28, X number is not found.
Enter a number you want to search for:
-1
Goodbye!
To simplify the assignment, we assume that the user input willbe all positive integers. At least one number will be entered, sothat the tree has at least a root. These integers are all unique(i.e. no duplicated number).
For this assignment, we mainly focus on and test the ability of inserting and searching for an element, although the removal of an element is also necessary operation in general. Consider a Binary Search Tree below.
- Implement A Binary Search Tree Bst In C The Implementation Should Include The Tree Structure Construction And Commo 1 (376.44 KiB) Viewed 33 times
Next, if the user wants to search for an element, for example,82, this Binary Search Tree will give the user a path that canreach that number, which is 44->88->65->82, therebycompleting the search operation. If the element that the user wantsto find does not exist, the Binary Search Tree will indicate thatsuch a number does not exist.
You will design the program in the following way. First, theprogram prompts the user to enter some numbers line-by-line (shownin red). When the user enters -1 (as a sentinel value), the programwill stop accepting user’s input and thus finish the tree buildingprocess. Next, the program asks the user to enter a value forsearching. After the user enters a value that exists in this tree,the program will output the path as how it uses the Binary SearchTree structure to find that number. The program should output anerror message or a symbol at the end of the path if such an enterednumber is not found (i.e. the tree is reaching to an external nodebut the entered value is not in the tree). When the user enters -1,the program will exit. Take a look at the following example. Redtexts are user’s inputs.
Enter numbers, one line for each:
44
17
88
32
28
65
82
76
-1
Enter a number you want to search for: 44
44, number is found
Enter a number you want to search for: 28
44, 17, 32, 28, number is found.
Enter a number you want to search for:
29
44, 17, 32, 28, X number is not found.
Enter a number you want to search for:
-1
Goodbye!
To simplify the assignment, we assume that the user input willbe all positive integers. At least one number will be entered, sothat the tree has at least a root. These integers are all unique(i.e. no duplicated number).
For this assignment, we mainly focus on and test the ability of inserting and searching for an element, although the removal of an element is also necessary operation in general. Consider a Binary Search Tree below.