#include <malloc.h>
#include <stdio.h>
//-----------------------------
#define TYP char
typedef struct binary_tree
{
 TYP info;
 struct binary_tree *left;
 struct binary_tree *right;
}tr;
//-----------------------------
void init_tree(tr **tree)//inits new tree.
{
 *tree = NULL;
}
//-----------------------------
void make_tree(tr **tree,TYP data)//creates tree with the root 'data';
{
 *tree =(tr *)malloc(sizeof(tr));
 (*tree)->info = data;
 (*tree)->right =NULL;
 (*tree)->left = NULL;
}
//-----------------------------
void set_right(tr **tree,tr **right)//creates right son to 'tree'
{
 (*tree)->right=*right;
}
//-----------------------------
void set_left(tr **tree,tr **left)//creates left son to 'tree'
{
 (*tree)->left=*left;
}
//-----------------------------
void update_root(tr *tree,TYP data)//updates the root of 'tree' with 'data'
{
 tree->info=data;
}
//-----------------------------
void replace_left(tr *tree,TYP data)
{
 tree->left = (tr *)malloc(sizeof(tr));
 tree->left->info = data;
 tree->left->left = NULL;
 tree->left->right = NULL;
}
//-----------------------------
void replace_right(tr *tree,TYP data)
{
 tree->right = (tr *)malloc(sizeof(tr));
 tree->right->info = data;
 tree->right->left = NULL;
 tree->right->right = NULL;
}
//-----------------------------
tr *ret_sub_left(tr *tree)
{
 return(tree->left);
}
//-----------------------------
tr *ret_sub_right(tr *tree)
{
 return(tree->right);
}
//-----------------------------
TYP read_root(tr *tree)
{
 return(tree->info);
}
//-----------------------------
 is_empty(tr **tree)
{
  return(*tree==NULL);
}
//-----------------------------
 void build_tree( tr *tree,TYP num)
{
	 tr *temp;
 if (tree != NULL)
  {
   if (num < tree->info)
	{
	 if (tree->left == NULL)
	  {
	   
		 make_tree(&temp,num);
		 set_left(&tree,&temp);
	  }
	 else
	  {
		build_tree(tree->left,num);
	  }
	}
   else
	{
	 if (tree->right == NULL)
	  {
		 make_tree(&temp,num);
	   set_right(&tree,&temp);
	  }
	 else
	  {
		build_tree(tree->right,num);
	  }
	}
  }
}
//--------------------------
int count_tree( tr*tree)
{
 if (tree == NULL)
  {
   return(0);
  }
 else
  {
	return(1+count_tree(tree->left)+count_tree(tree->right));
  }
}
//--------------------------
int count_leaf( tr*tree)
{
 if (tree == NULL)
  {
	return(0);
  }
 else
  {
	if ((tree->left==NULL)&&(tree->right==NULL))
	{
	 return(1+count_leaf(tree->left)+count_leaf(tree->right));
	}
	else
	{
	 return(count_leaf(tree->left)+count_leaf(tree->right));
	}
  }
}
//--------------------------
int sum_tree( tr *tree)
{
 if (tree == NULL)
  {
	return(0);
  }
 else
  {
	return(tree->info+sum_tree(tree->left)+sum_tree(tree->right));
  }
}
//--------------------------
tr *find_addres(tr *tree,int num)
{
 if (tree == NULL)
  {
	return(NULL);
  }
 else
  {
   if (tree->info == num)
	{
	 return(tree);
	}
	else
	{
	 if (find_addres(tree->left,num)!=NULL)
	  {
		return(find_addres(tree->left,num));
	  }
	 if (find_addres(tree->right,num)!=NULL)
	  {
		return(find_addres(tree->right,num));
	  }
	}
  }
 return(0);
}
//-----------------------------
tr *mirror(tr *tree)
{
 tr *temp;
 if (tree!=NULL)
 {
  temp=tree->left;
  tree->left=tree->right;
  tree->right=temp;
  mirror(tree->left);
  mirror(tree->right);
  return(tree);
 }
 return(0);
}
//-----------------------------
int height(tr *root)
{
int h_left,h_right;
if(root==NULL)
return(-1);
h_left=height(root->left);
h_right=height(root->right);
if(h_left>h_right) return(h_left+1);
else return(h_right+1);
}
//-----------------------------
void print_in(tr *t)
{
 if (t!=NULL)
 {
  print_in(t->left);
  printf("%c ",t->info);
  print_in(t->right);
 }
}
//-----------------------------
void print_post(tr *t)
{
 if (t!=NULL)
 {
  print_in(t->left);
  print_in(t->right);
  printf("%c ",t->info);
 }
}
//-----------------------------
void print_pre(tr *t)
{
 if (t!=NULL)
 {
  printf("%c ",t->info);
  print_pre(t->left);
  print_pre(t->right);
 }
}
int sim_tree(tr *t1,tr *t2)
{
	if (is_empty(&t1) && is_empty(&t2))
	{
		return (1);
	}
	if (is_empty(&t1) || is_empty(&t2))
	{
		return (0);
	}
	return (  sim_tree(t1->left,t2->left)
				&&sim_tree(t1->right,t2->right)  );
}
tr* treetree(tr *tl, char op, tr *t2)
{
	tr *tmp=NULL;
	make_tree(&tmp,op);
	tmp->left=tl;
	tmp->right=t2;
	return tmp;
}
tr *build_math_tree(char s,int &i)
{
	tr *t,*t1,*t2;
	char ch,op;
	ch=s;
	if (ch>='0' && ch<='9')
	{
		make_tree(&t,ch);
	}
	else
	{
		if (ch=='(')
		{
			t1=build_math_tree(s,i);
		}
		op=s;
		t2=build_math_tree(s,i);
		t=treetree(t1, op, t2);
		ch=s;
	}
	return (t);
}
bool leaf(tr *t)
{
	return (!(t->right && t->left));
}
int calc(tr *t)
{
	if (t->info>='0' && t->info<='9')
		return (t->info - '0');
	switch (t->info)
	{
	case '+':
		return calc(t->left)+calc(t->right);
		break;
	case '-':
		return calc(t->left)-calc(t->right);
		break;
	case '*':
		return calc(t->left)*calc(t->right);
		break;
	case '/':
		return calc(t->left)/calc(t->right);
		break;
	}
	return 0;
}
bool avg_tree( tr *t)
{
	if (!t)
		return true;
	if (leaf(t))
		return true;
	if (((t->right->info+t->left->info)/2)==t->info)
		return (avg_tree(t->left)&&avg_tree(t->right));
	return false;
}
void main()
{
	int i=0;
	tr *t;
	init_tree(&t);
	t=build_math_tree("(((6/2)+2)*5)", i);
	print_in(t);
	printf("\n\n\n%d\n\n", calc(t));
	free(t);
}