Tree Operations

#include<iostream.h>

#include<conio.h>
#include<stdlib.h>

class Node{

public:
Node* left;
Node* right;

int data;

};


Node* root = NULL;

Node* createTree( int *data,int start,int end)
{

if(end<start)
return NULL;
int mid=(start+end)/2;

cout<<" MID Value is : "<< mid <<"value :    "<<data[mid]<<endl;

Node *node = new Node;
node->data = data[mid];

cout<<"Adding to left"<<start<<"    "<<mid-1<< endl;
node->left = createTree(data,start, mid-1);


cout<<"Adding to right....."<<mid+1<<"     "<<end<<endl;
node->right = createTree(data,mid+1,end);


return node;
}

void inOrder(Node *root)
{
if(root == NULL)
return;

inOrder(root->left);
cout<<root->data<<endl;
inOrder(root->right);
}

void preOrder(Node *root)
{
if(root == NULL)
return;
cout<<root->data<<endl;
inOrder(root->left);
inOrder(root->right);
}
void postOrder(Node *root)
{
if(root == NULL)
return;

inOrder(root->left);
inOrder(root->right);
cout<<root->data<<endl;
}

class queue{
Node* data[10];
int front,back;
public:
queue()
{
front=-1;
back =-1;


memset(data,NULL,sizeof(data));

}
void push(Node* a)
{
++back;
data[back] = a;
// cout<<"inserting at "<<back<<"   value   :"<<a->data<<endl;

}
Node* pop()
{
// if(data[pos]=='\0')
// return NULL;
       // cout<<" returning ...."<<front+1<<endl;
Node* t =  data[++front];

// cout<<" returning at post is  "<<front<<" value "<<t->data<<endl;


return t;
}
bool empty()
{
if(front==back)
return true;
return false;
}
};

void BFS(Node* root)
{
queue *q = new queue();

q->push(root);

int level =0 ;
     int bvalue = 1;
while(!q->empty())
{
Node* node= q->pop();
cout<<node->data;
level++;
        if(level == bvalue)
{
level=0;
cout<<endl;
bvalue = bvalue*2;
}


if(node->left!=NULL)
q->push(node->left);

if(node->right!=NULL)
q->push(node->right);
}

}

class stack{
int top;
Node* data[10];
public:
stack()
{
top=-1;
memset(data,NULL,sizeof(data));
}

void push(Node* a)
{
data[++top] = a;
   // cout<<"pushed at  :"<<top<<"    "<< a->data<<endl;
}

Node* pop()
{
// cout<<"pop of data from "<< top-1<<endl;

return data[top--];
}

bool empty()
{
if(top==-1)
return true;
return false;
}
};


void DFS(Node* root)
{

stack st;
 
st.push(root);
while(!st.empty())
{
Node *t = st.pop();
        cout<<t->data<<endl;

if(t->right!=NULL)
st.push(t->right);

if(t->left!=NULL)
st.push(t->left);
}

}

int main()
{

int a[]={1,2,3,4,5,6,7,8,9,10,'/0'};

root = createTree(a,0,9);
cout<<" In Order ....."<<endl;

inOrder(root);

cout<<" Pre Order ....."<<endl;

preOrder(root);


cout<<" Post Order ....."<<endl;

postOrder(root);

cout<<"BFS of the tree...."<<endl;
BFS(root);

cout<<"DFS of the tree...."<<endl;
DFS(root);


return 0;
}