Binary Search Tree

program to store prefix expression in BST and display infix,postfix us

Page 1 of 1

0 Replies - 746 Views - Last Post: 10 March 2009 - 12:51 AM Rate Topic: -----

#1 #Chaitanya  Icon User is offline

  • New D.I.C Head

Reputation: 0
  • View blog
  • Posts: 5
  • Joined: 07-March 09

Binary Search Tree

Post icon  Posted 10 March 2009 - 12:51 AM

Let me know if any improvement can be done in this program.

Language used : C
Compiler Used : Turbo C++

#include<stdio.h>
#include<conio.h>
#include<alloc.h>
#define max 20
struct node
{
	char info;
	struct node *left,*right;
}*root = NULL,*ptr;
struct stack
{
	struct node *a[max];
	int top;
};
void push(struct stack *s,struct node *item)
{
	if(s->top == max - 1)
		printf("\nOVERFLOW ERROR : STACK IS FULL");
	else
		s->a[++s->top] = item;
}
struct node* pop(struct stack *s)
{
	if(s->top == -1)
	  return NULL;
	else
	  return s->a[s->top--];

}
int gettype(char op)
{
	 switch(op)
	 {
	 case '+':
	 case '-':
	 case '/':
	 case '*':
		return 1;
	 default:
		return 0;
	 }
}
void create()
{
	  /*  DECLARATION */
	  struct stack *s;
	  struct node *n;
	  char pre[max];
	  int l,i;
	  /* INITIALIZATION */
	  s->top = -1;
	  printf("\n\nEnter Prefix Expression : ");
	  scanf("%s",pre);
	  if(gettype(pre[0]) == 0) // Prefix expression always starts with operator.
	  {
	 printf("\nIllegal Expression. Cannot create tree");
	 return;
	  }
	  root = (struct node*)malloc(sizeof(struct node));
	  root->info = pre[0];
	  l = strlen(pre);
	  root->left = NULL;
	  root->right = NULL;
	  ptr = root;

	  /* CREATION */
	  for(i = 1; i < l; i++)
	  {
	  n = (struct node*)malloc(sizeof(struct node));
	  n->info = pre[i];
	  if(gettype(ptr->info) == 1)
	  {
		 push(s,ptr);
		 ptr->left = n;
	  }
	  else
	  {
		 ptr = pop(s);
		 ptr->right = n;
	  }
	  ptr = n;
	  ptr->left = NULL;
	  ptr->right = NULL;
	  }
}
void pre(struct node *curr)
{
	printf("%c",curr->info);
	if(curr->left != NULL)
	   pre(curr->left);
	if(curr->right != NULL)
	   pre(curr->right);
}
void post(struct node *curr)
{
   if(curr->left != NULL)
	   post(curr->left);
   if(curr->right != NULL)
	   post(curr->right);
   printf("%c",curr->info);
}
void inord(struct node* curr)
{
	if(curr->left != NULL)
	   inord(curr->left);
	printf("%c",curr->info);
	if(curr->right != NULL)
	   inord(curr->right);
}
void erase(struct node* curr)
{
	if(curr->left != NULL)
	  erase(curr->left);
	if(curr->right != NULL)
	  erase(curr->right);
	free(curr);
}
void main()
{
   char ch,t_ch;
   do
   {
	 clrscr();
	 printf("1. Create Tree\n2. Traverse\n3. Erase tree\n4. Exit\nEnter Your Choice : ");
	 ch = getche();
	 switch(ch)
	 {
	   case '1':
	  if(root == NULL)
		 create();
	  else
		 printf("\n\nTree already created. To create new tree, erase the existing one.");
	  printf("\n\nPress any key to continue.");
	  getch();
	  break;
	   case '2':
	  if(root == NULL)
	  {
		 printf("\n\nTree does not exist.\n\nPress any key to continue.");
		 getch();
		 break;
	  }
	  printf("\n\n1.In Order\n2.Post Order\n3.Pre Order\nEnter your choice : ");
	  t_ch = getche();
	  switch(t_ch)
	  {
		  case '1':
		  printf("\n\n\nInfix Expression :  ");
		  inord(root);
		  break;
		  case '2':
		  printf("\n\nPostfix Expression :  ");
		  post(root);
		  break;
		  case '3':
		  printf("\n\nPrefix Expression :  ");
		  pre(root);
		  break;
		  default:
		  printf("\n\nWrong Choice");
	  }
	  printf("\n\nPress any key to continue.");
	  getch();
	  break;
	   case '3':
	  if(root == NULL)
	  {
		  printf("\n\nTree does not exist.\nPress any key to continue");
		  getch();
		  break;
	  }
	  erase(root);
	  root = NULL;
	  printf("\n\nTree erased.");
	  printf("\n\nPress any key to continue.");
	  getch();
	  break;
	 }
   }while(ch != '4');
}



Is This A Good Question/Topic? 0
  • +

Page 1 of 1