Binary search tree implementation c++

This C++ Program demonstrates operations on Binary Search Tree
Here is source code of the C++ Program to demonstrate Binary Tree. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

/*
* C++ Program To Implement BST
*/
# include
# include
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<<"-----------------"<>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"<>num;
bst.del(num);
break;
case 3:
cout<<"Inorder Traversal of BST:"<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"<info == newnode->info)
{
cout<<"Element already in the 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"<right != NULL)
{
insert(tree->right, newnode);
}
else
{
tree->right = newnode;
(tree->right)->left = NULL;
(tree->right)->right = NULL;
cout<<"Node Added To Right"<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"<info<<" "; preorder(ptr->left);
preorder(ptr->right);
}
}
/*
* In Order Traversal
*/
void BST::inorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<left);
cout<info<<" "; inorder(ptr->right);
}
}

/*
* Postorder Traversal
*/
void BST::postorder(node *ptr)
{
if (root == NULL)
{
cout<<"Tree is empty"<left);
postorder(ptr->right);
cout<info<<" "; } } /* * Display Tree Structure */ void BST::display(node *ptr, int level) { int i; if (ptr != NULL) { display(ptr->right, level+1);
cout<: “;
else
{
for (i = 0;i < level;i++) cout<<" "; } cout<info;
display(ptr->left, level+1);
}
}
$ 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
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:

——————
(program exited with code: 1)
Press return to continue

Top Stories

What idea is emphasized through repetition

The a value of a function in the form f(x) = ax2 + bx + c is negative. which statement must be true?

What experimental evidence led to the development of this atomic model from the one before it?

Stay Connected

Binary search tree implementation c++

Search

Quick Links

About US