Binary Tree(BT)

Algorithm:Binary Tree(BT)

Let us consider a binary tree represented in linked format and 
the root of the tree is named as ‘root’.
Now we will go through some general operations’ algorithms on that tree.

1.Preorder traversal

preorder(root)
{
if(root≠NULL)
	{
	print(root->data)
	printeorder(root->lchild)
	printeorder(root->rchild)
	}
}

2.Postorder traversal

postorder(root)
{
if(root≠NULL)
	{
	postorder(root->lchild)
	postorder(root->rchild)
	print(root->data)
	}
}


3.Inorder traversal 

inorder(root)
{
if(root≠NULL)
	{
	inorder(root->lchild)
	print(root->data)
	inorder(root->rchild)
	}
}

4.Searching a specific element named as ‘key’ in the binary tree

search(root,key)
{

if(root=NULL)
	return NULL
else if(root->data=key)      //if found
	return root
else
	{                                   //if not found in the left subtree then
                                               searching the right subtree.
	r=search(root->lchild,key)
	if(r=NULL)
		r=search(root->rchild,key)
	return r
	}

}

 
5.Inserting a node as a leaf node in the binary tree 

where ‘key’ is the value after which the new value ‘item’ is to be inserted.

insertleaf(root,item,key)
{

t=getnode()
t->data=item

ptr=search(root,key)
if(ptr=NULL)
	print(“Key value doesn’t exist at all..! :(")
else
	{
	if(ptr->lchild=NULL or ptr->rchild=NULL)
		{
		read option                       //taking input whether the new
                                                    item will be left child
                                                    or right child of key
		if(opt=left)
			{
			if(ptr->lchild=NULL)
				{
				ptr->lchild=t
				print("Successfully inserted.. :)")
				}
			else
				print("Left child isn't available..")

			}
		else if(opt=right)
			{
			if(ptr->rchild=NULL)
				{
				ptr->rchild=t
				print("Successfully inserted.. :)") 
				}
			else
				print("Right child isn't available..")

			}
		}
	else                                       //if the key node already
                                                       has two children.
		print("Not available..")
	}

}


6.Searching

The parent node of an element ‘key’ in the tree

parent(root,key)
{
if(root=NULL)
	par=NULL
else
	{
	ptr=root
	p1=ptr->lchild
	p2=ptr->rchild

	if(p1=NULL and p2=NULL)
		par=NULL
	if(p1≠NULL)
		{
		if(p1->data=key)                                       //if found
			par=ptr
		else
			par=parent(p1,key)
		}
	if(par=NULL and p2≠NULL)                             //if not found in the left subtree 
                                                              then searching the right subtree.
		{
		if(p2->data=key)
			par=ptr
		else
			par=parent(p2,key)
		}

	}
return par
}


7.Deleting a leaf node from the binary tree with the help of the previous algorithm
of finding parent and searching. 

Here the ‘root’ is treated as ‘r’.

deleteleaf(r,key)
{
par=parent(r,key)
 
if(par=NULL)
	print("Deletion not possible..")
else
	{
	ptr=search(r,key)
	if(ptr->lchild=NULL and ptr->rchild=NULL)            //if found checking whether
                                                                 it is a leaf node or not.
		{
		if(par->lchild=ptr)
			par->lchild=NULL
		else if(par->rchild=ptr)
			par->rchild=NULL

		print("Successfully deleted..")

		}
	else
		print("Sorry, its not a leaf node..")
	}

}


8.Counting the no. of nodes in a tree.

 count(root)
{
if(root=NULL)
	return 0
else
	return (count(root->lchild)+count(root->rchild)+1)
}



9.Calculating the height of a binary tree

height(root)
{

if(root=NULL)
	return 0
else
	{
	h1=height(root->lchild)
	h2=height(root->rchild)
	if(h1>h2)
		return h1+1
	else
		return h2+1
	}

}

10.Preorder and Inorder traversal using stack.

Here we will use the two most important algorithms used in stack named pop() and push().

preorders(root)
{

push(root)                                 //here ‘top’ denotes the top of
                                             the stack named ‘S’
                                             where push,s pop operation is done.

while(top≠-1)
	{
	ptr=pop()
	print(ptr->data)
	if(ptr->rchild≠NULL)
		push(ptr->rchild)
	if(ptr->lchild≠NULL)
		push(ptr->lchild)
	}
}

inorders(root)
{
ptr=root
while(ptr≠NULL or top≠-1)
	{
	if(ptr≠NULL)
		{
		push(ptr) 
		ptr=ptr->lchild
		}
	else
		{
		ptr=pop()
		print(ptr->data)
		ptr=ptr->rchild
		}
	}
}

In this set of algorithms, we have often used a algorithm 
called getnode().
This algorithm allocates a node structure in the memory and returns its address to the variable.

  

C Program For Binary Tree(BT)

Source Code:

#include<stdio.h>
#include<stdlib.h>
#include<string.h>

struct tree
{
 char data;
 struct tree *lchild;
 struct tree *rchild;
};

struct tree * s[30];
int top=-1,tp=-1;
char a[20];

struct tree * gettree()
{
 struct tree *t;
 t=(struct tree *)malloc(sizeof(struct tree));
 t->lchild=NULL;
 t->rchild=NULL;
 return t;
}

void push(struct tree *item)
{

  top=top+1;
  s[top]=item;
}

struct tree * pop()
{
  struct tree *item;
  item=s[top];
  top=top-1;
 return item;
}

void pre_order(struct tree *root)
{
   struct tree *ptr;
	push(root);
	while(top!=-1)
	{
	   ptr=pop();
	   printf("  %c",ptr->data);
	   if(ptr->rchild!=NULL)
	       push(ptr->rchild);
	   else if(ptr->lchild!=NULL)
	       push(ptr->lchild);
	}
}

void in_order(struct tree *root)
{
    struct tree *ptr;
    ptr=root;
    while(ptr!=NULL || top!=-1)
    {
       if(ptr!=NULL)
       {
	  push(ptr);
	  ptr=ptr->lchild;
       }
       else
       {
	  ptr=pop();
	  printf("  %c",ptr->data);
	  ptr=ptr->rchild;
       }
    }
}

struct tree * search(struct tree *root,char key)
{
  struct tree *r;
	if(root==NULL)
		return NULL;
	else
	{
		if(root->data==key)
			return root;
		else
		{
			r=search(root->lchild,key);
			if(r==NULL)
			{
				r=search(root->rchild,key);
			}
			return r;
		}
       }
}

int count(struct tree *root)
{
   if(root==NULL)
      return 0;
   else
      return count(root->lchild)+count(root->rchild)+1;
}

void insertion(struct tree *root,char key,char item,int opt)
{
   struct tree *t,*ptr;
   t=gettree();
   t->data=item;
   if(root->data=='$')
      root->data=t->data;
   else
   {
      ptr=search(root,key);
      if(ptr==NULL)
	 printf("\nKey does not exists.");
      else
      {
	 if(ptr->lchild==NULL || ptr->rchild==NULL)
	 {
	    if(opt==1)
	    {
	       if(ptr->lchild==NULL)
		  ptr->lchild=t;
	       else
		  printf("\nLeft child not empty.");
	    }
	    else if(opt==2)
	    {
	       if(ptr->rchild==NULL)
		  ptr->rchild=t;
	       else
		  printf("\nRight child not empty.");
	    }
	 }
	 else
	    printf("\nPosition not available.");
      }
   }
}

struct tree * parent(struct tree *root,char key)
{
	struct tree *par,*ptr,*p1,*p2;
	if(root==NULL)
	   par=NULL;
	else
	{
	   ptr=root;
	   p1=ptr->lchild;
	   p2=ptr->rchild;
	   if(p1==NULL && p2==NULL)
	      par=NULL;
	   if(p1!=NULL)
	   {
	      if(p1->data==key)
		 par=ptr;
	      else
		 par=parent(p1,key);
	   }
	   if(par==NULL && p2!=NULL)
	   {
	      if(p2->data==key)
		 par=ptr;
	      else
		 par=parent(p2,key);
	   }
	}
	return par;
}

void deleteleaf(struct tree *root,char key)
{
	struct tree *par,*ptr;
	par=parent(root,key);
	if(height(root)==1)
	{
	   root->data='$';
	}
	else if(par==NULL)
	   printf("\nDeletion not possible.");
	else
	{
	   ptr=search(root,key);
	   if(ptr->lchild==NULL && ptr->rchild==NULL)
	   {
	      if(par->lchild==ptr)
		 par->lchild=NULL;
	      else if(par->rchild==ptr)
		 par->rchild=NULL;
	   }
	   else
	      printf("\nNot a leaf node of the tree.");
	}
}

void inorder(struct tree *root)
{
   if(root->data=='$')
      printf("\nTree not created");
   else
   {
      if(root!=NULL)
      {
	 inorder(root->lchild);
	 printf("  %c",root->data);
	 inorder(root->rchild);
      }
   }
}

void preorder(struct tree *root)
{
   if(root->data=='$')
      printf("\nTree not created");
   else
   {
      if(root!=NULL)
      {
	 printf("  %c",root->data);
	 preorder(root->lchild);
	 preorder(root->rchild);
      }
   }
}

void postorder(struct tree *root)
{
   if(root->data=='$')
      printf("\nTree not created");
   else
   {
      if(root!=NULL)
      {
	 postorder(root->lchild);
	 postorder(root->rchild);
	 printf("  %c",root->data);
      }
   }
}

int height(struct tree *root)
{
	if(root==NULL)
	   return 0;
	else
	{
	   if(height(root->lchild)>height(root->rchild))
	      return height(root->lchild)+1;
	   else
	      return height(root->rchild)+1;
	}
}

int nodenum(struct tree *root,int opt)
{
   if(opt==1)
   {
      if(root==NULL)
	 return 0;
      else
	 return count(root->lchild)+1;
   }
   if(opt==2)
   {
      if(root==NULL)
	 return 0;
      else
	 return count(root->rchild)+1;
   }
}

int isop(char y)
{
  switch(y)
   {
     case '+':
     case '-':
     case '*':
     case '/':
     case '%':
     case '^':
	      return 1;
	      break;
     case '{':
     case '[':
     case '(':
     case ')':
     case '}':
     case ']':
	      return 2;
	      break;
     default:
	     return 0;
	     break;
   }
}

int pre(char op)
{
  switch(op)
   {
     case '+':
     case '-':
	      return 1;
	      break;
     case '*':
     case '/':
     case '%':
	      return 2;
	      break;
     case '^':
	      return 3;
	      break;
     default:
	     return 0;
	     break;
   }
}

float operation(float b,float a,char z)
{
  switch(z)
   {
     case '+':
	      return b+a;
	      break;
     case '-':
	      return b-a;
	      break;
     case '*':
	      return b*a;
	      break;
     case '/':
	      return (b/a);
	      break;
     case '%':
	      return ((int )b%(int )a);
	      break;
     case '^':
	      return pow(b,a);
	      break;
    }
}

void pu_sh(char item)
{

 if(tp==9)
   {
     printf("\nStack overflow");
   }
 else
   {
     tp=tp+1;
     a[tp]=item;
   }
}

char p_op()
{
  char item;
  if(tp==-1)
   {
     printf("\nStack Underflow");

   }
  else
   {
     item=a[tp];
     tp=tp-1;
   }
  return item;
}

void itop(char e[15],char p[15])
{
  int j,k=0,l,i,g;
  char x,y,m,sym;

  printf("\nEnter an infix expression: ");
  fflush(stdin);
  gets(e);
  l=strlen(e);
  strcat(e,")");
  m='(';
  pu_sh(m);
  i=0;
  while(tp!=-1)
   {
      x=e[i];
      if(isop(x)==0)
       {
	 p[k]=x;
	 k=k+1;
       }

      else if(x=='(')
       {
	 pu_sh(x);
       }

      else if(x==')')
       {
	 y=p_op();
	 while(y!='(')
	  {
	    p[k]=y;
	    k=k+1;
	    y=p_op();
	  }
       }

      else if(isop(x)==1)
       {
	 y=p_op();
	 while(isop(y)==1 && pre(y)>=pre(x))
	  {
	    p[k]=y;
	    k=k+1;
	    y=p_op();
	  }
	 pu_sh(y);
	 pu_sh(x);
       }
     i++;
   }
  p[k]='\0';
}

struct tree * crextree()
{
  struct tree *p1,*p2,*t,*r;
  char sym,e[15],p[15];
  int g;
  itop(e,p);
  strcat(p,"#");
  g=0;
  sym=p[g];
  while(sym!='#')
  {
     if(isop(sym)==0)
     {
	t=gettree();
	t->data=sym;
	push(t);
     }
     else if(isop(sym)==1)
     {
	p1=pop();
	p2=pop();
	t=gettree();
	t->data=sym;
	t->lchild=p2;
	t->rchild=p1;
	push(t);
     }
     g++;
     sym=p[g];
  }
  r=pop();
  return r;
}

float evaluate(struct tree *root)
{
    struct tree *ptr,*lptr,*rptr;
    char op;
    float v1,v2;
    ptr=root;
    if(ptr!=NULL)
    {
       lptr=ptr->lchild;
       rptr=ptr->rchild;
       if(isop(lptr->data)==0)
	  v1=(float)(lptr->data)-'0';
       else
	  v1=evaluate(lptr);
       if(isop(rptr->data)==0)
	  v2=(float)(rptr->data)-'0';
       else
	  v2=evaluate(rptr);
       op=ptr->data;
       return operation(v1,v2,op);
    }
}

void main()
{
 int ch,h,c,opt,h1,h2,c1,c2;
 char key,item;
 float v;
 struct tree *root,*s,*rt;
 root=gettree();
 root->data='$';
 while(1)
 {
	printf("\n\nBinary tree Operations:");
	printf("\n\t1.Insertion\n\t2.Deletion\n\t3.Traversal\n\t4.Search");
	printf("\n\t5.Height\n\t6.Count node of the tree");
	printf("\n\t7.Each subtree node number\n\t8.Decide which branch is heavier");
	printf("\n\t9.Create expression tree\n\t10.Evaluate expression tree\n\t11.Exit");
	printf("\n\nEnter your choice:");
	scanf("%d",&ch);
	switch(ch)
	{
	    case 1: printf("\nEnter key:");
		    fflush(stdin);
		    scanf("%c",&key);
		    printf("\nEnter data:");
		    fflush(stdin);
		    scanf("%c",&item);
		    printf("\nEnter as a 1.left-child  2.right-child");
		    printf("\nEnter your choice:");
		    fflush(stdin);
		    scanf("%d",&ch);
		    switch(ch)
		    {
		       case 1: opt=1;
			       insertion(root,key,item,opt);
			       break;
		       case 2: opt=2;
			       insertion(root,key,item,opt);
			       break;
		    }
		    break;
	    case 2: if(root->data=='$')
			printf("\nTree not created.");
		    else
		    {
			printf("\nEnter the Key:");
			fflush(stdin);
			scanf("%c",&key);
			deleteleaf(root,key);
		    }
		    break;
	    case 3: printf("\n\n\t1.Inorder\n\t2.Preorder\n\t3.Postorder");
		    printf("\nEnter Your choice:");
		    scanf("%d",&ch);
		    switch(ch)
		    {
		       case 1: printf("\nInorder traversal:\n");
			       inorder(root);
			       break;
		       case 2: printf("\nPreorder traversal:\n");
			       preorder(root);
			       break;
		       case 3: printf("\nPostorder traversal:\n");
			       postorder(root);
			       break;
		    }
		    break;
	    case 4: if(root->data=='$')
		       printf("\nTree not created.");
		    else
		    {
		       printf("\nEnter the key:");
		       fflush(stdin);
		       scanf("%c",&key);
		       s=search(root,key);
		       if(s!=NULL)
			  printf("\nKey found");
		       else
			  printf("\nKey not found.");
		    }
		    break;
	    case 5: if(root->data=='$')
		       printf("\nTree not created.");
		    else
		    {
		       h=height(root);
		       printf("\nHeight of the binary tree=%d",h);
		    }
		    break;
	    case 6: if(root->data=='$')
		       printf("\nTree not created.");
		    else
		    {
		       c=count(root);
		       printf("\nTotal node of the binary tree=%d",c);
		    }
		    break;
	    case 7: if(root->data=='$')
		       printf("\nTree not created");
		    else
		    {
		       printf("\nNode-number ???   1.Left-subtree 2.Right-subtree");
		       printf("\nEnter your choice:");
		       scanf("%d",&ch);
		       switch(ch)
		       {
			  case 1: opt=1;
				  h1=nodenum(root,opt)-1;
				  printf("\nNode-number of Left subtree=%d",h1);
				  break;
			  case 2: opt=2;
				  h2=nodenum(root,opt)-1;
				  printf("\nNode-number of Right subtree=%d",h2);
				  break;
		       }
		    }
		    break;
	    case 8: if(root->data=='$')
		       printf("\nTree not created.");
		    else if(root->lchild==NULL && root->rchild==NULL && root->data!=-1)
		       printf("\nOnly the root node is present.");
		    else
		    {
		       c1=1;
		       h1=nodenum(root,c1)-1;
		       c2=2;
		       h2=nodenum(root,c2)-1;
		       if(h1>h2)
			  printf("\nLeft subtree is heavier.");
		       else if(h1