Implement a binary search tree (BST) with the following applications:
1. Insert: Insert a node into the BST.
2. Inorder: Print the BST in inorder traversal method.
Hint: The output should be a sorted list of numbers.
3. Delete: Delete a specific node from the tree.
4. Search: Search function needs to confirm whether the target is found.
Note: You should NOT use any related STL or sort function when implementing the BST.
Fill in the blanks marked "//TODO"
Template:
// C++ program to demonstrate insertion in a BST recursively.
#include <iostream>
using namespace std;
class BST
{
int key;
BST *left, *right;
public:
// Default constructor.
BST();
// Parameterized constructor.
BST(int);
// Insert function.
BST* Insert(BST*, int);
BST* deleteNode(BST*,int);
BST* minValueNode(BST*);
BST* searchValue(BST*,int);
// Inorder traversal.
void Inorder(BST*);
// Postorder traversal.
void Postorder(BST*);
//void Preorder(BST*);
};
// Default Constructor definition.
BST ::BST()
: key(0)
, left(NULL)
, right(NULL)
{
}
// Parameterized Constructor definition.
BST ::BST(int value)
{
key = value;
left = right = NULL;
}
// Insert function definition.
BST* BST ::Insert(BST* root, int key)
{
if (!root)
{
// Insert the first node, if root is NULL.
//TODO
}
// Insert data.
//TODO
}
// Inorder traversal function.
// This gives data in sorted order.
void BST ::Inorder(BST* root)
{
//TODO
}
//Postorder traversal function.
void BST ::Postorder(BST* root)
{
if (!root) {
return;
}
Postorder(root->left);
Postorder(root->right);
cout << root->key <<endl;
}
//minValueNode
BST* BST::minValueNode(BST* root){
BST* current = root;
while (current && current->left!=NULL)
current = current->left;
return current;
}
//deleteNode
BST* BST::deleteNode(BST* root,int key){
if (root == NULL)
return NULL;
//TODO
}
//searchValue
BST* BST::searchValue(BST* root,int key){
if (root == NULL)
return NULL;
//TODO
}
// Driver code
int main()
{
BST b, *root = NULL;
string cmd;
int count = 0;
while(cin >> cmd){
if(cmd == "Insert"){
int x;
cin >> x;
if (count == 0)
root = b.Insert(root,x);
else
b.Insert(root,x);
count+=1;
}else if(cmd == "Delete"){
int x;
cin >> x;
b.deleteNode(root,x);
count-=1;
}else if(cmd == "Inorder"){
b.Inorder(root);
}else if(cmd == "Search"){
int x;
cin >> x;
if(b.searchValue(root,x))
cout<<"found"<<endl;
else
cout<<"not found"<<endl;
}else if(cmd == "Postorder"){
b.Postorder(root);
}else if(cmd == "exit"){
return 0;
}
}
return 0;
}
// This code is contributed by pkthapa
// This code is contributed by shivanisinghss2110
Hint:
1.Assume that all input parameters would be valid. (Will not input “Delete” “Inorder” “Postorder” “Search” when the tree is empty)
2.Will not insert an existing key value (key value will not be repeated)
3.In the Inorder function, a new line is required for each element printed.(The output format can refer to the Postorder function)
4.When the search function is called, if the input key value is found, “found” will be printed, if not, “not found” will be printed.
There are multiple lines in the input.
According to the different instructions, operating the different tasks.
Input format:
Insert x:Insert the key value x into the binary search tree
Delete x:Delete the key value x from the binary search tree
Inorder:Print the inorder traversal result of the binary search tree (the sorted order of the key value in the binary search tree)
Search x:Check if x is in the binary search tree. If there is, then output “found”. If not, output “not found”.
Postorder: Print the postorder traversal result of the binary search tree
1.Inorder command will output the inorder traversal result of the binary search tree
2.Search command will output “found” or “not found”
3.Postorder command will output the postorder traversal result of the binary search tree