#pragma once

#include <iostream>
#include <ostream>
template <typename T>
class Node
{
private:
 Node* left;
 Node * right;
 T data;
public:
 Node(const Node& Item)
 {
  left = Item.left;
  right = Item.right;
  data = Item.data;
 }
 Node(T value)
 {
  left = nullptr;
  right = nullptr;
  data = value;
 }
 T get_data() const
 {
  return data;
 }
 void add(T value);   //добавление нового элемента
 bool search(T value) const; //проверка - есть ли элемент с заданным
 bool remove(T value);
 T get_min() const;
 T get_max() const;
 void printVozrast() const;
 void printUbiv() const;
 friend std::ostream& operator«(std::ostream& os, const Node<T>& node);

};
template <typename T>
class BinaryTree
{
private:
 Node<T>* root;
public:
 BinaryTree()
 {
  root = nullptr;
  std::cout « "Tree created" « std::endl;// вывод
 }//конструктор
 bool isEmpty() const
 {
  return(root ? false : true)
 }//проверяет на существования корня
 void add(T value);//добавление узла
 bool search(T value) const;//поиск узла с заданным значением
 void remove(T value);//при тру поиск и при нахождении удаление , при фалс не удаляет ничего (значит нет такого узла)
 T getMin()const;
 T getMax()const;
 void print(bool ubivanie = false)const;
 ~BinaryTree();
 friend std::ostream& operator«(std::ostream& os, const BinaryTree<T>& tree);
};




template <typename T>
void Node<T>::add(T value)
{
 // элемент должен попасть в право
 if (value > data)
  //если правое существует
  if (right)
   //рекурсивно
   right->add(value);
  else
   //иначе создаём новый и ставим его правым
   right = new Node(value);
 //ВАЖНО!!!
 //оператор new распределяет динамическую память,
 //но при этом ещё и вызывается конструктор для создаваемого объекта

 //добавляемый элемент должен попасть в левое поддерево
 if (value < data)
  if (left)
   left->add(value);
  else
   left = new Node(value);
}
template <typename T>
Node<T>* Node<T>::search(T value)const
{
 //если нашли - вернули адрес узла
 if (data == value)
 {
  return this;
 }

 if(value > data)
 {
  if (right)
   return right->search(value);
  else
   return nullptr;
 }
 else
  if (left)
  {
   return left->search(value);
  }
  else
   return nullptr;
}


template <typename T>
Node<T>* Node<T>::remove(T value)
{

 Node<T>* udalenie = nullptr;

 if (value > data && right)
 {

  udalenie = right->remove(T value);

  if (udalenie == right)
  {
   right = nullptr;
  }
 }

 if (value < data && left)
 {
  udalenie = left->remove(value);
  if (udalenie == left)
   left = nullptr;
 }

 if (data == value)
 {
  if (!left && !right)
  {
   udalenie = this;
  }
  if (left && !right)
  {
   udalenie = left;
   *this = *left;
  }

  if (!left && right)
  {
   udalenie = right;
   *this = *right;
  }
 }

 if (left && right)
 {

  int max_left = left->get_max()->data;
  int min_right = right->get_min()->data;

  if ((data - max_left) < (min_right - data))
  {

   udalenie = left->remove(max_left);

   data = max_left;
  }
  else
  {

   udalenie = right->remove(min_right);
   data = min_right;
  }
 }

 if (udalenie)
 {

  udalenie->left = nullptr;
  udalenie->right = nullptr;

 }
 return udalenie;
}


template <typename T>
T Node<T>::get_min()const
{

 if (left)
  return left->get_min();//рекурсивно
 else

  return this;
}
template <typename T>
T Node<T>::get_max()const
{

 if (left)
  return left->get_max();
 else

  return this;
}

template <typename T>
Node<T>::~Node()
{


 if (left)
  delete left;
 if (right)
  delete right;


 std::cout « "destructor work! " « data « endl;
}
template <typename T>
std::ostream& Node<T>::operator«(std::ostream& os, const Node<T>& node)
{
 os « node->get_data() « std::endl;
 return os;
}
template <typename T>
void Node<T>::printVozrast() const
{
 if (left)
  left->printVozrast();  //обходим левое

 cout « data « " ";   //печатаем содержимое

 if (right)
  right->printVozrast(); //обхдим правое
}
template <typename T>
void Node<T>::printUbiv() const
{

 if