#ifdef HAVE_CONFIG_H
#include <config.h>
#endif

#include <iostream>
#include <cstdlib>
#include <vector.h>
#include <math.h>

using namespace std;
struct  TNode
{
  int Key;
  int index;
  int Count;
  TNode *Left;
  TNode *Right;
};

class TArbre
{
  private:
    TNode *Tree;
    void Search (int,TNode**);
  public:
    vector<int> index;
    TArbre() {Tree=NULL;}
    TNode** Rendre_la_racine () {return &Tree;}
    void BuildTree ();
    void CleanTree (TNode **);
    void Gauche_detour (TNode **); 
    void Imprimante (TNode **,int);
    int Altitude (TNode **);
    void Reindex (TNode **, vector<int> &);
    void iGauche_detour (TNode **, vector<int> &);
    void icGauche_detour (TNode **, vector<int> &);
    bool IsInIndex (const int &, vector<int> &);
};

int main ()
{
  TArbre A;
  A.index.reserve( 10 );
  A.BuildTree ();
  cout<<"\nВывод дерева:\n";
  A.Imprimante (A.Rendre_la_racine(), 0 );
  cout<<"\nВысота дерева:"<<A.Altitude(A.Rendre_la_racine())<<endl;
  cout<<"\nЛевосторонний обход дерева: ";
  A.Gauche_detour (A.Rendre_la_racine()); 
  A.Reindex (A.Rendre_la_racine(), A.index);
  bool cont=true;
  while (cont==true)
  {
     cout<<"\nВведите искомый элемент: ";
     int z;
     cin>>z;
     if (A.IsInIndex (z, A.index)==true)
     {
        cout<<"\nТакой элемент в дереве есть."; 
     }
     else
     {
        cout<<"\nТакого элемента в дереве нет."; 
     }
     cout<<"\nХотите попробовать найти другой элемент? (1/0)"; 
     int b;
     cin>>b;
     if (b== 0 ) cont=false;
  }
  A.CleanTree (A.Rendre_la_racine());
 return  0 ;
}

void TArbre::BuildTree ()
{
  int el;
  cout<<"Вводите количество ключей вершин дерева: ";
  int cnt;
  cin>>cnt;
  for(int i= 0 ;i<cnt;i++)
  {cout<<"Введите "<<i+ 1 <<"-ю вершину дерева: "; cin>>el; Search (el,&Tree);}
}

void TArbre::Search (int x,TNode **p)
{
  if  (*p==NULL)
  {// Вершины в дереве нет; включить ее.
    *p = new(TNode);
    (**p).Key = x;     (**p).Count =  1 ;
    (**p).Left = NULL; (**p).Right = NULL; }
  else
    if  (x<(**p).Key) Search (x,&((**p).Left));
    else
      if  (x>(**p).Key) Search (x,&((**p).Right));
      else  (**p).Count = (**p).Count +  1 ;
}

void TArbre::Gauche_detour (TNode **w)
{
  if  (*w!=NULL)
  {
    cout<<(**w).Key<<" ";
    Gauche_detour (&((**w).Left));
    Gauche_detour (&((**w).Right));
  }
}

void TArbre::CleanTree (TNode **w)
{
  if  (*w!=NULL)
  { CleanTree (&((**w).Left));
    CleanTree (&((**w).Right));
    delete *w; }
}

void TArbre::Imprimante (TNode **w,int l)
{
  int i;

  if  (*w!=NULL)
  { Imprimante (&((**w).Right),l+ 1 );
    for  (i= 1 ; i<=l; i++) cout<<"   ";
    cout<<(**w).Key<<endl;
    Imprimante (&((**w).Left),l+ 1 ); }
}

int TArbre::Altitude (TNode **w)
{
  int h1,h2;
  if  (*w==NULL) return (- 1 );
  else
  {
    h1 = Altitude (&((**w).Left));
    h2 = Altitude (&((**w).Right));
    if  (h1>h2) return ( 1  + h1);
    else  return ( 1  + h2);
  }
}

void TArbre::iGauche_detour (TNode **w, vector<int> &index)
{
  if  (*w!=NULL)
  {
    index.resize(index.size()+ 1 );
    index.at(index.size()- 1 )=(**w).Key;
    iGauche_detour (&((**w).Left), index);
    iGauche_detour (&((**w).Right), index);
  }
}

void TArbre::icGauche_detour (TNode **w, vector<int> &index)
{
  if  (*w!=NULL)
  {
    for (int i= 0 ;i<index.size();i++)
    {
       if (index.at(i)==(**w).Key)
       {
          (**w).index=index.at(i);
       }
    }
    icGauche_detour (&((**w).Left), index);
    icGauche_detour (&((**w).Right), index);
  }
}

void TArbre::Reindex (TNode **w, vector<int> &index)
{
   index.clear();
   iGauche_detour (w, index);
   for(int j= 0 ;j<index.size();j++)
   {
      for(int i= 0 ;i<index.size()-j;i++)
      {
          if (index.at(i)>index.at(i+ 1 ))
          {
             int buf=index.at(i);
             index.at(i)=index.at(i+ 1 );
             index.at(i+ 1 )=buf;
          }
      }
   }
   for (int i= 0 ;i<index.size();i++)
   {
       index.at(i)=i;
   }
   icGauche_detour (w, index);
}

bool TArbre::IsInIndex (const int &x, vector<int> &index)
{
   int a= 0 ;
   int b=(index.size()- 1 );
   int c=- 1 ;
   bool rst=false;
   while ((a!=b)&&(rst==false))
   {
      c=trunc((b-a)/ 2 );
      if (index.at(c)==x) rst=true;
      if (index.at(c)<x) b=trunc(b/ 2 );
      if (index.at(c)>x)
      {
          if (b<=(c+ 1 ))
          {
              a=c+ 1 ;
          }
      }
   }
   if (index.at(a)==x) rst=true;
   return rst;
}