#include<iostream.h>
struct node
{
  int Key;
  int Count;
  node *Left;
  node *Right;
};

class TREE
{
  private:
	 node *Tree;//Указатель на корень дерева.
	 int Flag; //Флаг АВЛ-дерева.
	 //Поиск вершины в дереве (рекурсивный алгоритм).
	 void Search (int, node**);
	 int Height (node **);
  public:
	 TREE() { Tree = NULL;}
	 node** GetTree() {return &Tree;}
	 void SetFlagTrue() { Flag = 1;}
	 int GetFlag() { return Flag; }
	 void  BuildTree ();
	 void Vyvod (node**,int);
	 int AVLtree (node **);
};

void main ()
{
  TREE A;

  A.BuildTree ();  A.Vyvod (A.GetTree(),0);

  A.SetFlagTrue(); //Установка флага в "истину".
  A.AVLtree (A.GetTree()); cout<<endl;
  if (A.GetFlag()) cout<<"\nДерево является АВЛ-деревом";
  else cout<<"\nДерево не является АВЛ-деревом";
}


void TREE::BuildTree ()
//Построение бинарного дерева.
//Tree - указатель на вершину дерева.
{
  int el;

  cout<<"Вводите ключи вершин дерева: \n";
  cin>>el;
  while  (el!=0)
	 { Search (el,&Tree);cin>>el; }
}

void TREE::Vyvod (node **w,int l)
//Изображение дерева w на экране дисплея
//         (рекурсивный алгоритм).
//*w - указатель на корень дерева.
{
  int i;

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


void TREE::Search (int x,node **p)
//Поиск звена x в бинарном дереве со вставкой
//            (рекурсивный алгоритм).
//*p - указатель на вершину дерева.
{
  if  (*p==NULL)
  {  // Вершины в дереве нет; включить ее.
	 *p = new(node);
	 (**p).Key = x;     (**p).Count = 1;
	 (**p).Left = (**p).Right = NULL;
  }
  else
   if  (x<(**p).Key) Search (x,&((**p).Left));
   else
    if  (x>(**p).Key) Search (x,&((**p).Right));
    else  (**p).Count += 1;
}

int TREE::Height (node **w)
//Определение высоты бинарного дерева.
//*w - указатель на корень дерева.
{
  int h1,h2;
  if  (*w==NULL) return (-1);
  else
  {
	 h1 = Height (&((**w).Left));
	 h2 = Height (&((**w).Right));
	 if  (h1>h2) return (1 + h1);
	 else  return (1 + h2);
  }
}

int TREE::AVLtree (node **w)
// Предикат, возвращающий 0, если бинарное дерево поиска
// не является АВЛ-деревом.
// *w - указатель на корень дерева.
{
  int t;

  if (*w!=NULL)
  {
   t = Height (&((**w).Left)) - Height (&((**w).Right));
   if ((t<-1) || (t>1)) { Flag = 0; return (Flag); }
   AVLtree (&((**w).Left)); AVLtree (&((**w).Right));
  }
}