#include <iostream.h>
#include <stdlib.h>
#define N 10 //Количество элементов массива.
struct node
{
	int Key;
	int Count;
	node *Left;
	node *Right;
};

class Spisok {
  private:
	 node *UkStr[N];
	 void Search (int, node**);
	 void PrintTree (node *, int);
	 void U_d (node **,node **);
  public:
	 Spisok ();
	 void BuildTree();
	 void Sodergimoe();
	 node** GetTree (unsigned i) {return &(UkStr[i]);}
	 void Udaldr (node** d, int k);
};

Spisok::Spisok()
{
  //Инициализация хэш-списка.
  for (int i=0;i<N;i++) UkStr[i] = NULL;
}

void Spisok::BuildTree()
{
  int klutch;
  unsigned hash;

  cout << "\nВведите значение ключа...";
  //cin >> klutch;
  //Закомментируйте следующие три строки,
  //если нужно задавать значения ключей с клавиатуры.
  randomize();
  klutch = random(31);
  cout << klutch;
  while (klutch!=0)
  {
	 hash = klutch % 10;  //Вычисление значения хэш-функции.
	 Search (klutch,&UkStr[hash]);
	 cout << "\nВведите значение ключа...";
	 //cin >> klutch;
	 klutch = random(31);
	 cout << klutch;
  }
}

void Spisok::Search(int X, node **p)
{
  if  (*p==NULL)
   { //Узла нет в деpеве; включить его.
     *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;
}

void Spisok::Sodergimoe()
{
  for(int i=0;i<N;i++)
  {
	 cout << "  "<< i <<"...  ";
	 if  (UkStr[i]==NULL)  cout << "Деpево пусто...\n";
	 else
	 {
            cout << endl;
            PrintTree (UkStr[i],0);
	 }
	 cout << "------------------------------------------" << endl;
  }
}

void Spisok::PrintTree (node *w, int l)
{
  if  (w!=NULL)
  {
	 PrintTree ((*w).Right,l+1);
	 cout << "          ";
	 for (int i=1;i<=l;i++) cout <<"   ";
	 cout << (*w).Key << endl;
	 PrintTree ((*w).Left,l+1);
  }
}

void Spisok::Udaldr (node** d, int k)
{ //Удаление узла с ключом k из деpева d.
  node** q;

  if (*d==NULL) cout << "Узел с заданным ключом в деpеве не найден...\n";
  else
	if  (k < (**d).Key) Udaldr (&((**d).Left),k);
	else
     if  (k > (**d).Key)  Udaldr (&((**d).Right),k);
     else  
      {
        q = d;
        if ((**q).Right == NULL) *d = (**q).Left;
        else
          if  ((**q).Left == NULL )  *d = (**q).Right;
          else  U_d (&((**q).Left),&(*q));
      }
}

void Spisok::U_d(node **r, node **q)
{
  if  ((**r).Right == NULL)
  {
    (**q).Key = (**r).Key;
    (**q).Count = (**r).Count;
    q = r; *r = (**r).Left; delete (*q);
  }
  else  U_d (&((**r).Right),&(*q));
}

void main()
{
  Spisok A;
  int klutch;
  unsigned hash;
  
  A.BuildTree();
  cout << "\n          Содеpжимое хэш-списка...";
  cout << "\n    -----------------------------------";
  A.Sodergimoe();
  //Удаление элемента из хэш-списка.
  for (int i=0;i<4;i++) //Будем удалять всего 4 pаза!
  {
    cout << "\nВведите значение удаляемого ключа...";
    cin >> klutch;
    hash = klutch % 10;
    A.Udaldr (A.GetTree(hash),klutch);
    cout << "          Содеpжимое хэш-списка...\n";
    cout << "   ----------------------------------\n";
    A.Sodergimoe();
  }
}