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

struct no
{
  node *elem;
  int ch;
  no *sled;
};

class TREE
{
  private:
    node *Tree;
    void PushStack (no **,node **,int *);
    void PopStack (no**,node **,int *);
    void VyvodStack (no**);
  public:
    TREE () { Tree = new(node); (*Tree).Right = NULL; }
    node* GetTreeRight () {return (*Tree).Right;}
    void  TreeSearch (int);
    void  VyvodTree (node *);
};

void main ()
{
  TREE A;
  int el;

  cout<<"Вводите значения информационных полей вершин: "<<endl;
  cin>>el;
  while  (el!=0)
   { A.TreeSearch (el); cin>>el; }
  A.VyvodTree (A.GetTreeRight());
}

void TREE::TreeSearch (int el)
 // Поиск вершины с информационным полем  el в дереве с
 // последующим (в случае неудачного поиска!) включением
 // в дерево. Tree - указатель на корень дерева.
{
  node *p1,*p2;
  int  d;

  p2 = Tree; p1 = (*p2).Right; d = 1;
  while  (p1!=NULL && d!=0)
  {
    p2 = p1;
    if  (el<(*p1).Key) {p1 = (*p1).Left; d = -1;}
    else
      if  (el>(*p1).Key) {p1 = (*p1).Right; d = 1;}
      else  d = 0;
  }
  if  (d==0)  (*p1).Count = (*p1).Count + 1;
  else
  {
    p1 = new(node);
    (*p1).Key = el;  (*p1).Left = NULL;
    (*p1).Right = NULL;  (*p1).Count = 1;
    if  (d<0) (*p2).Left = p1;
    else  (*p2).Right = p1;
  }
}


void TREE::VyvodTree (node *t)
 //Построение дерева, заданного указателем t,
 //на экране дисплея (нерекурсивный алгоритм).
{
  no *stk,*stk1;
  node *u;
  int i,n;
  stk = stk1 = NULL; n = 0;
  while  (t!=NULL)
  {
    PushStack (&stk1,&t,&n);
    if  ((*t).Right!=NULL)
    {
      if  ((*t).Left!=NULL) PushStack (&stk,&((*t).Left),&n);
      t = (*t).Right;
    }
    else
    {
      if  ((*t).Left!=NULL)
      {
        if  (stk1!=NULL)
        {
          PopStack (&stk1,&u,&n);
          for  (i=0; i<=n; i++) cout<<" ";
          cout<<(*u).Key<<endl;
        }
        t = (*t).Left;
      }
      else
       if  (stk==NULL) t = NULL;
       else
       {
         while  ((*stk).elem!=(*((*stk1).elem)).Left)
         {
           PopStack (&stk1,&u,&n);
           for  (i=0; i<=n; i++) cout<<" ";
           cout<<(*u).Key<<endl;
         }
         PopStack (&stk1,&u,&n);
         for  (i=0; i<=n; i++) cout<<" ";
         cout<<(*u).Key<<endl;
         PopStack (&stk,&t,&n);
       }
    }
    n = n + 1;
  }
  VyvodStack (&stk1);
}


void TREE::PushStack (no **stk,node **el,int *n)
 // Помещение звена с элементами *el и n в стек.
 // *stk - указатель на стек.
{
  no *q;

  q = new(no);
  (*q).elem = *el;  (*q).ch = *n;
  (*q).sled = *stk; *stk = q;
}

void TREE::PopStack (no**stk,node **t,int *n)
// Извлечение из стека звена с элементами *t и n.
// *stk - указатель на стек.
{
  no *q;

  if  (*stk!=NULL)
  {
    *t = (**stk).elem;
    *n = (**stk).ch;
    q  = *stk; 
    *stk = (**stk).sled; 
    delete q;
  }
}

void TREE::VyvodStack (no** stk)
// Вывод содержимого стека на экран дисплея.
// *stk - указатель на стек.
{
  node *k;
  int i,n;

  while  (*stk!=NULL)
  {
    k = (**stk).elem; n = (**stk).ch;
    for  (i=0; i<=n; i++) cout<<" ";
      cout<<(*k).Key<<endl;
    *stk = (**stk).sled;
  }
}