/*** sapd - lab_2 ***/
#include <stdio.h>
#include <stdlib.h>
#define SIZE 100

struct vertex //структура дерева
            {
             vertex *left;
             vertex *right;
             int data;
            } *root,*sroot, *sroot1 ;   
int array[SIZE];

//create tree 
vertex *IDSP(int L, int R) 
{
 int i;      
 vertex *r;
 if(L>R) return NULL;
 else 
 {
  i=(L+R)/2;
  r=new vertex;
  r->data=array[i];
  r->left=IDSP(L,i-1);
  r->right=IDSP(i+1,R);
  return r;
 }
}

//create binare search tree
vertex *AddVertex(int data, vertex *root)
{
 vertex **p;
 p=&root;
 while(*p!=NULL)
 {
  if(data<(*p)->data) p=&((*p)->left);
  if(data>(*p)->data) p=&((*p)->right);
  else break;
 }
 if(*p==NULL)
 {
  *p=new vertex;
  if((*p)==NULL)   
  {
   printf("Error 0x42! Not enought memory!\n");
  }
  (*p)->data=data;
  (*p)->right=NULL;
  (*p)->left=NULL;
  //printf("%4d",(*p)->data);
 }
}

vertex *AddVertexRec(int data, vertex *&p) 
{
 if(!p) 
 {
  p=new vertex;
  if(p==NULL)   
  {
   printf("Error 0x42! Not enought memory!\n");
  }
  p->data=data;
  p->left=NULL;
  p->right=NULL;
 }
 else 
 { 
  if(data<p->data) AddVertexRec(data,p->left);
  else 
   if(data>p->data) AddVertexRec(data,p->right);
 }
}

//detour
void Detour(vertex *p)
{
 if(!p) return;
 Detour(p->left);
 printf("%4d",p->data);
 Detour(p->right);
} 


//size
int Size(vertex *p)
{
 if(!p) return 0;
 return 1+Size(p->left)+Size(p->right);
}

//max
int max(int a, int b) 
{
 if(a>b)return a;
 return b;
}

//height 
int Height(vertex *p)
{
 if(!p)return 0;
 return 1+max(Height(p->left),Height(p->right));
}

//midheight
float MidHeight(vertex *p, int layer)
{
 if(!p) return 0;
 return layer+MidHeight(p->left,layer+1)+MidHeight(p->right,layer+1); 
}



//MAIN
int main()
{
//create array 
 printf("array:\n");
 for(int i=0;i<SIZE;i++)
 {
  array[i]=array[i-1]+rand()%10;
  printf("%4d",array[i]);
 }
 
//create IBST 
 printf("\n");
 root=IDSP(0,SIZE-1);
 printf("tree:\n");
 Detour(root);
 printf("\ntree size: %4d",Size(root));          
 printf("\ntree height: %4d",Height(root));
 float Mheight=MidHeight(root,1)/Size(root);
 printf("\ntree midheight: %4.2f",Mheight);
 printf("\n");
 
 
//create BST rec
 printf("array:\n");
 for(int i=0;i<SIZE;i++)
 {
  array[i]=rand()%100;
  printf("%4d",array[i]);
 }
 printf("\n");
 printf("tree:\n");
 sroot=NULL;
 for(int i=0;i<SIZE;i++)
  AddVertexRec(array[i],sroot);  
 Detour(sroot);
 printf("\ntree size: %4d",Size(sroot));          
 printf("\ntree height: %4d",Height(sroot));
 Mheight=MidHeight(sroot,1)/Size(sroot); 
 printf("\ntree midheight: %4.2f",Mheight);
 printf("\n");
 

//create BST
 printf("\n");
 printf("array:\n");
 for(int i=0;i<SIZE;i++)
 {
  array[i]=rand()%100;
  printf("%4d",array[i]);
 }
 printf("\n");
 printf("tree:\n");
 sroot1=NULL;
 for(int j=0;j<SIZE;j++)
  AddVertex(array[j],sroot1);  
 Detour(sroot1);
 printf("\ntree size: %4d",Size(sroot1));          
 printf("\ntree height: %4d",Height(sroot1));
 Mheight=MidHeight(sroot,1)/Size(sroot1); 
 printf("\ntree midheight: %4.2f",Mheight);
 printf("\n");
 
 
 printf("\nProgramm complite successfull.Stop 0x00\n");
 system("PAUSE");       
 return 0;
}

void AddVertex(int data, vertex *&root)
{
 vertex **p;
 p=&root;
 while((*p)!=NULL)
 {
  if(data<(*p)->data) p=&((*p)->left);
  else
   if(data>(*p)->data) p=&((*p)->right);
   else
    if(data==(*p)->data) break;
 }
 if((*p)==NULL)
 {
  *p=new vertex;
  if((*p)==NULL)   
  {
   printf("Error 0x42! Not enought memory!\n");
  }
  (*p)->data=data;
  (*p)->right=NULL;
  (*p)->left=NULL;
  
 }
}