//Implement program for Binary Search Tree and Non-Recursive Traversals.
#include<stdio.h>
#include<stdlib.h>
#define max 30
struct btree
{
int data;
int flag;
struct btree *lchild,*rchild;
};
struct stack
{
struct btree *stk[max];
int top;
};
typedef struct stack stack;
typedef struct btree NODE;
NODE *create(NODE *);
NODE *getnode();
void inorder(NODE *);
void preorder(NODE *);
void postorder(NODE *);
int main()
{
NODE *root;
int choice,digit,n,i;
char ch;
root=NULL;
do
{
printf("\n\n\t\tMENU");
printf("\n\t1. Insert Node");
printf("\n\t2. Inorder");
printf("\n\t3. Preorder");
printf("\n\t4. Postorder");
printf("\n\t0. Exit");
printf("\nEnter your choice");
scanf("%d",&choice);
switch(choice)
{
case 1:
root=create(root);
break;
case 2:
printf("\nInorder Traversing Tree\n\n");
inorder(root);
break;
case 3:
printf("\nPreorder Traversing Tree\n\n");
preorder(root);
break;
case 4:
printf("\nPreorder Traversing Tree\n\n");
postorder(root);
break;
case 0:
exit(0);
break;
default:
printf("\nWrong Choice \n");
break;
}
printf("\nDo you want to continue (y/n)?");
scanf("%s",&ch);
}while(ch=='y'||ch=='Y');
return(0);
}
void push(stack *s, NODE *t)
{
s->top=s->top+1;
s->stk[s->top]=t;
}
NODE *pop(stack *s)
{
NODE *t;
t=s->stk[s->top];
s->top=s->top-1;
return(t);
}
int empty(stack *s)
{
if(s->top==0)
return(1);
else
return(0);
}
NODE *getnode()
{
NODE *temp;
temp=(NODE*)malloc(sizeof(NODE));
printf("\nEnter Data : ");
scanf("%d",&temp->data);
temp->rchild=NULL;
temp->lchild=NULL;
return(temp);
}
NODE *create(NODE *root)
{
NODE *temp,*ptr;
char ch;
do
{
temp=getnode();
if(root==NULL)
root=temp;
else
{
ptr=root;
while(ptr!=NULL)
{
if(ptr->data>temp->data)
{
if(ptr->lchild!=NULL)
ptr=ptr->lchild;
else
{
ptr->lchild=temp;
break;
}
}
else
{
if(ptr->rchild!=NULL)
ptr=ptr->rchild;
else
{
ptr->rchild=temp;
break;
}
}
}
}
printf("\nAdd more(y/n): ");
scanf("%s",&ch);
}while(ch=='y'||ch=='Y');
return(root);
}
void inorder(NODE *root)
{
NODE *ptr;
stack stack;
stack.top=NULL;
ptr=root;
do
{
while(ptr!=NULL)
{
push(&stack,ptr);
ptr=ptr->lchild;
}
ptr=pop(&stack);
printf("%d\t",ptr->data);
ptr=ptr->rchild;
}while(!empty(&stack)||ptr!=NULL);
}
void preorder(NODE *root)
{
NODE *ptr;
stack stack;
stack.top=NULL;
ptr=root;
do
{
while(ptr!=NULL)
{
printf("%d\t",ptr->data);
if(ptr->rchild!=NULL)
push(&stack,ptr->rchild);
ptr=ptr->lchild;
}
if(!empty(&stack))
ptr=pop(&stack);
}while(!empty(&stack)||ptr!=NULL);
}
void postorder(NODE *root)
{
NODE *ptr;
stack stack;
stack.top=NULL;
ptr=root;
do
{
while(ptr!=NULL)
{
push(&stack,ptr);
ptr=ptr->lchild;
}
ptr=pop(&stack);
if(ptr->flag==1)
{
printf("%d\t",ptr->data);
ptr=NULL;
}
else
{
ptr->flag=1;
push(&stack,ptr);
ptr=ptr->rchild;
}
}while(!empty(&stack)||ptr!=NULL);
}
