Search Binary Tree Implementation using Recursive an iterative Process
#include<iostream>//headerfile
using namespace std;//for std
#define size 20 //fix the size
struct Tree{
int data;
Tree *left;
Tree *right;
};
struct Stack{ //creation of stack
Tree *arr[size];
int top = -1;
bool isEmpty() //to check stack tat is this empty
{
return (top < 0);
}
bool isFull() //to check stack is this full
{
return (top == size - 1);
}
void push(Tree *v) //to push the adress inside the stack
{
if (isFull())
{
cout << "Value cannot Store" << endl;
}
else
{
arr[++top] = v;
}
}
Tree *pop() //to pop the address from stack
{
if (isEmpty())
{
cout << "There is nothing o display" << endl;
}
else
{
Tree *v = arr[top--];
return v;
}
}
Tree *peek() //to check the top adress
{
if (isEmpty())
{
cout << "There is nothing to show" << endl;
}
else
{
Tree *v = arr[top];
return v;
}
}
};
Tree *root = NULL; //root of tree
Tree *insertion(Tree *temp,int x)//insertion using iteration
{
Tree *newNode = new Tree;
newNode->data = x;
newNode->left = newNode->right = NULL;
if (temp == NULL)
{
temp = newNode;
cout << "Value is fitted" << endl;
}
else
{
Tree *temp2 = root;
while (temp2 != NULL){
if (temp2->data > x){
if (temp2->left == NULL)
{
temp2->left = newNode;
break;
}
temp2 = temp2->left;
}
else
{
if (temp2->right == NULL){
temp2->right = newNode;
break;
}
temp2 = temp2->right;
}
}
}
return temp;
}
Tree *InsertionRecursion(Tree *temp, int v) //insertion using recursion
{
if (temp == NULL)
{
Tree *newNode = new Tree;
newNode->data = v;
newNode->left = newNode->right = NULL;
temp = newNode;
}
else if (temp->data<v)
{
temp->left = InsertionRecursion(temp->left,v);
}
else if (temp->data >= v)
{
temp->right = InsertionRecursion(temp->right,v);
}
return temp;
}
void displayInorderRec(Tree *temp) //inorder display using recursion
{
if (temp != NULL){
displayInorderRec(temp->left);
cout << "Value in inorder is:" << temp->data << endl; system("pause");
displayInorderRec(temp->right);
}
}
void displayPostOrderRec(Tree *temp)//post order display using recursion
{
if (temp != NULL){
displayPostOrderRec(temp->left);
displayPostOrderRec(temp->right);
cout << "Value is:" << temp->data << endl; system("pause");
}
}
void displayPreOrderRec(Tree *temp)//pre order display using recursion
{
if (temp != NULL){
cout << "Value in PreOrder is:" << temp->data << endl; system("pause");
displayPreOrderRec(temp->left);
displayPreOrderRec(temp->right);
}
}
void displayInOrder(Tree *temp) //inorder display using iteration
{
Stack s1;
if (temp == NULL)
{
return;
}
else if (temp != NULL)
{
while (temp != NULL || s1.isEmpty() == false){
while (temp != NULL){
s1.push(temp);
temp = temp->left;
}
temp = s1.peek();
s1.pop();
cout << "Values of Display in Order is:" << temp->data << endl; system("pause");
temp = temp->right;
}
}
}
void displayPostOrder(Tree *temp)//post order display using iteration
{
Stack s1; Tree *temp2 = root; int count = 0;
if (temp == NULL)
{
return;
}
else if (temp != NULL)
{
while (temp != NULL || s1.isEmpty() == false){
while (temp != NULL)
{
s1.push(temp);
temp = temp->right;
}
temp = s1.peek();
s1.pop();
cout << "Values of Display in Order is:" << temp->data << endl; system("pause");
temp = temp->left;
}
}
}
void displayPreOrder(Tree *temp) //pre order display using iteration
{
Stack s1; Tree *temp2 = root;
if (temp == NULL)
{
return;
}
else if (temp != NULL)
{
while (temp != NULL || s1.isEmpty() == false){
while (temp != NULL){
s1.push(temp);
temp = temp->left;
}
while (temp != NULL)
{
s1.push(temp);
temp = temp->right;
}
temp = s1.peek();
s1.pop();
cout << "Values of Display in Order is:" << temp->data << endl;
system("pause");
temp = temp->right;
}
}
}
int main()
{
int m=0,p,q;
root = insertion(root, 5);
root = insertion(root, 6);
root = insertion(root, 7);
root = insertion(root, 8);
root = InsertionRecursion(root, 5);
root = InsertionRecursion(root, 7);
root = InsertionRecursion(root, 2);
while (m != 9){
system("cls");
cout << "Enter 1 to insert Node in Tree using Itration" << endl;
cout << "Enter 2 to insert Node in Tree using Recusrion" << endl;
cout << "Enter 3 to display InOrder using itration" << endl;
cout << "Enter 4 to display InOrder using Recusrion" << endl;
cout << "Enter 5 to display PostOrder using Itration" << endl;
cout << "Enter 6 to display PostOrder using Recursion" << endl;
cout << "Enter 7 to display PreOrder using Itration" << endl;
cout << "Enter 8 to display PreOrder using Recursion" << endl;
cout << "Enter 9 to Cancel Manu" << endl;
cin >> m;
switch (m){
case 1:
cout << "Enter the value to insert:"; cin >> p;
root = insertion(root, p);
break;
case 2:
cout << "Enter the value to insert:"; cin >> p;
root = InsertionRecursion(root, p);
break;
case 3:
displayInOrder(root);
break;
case 4:
displayInorderRec(root);
break;
case 5:
displayPostOrder(root);
break;
case 6:
displayPostOrderRec(root);
break;
case 7:
displayPreOrder(root);
break;
case 8:
displayPreOrderRec(root);
break;
default:
if (m == 9)
{
cout << "Thank You So Much For Our Services" << endl;
system("pause");
}
else
{
cout << "This Option is Not found" << endl;
cout << endl << "Please Enter again" << endl;
system("pause");
}
}
}
getchar();
getchar();
return 0;
}
Comments
Post a Comment