Binary Search tree Implementation of a BST class that include the following operations: - Insertion, Search, Deletion - Traversals: Inorder, Preorder, Postorder using c++
CODE
/*
* C++ Program To Implement BST
*/
# include <iostream>
# include <cstdlib>
using namespace std;
/*
* Node Declaration
*/
struct node
{
int info;
struct node *left;
struct node *right;
}*root;
/*
* Class Declaration
*/
class BST
{
public:
void find(int, node **, node **);
void insert(node *, node *);
void del(int);
void case_a(node *,node *);
void case_b(node *,node *);
void case_c(node *,node *);
void preorder(node *);
void inorder(node *);
void postorder(node *);
void display(node *, int);
BST()
{
root = NULL;
}
};
/*
* Main Contains Menu
*/
int main()
{
int choice, num;
BST bst;
node *temp;
while (1)
{
cout<<"-----------------"<<endl;
cout<<"Operations on BST"<<endl;
cout<<"-----------------"<<endl;
cout<<"1.Insert Element "<<endl;
cout<<"2.Delete Element "<<endl;
cout<<"3.Inorder Traversal"<<endl;
cout<<"4.Preorder Traversal"<<endl;
cout<<"5.Postorder Traversal"<<endl;
cout<<"6.Display"<<endl;
cout<<"7.Quit"<<endl;
cout<<"Enter your choice : ";
cin>>choice;
switch(choice)
{
case 1:
temp = new node;
cout<<"Enter the number to be inserted : ";
cin>>temp->info;
bst.insert(root, temp);
case 2:
if (root == NULL)
{
cout<<"Tree is empty, nothing to delete"<<endl;
continue;
}
cout<<"Enter the number to be deleted : ";
cin>>num;
bst.del(num);
break;
case 3:
cout<<"Inorder Traversal of BST:"<<endl;
bst.inorder(root);
cout<<endl;
break;
case 4:
cout<<"Preorder Traversal of BST:"<<endl;
bst.preorder(root);
cout<<endl;
break;
case 5:
cout<<"Postorder Traversal of BST:"<<endl;
bst.postorder(root);
cout<<endl;
break;
case 6:
cout<<"Display BST:"<<endl;
bst.display(root,1);
cout<<endl;
break;
case 7:
exit(1);
default:
cout<<"Wrong choice"<<endl;
}
}
}
/*
* Find Element in the Tree
*/
void BST::find(int item, node **par, node **loc)
{
node *ptr, *ptrsave;
if (root == NULL)
{
*loc = NULL;
*par = NULL;
return;
}
if (item == root->info)
{
*loc = root;
*par = NULL;
return;
}
if (item < root->info)
ptr = root->left;
else
ptr = root->right;
ptrsave = root;
while (ptr != NULL)
{
if (item == ptr->info)
{
*loc = ptr;
*par = ptrsave;
return;
}
ptrsave = ptr;
if (item < ptr->info)
ptr = ptr->left;
else
ptr = ptr->right;
}
*loc = NULL;
*par = ptrsave;
}
/*
* Inserting Element into the Tree
*/
void BST::insert(node *tree, node *newnode)
{
if (root == NULL)
{
root = new node;
root->info = newnode->info;
root->left = NULL;
root->right = NULL;
cout<<"Root Node is Added"<<endl;
return;
}
if (tree->info == newnode->info)
{
cout<<"Element already in the tree"<<endl;
return;
}
if (tree->info > newnode->info)
{
if (tree->left != NULL)
{
insert(tree->left, newnode);
}
else
{
tree->left = newnode;
(tree->left)->left = NULL;
(tree->left)->right = NULL;
cout<<"Node Added To Left"<<endl;
return;
}
}
else
{
if (tree->right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right"<<endl;
return;
}
}
}
/*
* Delete Element from the tree
*/
void BST::del(int item)
{
node *parent, *location;
if (root == NULL)
{
cout<<"Tree empty"<<endl;
return;
}
find(item, &parent, &location);
if (location == NULL)
{
cout<<"Item not present in tree"<<endl;
return;
}
if (location->left == NULL && location->right == NULL)
case_a(parent, location);
if (location->left != NULL && location->right == NULL)
case_b(parent, location);
if (location->left == NULL && location->right != NULL)
case_b(parent, location);
if (location->left != NULL && location->right != NULL)
case_c(parent, location);
free(location);
}
/*
* Case A
*/
void BST::case_a(node *par, node *loc )
{
if (par == NULL)
{
root = NULL;
}
else
{
if (loc == par->left)
par->left = NULL;
else
par->right = NULL;
}
}
/*
* Case B
*/
void BST::case_b(node *par, node *loc)
{
node *child;
if (loc->left != NULL)
child = loc->left;
else
child = loc->right;
if (par == NULL)
{
root = child;
}
else
{
if (loc == par->left)
par->left = child;
else
par->right = child;
}
}
/*
* Case C
*/
void BST::case_c(node *par, node *loc)
{
node *ptr, *ptrsave, *suc, *parsuc;
ptrsave = loc;
ptr = loc->right;
while (ptr->left != NULL)
{
ptrsave = ptr;
ptr = ptr->left;
}
suc = ptr;
parsuc = ptrsave;
if (suc->left == NULL && suc->right == NULL)
case_a(parsuc, suc);
else
case_b(parsuc, suc);
if (par == NULL)
{
root = suc;
}
else
{
if (loc == par->left)
par->left = suc;
else
par->right = suc;
}
suc->left = loc->left;
suc->right = loc->right;
}
/*
* Pre Order Traversal
*/
void BST::preorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
cout<<ptr->info<<" ";
preorder(ptr->left);
preorder(ptr->right);
}
}
/*
* In Order Traversal
*/
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
inorder(ptr->left);
cout<<ptr->info<<" ";
inorder(ptr->right);
}
}
/*
* Postorder Traversal
*/
void BST::postorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<<endl;
return;
}
if (ptr != NULL)
{
postorder(ptr->left);
postorder(ptr->right);
cout<<ptr->info<<" ";
}
}
/*
* Display Tree Structure
*/
void BST::display(node *ptr, int level)
{
int i;
if (ptr != NULL)
{
display(ptr->right, level+1);
cout<<endl;
if (ptr == root)
cout<<"Root->: ";
else
{
for (i = 0;i < level;i++)
cout<<" ";
}
cout<<ptr->info;
display(ptr->left, level+1);
}
}
OUTPUT $ g++ bst.cpp $ a.out ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 1 Enter the number to be inserted : 8 Root Node is Added ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 6 Display BST: Root->: 8 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 1 Enter the number to be inserted : 9 Node Added To Right ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 6 Display BST: 9 Root->: 8 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 1 Enter the number to be inserted : 5 Node Added To Left ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 6 Display BST: 9 Root->: 8 5 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 1 Enter the number to be inserted : 11 Node Added To Right ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 6 Display BST: 11 9 Root->: 8 5 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 1 Enter the number to be inserted : 3 Node Added To Left ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 1 Enter the number to be inserted : 7 Node Added To Right ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 6 Display BST: 11 9 Root->: 8 7 5 3 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 1 Enter the number to be inserted : 10 Node Added To Left ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 6 Display BST: 11 10 9 Root->: 8 7 5 3 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 2 Enter the number to be deleted : 10 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 6 Display BST: 11 9 Root->: 8 7 5 3 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 3 Inorder Traversal of BST: 3 5 7 8 9 11 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 4 Preorder Traversal of BST: 8 5 3 7 9 11 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 5 Postorder Traversal of BST: 3 7 5 11 9 8 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 2 Enter the number to be deleted : 8 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 6 Display BST: 11 Root->: 9 7 5 3 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 1 Enter the number to be inserted : 10 Node Added To Left ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 6 Display BST: 11 10 Root->: 9 7 5 3 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 1 Enter the number to be inserted : 15 Node Added To Right ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 6 Display BST: 15 11 10 Root->: 9 7 5 3 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 4 Preorder Traversal of BST: 9 5 3 7 11 10 15 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 5 Postorder Traversal of BST: 3 7 5 10 15 11 9 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 6 Display BST: 15 11 10 Root->: 9 7 5 3 ----------------- Operations on BST ----------------- 1.Insert Element 2.Delete Element 3.Inorder Traversal 4.Preorder Traversal 5.Postorder Traversal 6.Display 7.Quit Enter your choice : 7 ------------------ (program exited with code: 1) Press return to continue
Binary Search tree Implementation of a BST class that include the following operations: - Insertion, Search,...
Binary Search Trees (a) 5 pointsl Insert 5, 12, 7, 1, 6, 3, 13, 2, 10, 11 into an empty binary search tree in the given order. Show the resulting BST after every insertion. (b) 5 points) What are the preorder, inorder, and postorder traversals of the BST you have after (a)? (c) 5 points Delete 2, 7, 5, 6, 11 from the BST you have after (a) in the given order Show the resulting BST after every deletion.
LANGUAGE: C++ Write a class to create the binary tree (insert, delete, search, exit) and display the output using inorder, preorder and postorder tree traversal methods.
in python 11.1 Binary Search Tree In this assignment, you will implement a Binary Search Tree You will also need to implement a Node class. This class will not be tested, but is needed to implement the BST. Your BST must implement the following methods. You are free to implement additional helper methods. It is recommended you create your own helper methods Constructor: Creates an Empty Tree String Method: Returns the string "Empty Tree" for an empty tree. Otherwise, returns...
3. (8 points) Using the implementation of binary search tree operations we discussed in class, draw the trees that result from the following operations: (a) Inserting 142, 400, 205, 127, 100, 320, 160, 141, and 110 into an initially-empty tree (in that order). (b) Deleting 142 from the tree you drew for part (a). 4. (8 points) Draw the unique binary tree that has a preorder traversal of 4, 1, 6, 3, 7, 5, 9, 2, 8 and an inorder...
Consider the partial implementation of a Binary Search Tree (BST) class. For simplicity, each Node stores only the key. Add a public member function to class BST that returns the largest absolute value in the tree. The language is C++ Want the height #4 Coding [6 points] Consider the partial implementation of a Binary Search Tree (BST) class. For simplicity, each Node stores only the key. Add a public member function to class BST that returns the height of the...
1) Extend the Binary Search Tree ADT to include a public method leafCount that returns the number of leaf nodes in the tree. 2) Extend the Binary Search Tree ADT to include a public method singleParent-Count that returns the number of nodes in the tree that have only one child. 3) The Binary search tree ADT is extended to include a boolean method similarTrees that receives references to two binary trees and determines whether the shapes of the trees are...
Binary tree Given the following preorder and inorder traversals for an unknown binary tree, determine the exact tree that would generate these traversals and then draw that tree. Once you have generated the tree be sure to check your work. Inorder: {D, B, E, A, C, F, G, H, I} Preorder: {C, B, D, A, E, F, H, G, I}
Please I need help ASAP Java Programing: Binary Search Tree Fully implement the BST class in Listing 25.4 (on page 961 of the 11th Edition of the text). Design and write a (main) driver program to completely test every method in the BST class to ensure the class meets all its requirements. You should read the Listing 25.5: TestBST.java for an idea of what your program should look like. Listing 25.4 BST.java public class BST> extends AbstractTree { protected TreeNode...
PYTHON 3 CODING Review the following tree and then implement Depth First Traversals. Your program should display the output from Inorder to Preorder and Postorder. Include the following items in your answer: Write the implementation for Inorder, Preorder, and Postorder Print the output for each of the Inorder, Preorder, and Postorder Use the following steps to help with your solution: Create the node structure. Each node structure should contain the data, left node and right node. Create a function to...
Write a program in C fro Binary Search tree using following functions 1. Insertion operation using recursion 2. Deletion operation 3. Minimum/Maximum of a BST 6. Reorganize the tree so that the tree height is minimum 7. Print all the nodes from the node to the path to the root 8. Find the lowest common shared node between two given nodes