Сформировать бинарное дерево поиска и определить максимальную глубину дерева

#include <iostream>
#include <conio.h>
 
using namespace std;
//Наша структура
struct node
{
    int info; //Информационное поле
    node *l, *r;//Левая и Правая часть дерева
};
 
node * tree=NULL; //Объявляем переменную, тип которой структура Дерево
 
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО*/
void push(int a,node **t)
{
    if ((*t)==NULL) //Если дерева не существует
    {
        (*t)=new node; //Выделяем память
        (*t)->info=a; //Кладем в выделенное место аргумент a
        (*t)->l=(*t)->r=NULL; //Очищаем память для следующего роста
        return; //Заложили семечко, выходим
    }
       //Дерево есть
        if (a>(*t)->info) push(a,&(*t)->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
        else push(a,&(*t)->l); //Иначе кладем его влево
}
 
/*ФУНКЦИЯ УДАЛЕНИЯ ЭЛЕМЕНТОВ ДЕРЕВA*/
void delete_node(){
    if (t==NULL) return; //Если дерево пустое, то удалять нечего, выходим
    else //Иначе
    { //найти максимальный элемент
               
    }
}
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print (node *t,int u)
{
    if (t==NULL) return; //Если дерево пустое, то отображать нечего, выходим
    else //Иначе
    {
    print(t->l,++u);//С помощью рекурсивного посещаем левое поддерево
    for (int i=0;i<u;++i) cout<<"|";
    cout<<t->info<<endl; //И показываем элемент
    u--;
    }
    print(t->r,++u); //С помощью рекурсии посещаем правое поддерево
}
 
/*Функция поиска максимального элемента*/
int getMaxDepth(node* tree, int depth) {
if (tree == NULL)
return depth;
return max(getMaxDepth(tree->l, depth + 1), getMaxDepth(tree->r, depth + 1));
}
 
int main(int argc, char *argv[])
{
    int n; //Количество элементов
    int s; //Число, передаваемое в дерево
    cout<<"Vvod kol-vo elementov ";
    cin>>n; //Вводим количество элементов
 
    for (int i=0;i<n;++i)
    {
    cout<<"Enter Digit:";
    cin>>s; //Считываем элемент за элементом
 
    push(s,&tree); //И каждый кладем в дерево
    }
    cout<<"Node\n";
    print(tree,0);
    cout << "Max = "<<getMaxDepth(tree, 0);
    getch();
    return 0;
}

    BinaryTree binaryTree;
    for(int i =0; i<5; i++){
        binaryTree.Insert(i, ( rand() % 10));
    }
 
    binaryTree.Print();
 
///////////////////////////////////
 
    void Print(){
        if(root->value != NULL)
        cout << root->value;  // Здесь должна быть обработка для вывода на консоль... (ВИДИМО) :)
 
        else cout << "Not Tree";
    }

    void Insert(std::size_t k, int v)
     {
         if(root == nullptr)
         {
             root = new Node(); //Выделили память
             root->key = k;     //индекс
             root->value = v;   //значение
 
             return;
         }
    }

#include <cstddef>
#include <limits>
 
class BinaryTree
{
private:
    struct Node
    {
        Node* left;
        Node* right;
 
        std::size_t key;
        int value;
 
        Node(Node* l = nullptr, Node* r = nullptr) :
            left(l), right(r)
        {
            // ...
        }
 
        void Find(std::size_t k)
        {
            
        }
        void Insert(std::size_t k, int v)
        {
            if(k > key)
            {
                if (right) right->Insert(k, v);
                else
                {
                    right = new Node();
                    right->key = k;
                    right->value = v;
                }
 
            }
            else if (k < key)
            {
                if (left) left->Insert(k, v);
                else
                {
                    left = new Node();
                    left->key = k;
                    left->value = v;
                }
            }
            else
            {
                key = k;
                value = v;
            }
        }
    };
 
    Node* root;
 
public:
    BinaryTree() : root(nullptr) {}
 
    int Find(std::size_t k)
    {
        // Пока не решил что делать если элемент не найден
        if (root == nullptr)
            return -1; 
 
        // ...
 
        return 0;
    }
    void Insert(std::size_t k, int v)
    {
        if(root == nullptr)
        {
            root = new Node();
            root->key = k;
            root->value = v;
 
            return;
        }
 
        root->Insert(k, v);
    }
    void Remove(std::size_t k)
    {
        // ...
    }
};

    void Insert(std::size_t k, int v)
     {
         if(root == nullptr)
         {
             root = new Node(); //Выделили память
             root->key = k;     //индекс
             root->value = v;   //значение
 
             return;
 
         }
         if(k > root->value){
             root->key = k++; root->right = v; }  ошибка: invalid conversion from 'int' to 'BinaryTree::Node*' [-fpermissive]
           }
                                           
    }

#include <cstddef>
#include <limits>
 
class BinaryTree
{
private:
    struct Node
    {
        Node* left;
        Node* right;
 
        std::size_t key;
        int value;
 
        Node(Node* l = nullptr, Node* r = nullptr) :
            left(l), right(r)
        {
            // ...
        }
 
        int Find(std::size_t k)
        {
            if (k > key)
            {
                if (right) return right->Find(k);
                else return -1;
            }
            else if (k < key)
            {
                if (left) return left->Find(k);
                else return -1;
            }
            else
            {
                return value;
            }
        }
        void Insert(std::size_t k, int v)
        {
            if(k > key)
            {
                if (right) right->Insert(k, v);
                else
                {
                    right = new Node();
                    right->key = k;
                    right->value = v;
                }
 
            }
            else if (k < key)
            {
                if (left) left->Insert(k, v);
                else
                {
                    left = new Node();
                    left->key = k;
                    left->value = v;
                }
            }
            else
            {
                key = k;
                value = v;
            }
        }
    };
 
    Node* root;
 
public:
    BinaryTree() : root(nullptr) {}
 
    int Find(std::size_t k)
    {
        // Пока не решил что делать если элемент не найден
        if (root == nullptr)
            return -1; 
 
        return root->Find(k);
    }
    void Insert(std::size_t k, int v)
    {
        if(root == nullptr)
        {
            root = new Node();
            root->key = k;
            root->value = v;
 
            return;
        }
 
        root->Insert(k, v);
    }
    void Remove(std::size_t k)
    {
        // ...
    }
};

#include <iostream>
#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include <malloc.h>
#include <Windows.h>
#include <math.h>
 
using namespace std;
 
 
typedef struct binarytree
{
    int Data; //поле данных
    binarytree * Left; //указатель на левого потомка
    binarytree * Right; //указатель на правого потомка
} BinaryTree;
 
 
//вставка вершины в бинарное дерево
void Insert_Node_BinaryTree(BinaryTree** Node,int Data) {
    BinaryTree* New_Node = (BinaryTree*)
    malloc(sizeof(BinaryTree));
    New_Node->Data = Data;
    New_Node->Left = NULL;
    New_Node->Right = NULL;
    BinaryTree** ptr = Node;//вспомогательный указатель
while (*ptr != NULL)
    if (Data < (*ptr)->Data) ptr = &((*ptr)->Left);
else ptr = &((*ptr)->Right);
*ptr = New_Node;
}
 
//создание бинарного дерева
void Create(BinaryTree** p, int x)
{
if(!(*p))//если указатель на корень дерева не равен NULL
{
BinaryTree* pnew = (BinaryTree*)
    malloc(sizeof(BinaryTree));// выделяем память
    pnew->Data = x;//заносим значение
    pnew->Left = pnew->Right = NULL;
    *p = pnew;
}
 
else
{
    if((*p)->Data> x)
    Create(&((*p)->Left), x);
else
    Create(&((*p)->Right), x);
    }
}
 
/*Вывод двоичного дерева на экран*/
void Vyvod (BinaryTree **p,int l)
{
int i;
if (*p!=NULL)
{
    Vyvod (&((*p)->Right),l+1);
for (i=0; i<l; i++)
    printf(" ");
    printf("%d\n",(*p)->Data);
    Vyvod (&((*p)->Left),l+1);
    }
}
 
//удаление вершины из бинарного дерева
void Delete_Node_BinaryTree(BinaryTree** Node,int Data){
    if ( (*Node) != NULL ){
        if ((*Node)->Data == Data){
        BinaryTree* ptr = (*Node);
    if ( (*Node)->Left == NULL && (*Node)->Right == NULL)
    (*Node) = NULL;
    else if ((*Node)->Left == NULL) (*Node) = ptr->Right;
    else if ((*Node)->Right == NULL) (*Node) = ptr->Left;
else {
(*Node) = ptr->Right;
BinaryTree ** ptr1;
ptr1 = Node;
while (*ptr1 != NULL)
    ptr1 = &((*ptr1)->Left);
    (*ptr1) = ptr->Left;
}
free(ptr);
    Delete_Node_BinaryTree(Node,Data);
}
else {
    Delete_Node_BinaryTree(&((*Node)->Left),Data);
    Delete_Node_BinaryTree(&((*Node)->Right),Data);
        }
    }
}
 
 
bool empty_tree(BinaryTree * Node) //Проверяем пустое ли дерево
{
    if(Node==NULL) return true;
    else return false;
}
//прямой обход бинарного дерева
void PreOrder_BinaryTree(BinaryTree* Node){
    if (Node != NULL) {
        printf ("%3ld",Node->Data);
    PreOrder_BinaryTree(Node->Left);
    PreOrder_BinaryTree(Node->Right);
    }
}
 
 
/* Выводим максимальную глубину дерева */
/*максимальная глубина бинарного дерева
 *  - это количество нод на самом длинном пути от корневой ноды до самой дальней листовой ноды.*/
int maxDepth(BinaryTree* Node) {
  if (Node==NULL) {
    return(0);
  }
  else {
    // compute the depth of each subtree
    int lDepth = maxDepth(Node->Left);
    int rDepth = maxDepth(Node->Right);
    // use the larger one
    if (lDepth > rDepth) return(lDepth+1);
    else return(rDepth+1);
  }
}
 
 
//освобождение памяти, выделенной под бинарное дерево
/*С помощью функции Delete_BinaryTree(Root) программа рекурсивно выполняет очистку памяти, занимаемой деревом, используя
функцию освобождения памяти free. После прохождения по всем элементам дерева программа возвращает указателю на корень дерева
Root значение NULL, таким образом стирая и сам указатель на это дерево.*/
 
BinaryTree* Delete_BinaryTree(BinaryTree* Node){
if (Node != NULL) //Пока дерево не пусто
{
    Delete_BinaryTree(Node->Left); //проходимся по левой ветви
    Delete_BinaryTree(Node->Right); //проходимся по правой
    free(Node); //Удаляем указатель на дерево
}
return NULL;
}
int main()
{
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    cout << "Binarnoe derevo:\n" << endl;
 
    int i,n,temp;
    BinaryTree * Root;
    Root=NULL;
    printf("Enter Kol-vo \t"); scanf("%d",&n);
    for(i=0;i<n;i++)
    {
        scanf("%d",&temp);
        Create(&Root,temp);
    }
    Vyvod(&Root,0);
 
 
    printf("Max Hight dereva %d", maxDepth(Root));
    //Удаляем дерево
        Root=Delete_BinaryTree(Root);
        if(empty_tree(Root))
            printf("\nMemory delete!\n");
        getch();
    return 0;
}

void Insert_Node_BinaryTree(BinaryTree** Node,int Data);

#include <iostream>
#include <conio.h>
#include <algorithm>
 
using namespace std;
 
//Наша структура
struct node
{
    int info; //Информационное поле
    node *l, *r;//Левая и Правая часть дерева
};
 
/*ФУНКЦИЯ ЗАПИСИ ЭЛЕМЕНТА В БИНАРНОЕ ДЕРЕВО, все элементы уникальны */
void push(int num, node*& t)
{
    if (t == NULL) //Если дерева не существует
    {
        t = new node; //Выделяем память
        t->info = num; //Кладем в выделенное место аргумент a
        t->l = t->r = NULL; //Очищаем память для следующего роста
    }
    else if (num > t->info)
    {
         push(num, t->r); //Если аргумент а больше чем текущий элемент, кладем его вправо
    }
    else if(num < t->info)
    {
        push(num, t->l); //Иначе кладем его влево
    }
}
 
// поиск родителя для num
node* find_parent(node* tree, int const num)
{
    node* parent = NULL;
    while (tree)
    {
        if (num < tree->info)
        {
            parent = tree;
            tree = tree->l;
        }
        else if (num > tree->info)
        {
            parent = tree;
            tree = tree->r;
        }
        else
        {
            break;
        }
    }
    if (!tree)
    {
        parent = NULL;
    }
 
    return parent;
}
 
/*ФУНКЦИЯ УДАЛЕНИЯ ЭЛЕМЕНТА ДЕРЕВA*/
void delete_node(node*& t, int num) 
{
    if (t)
    {
        node* tree = t;
        // ищем родителя для num
        node* parent = find_parent(tree, num);
        // если родитель найден то tree выставляем на потомка которого нужно удалить
        if (parent)
        {
            if (parent->l && parent->l->info == num)
            {
                tree = parent->l;
            }
            else
            {
                tree = parent->r;
            }
        }
 
        if (tree->info == num || parent)
        {
            if (NULL == tree->l && NULL == tree->r) // у удаляемого узла нет потомков
            {
                if (parent)
                {
                    parent->l == tree ? parent->l = NULL : parent->r = NULL;
                }
                else // корневой узел без потомков
                {
                    t = NULL;
                }
                delete tree;
                tree = NULL;
            }
            else if (NULL == tree->l) // у удаляемого узла нет l 
            {
                node* tmp = tree->r;
                std::iter_swap(tree, tree->r);
                delete tmp;
                tmp = NULL;
            }
            else if (NULL == tree->r) // у удаляемого узла нет r
            {
                node* tmp = tree->l;
                std::iter_swap(tree, tree->l);
                delete tmp;
                tmp = NULL;
            }
            else // у удаляемого узла есть l и r
            {
                if (NULL == tree->r->l)
                {
                    node* tmp = tree->r;
                    tree->info = tree->r->info;
                    tree->r = tree->r->r;
                    delete tmp;
                    tmp = NULL;
                }
                else
                {
                    node* tmp = tree->r;
                    while (tmp->l->l)
                    {
                        tmp = tmp->l;
                    }
                    tree->info = tmp->l->info;
                    if (NULL == tmp->l->r)
                    {
                        delete tmp->l;
                        tmp->l = NULL;
                    }
                    else
                    {
                        node* t1 = tmp->l->r;
                        std::iter_swap(tmp->l, tmp->l->r);
                        delete t1;
                        t1 = NULL;
                    }
                }
            }
        }
    }
}
 
/*ФУНКЦИЯ ОТОБРАЖЕНИЯ ДЕРЕВА НА ЭКРАНЕ*/
void print(node *t, int u = 0)
{
    if (t)
    {
        print(t->r, u + 1);//С помощью рекурсивного посещаем левое поддерево
        for (int i = 0; i < u; ++i)
        {
            cout << "|";
        }
        cout << t->info << endl; //И показываем элемент
        print(t->l, u + 1); //С помощью рекурсии посещаем правое поддерево
    }
}
 
/*Функция поиска глубины*/
int depth(node* tree) 
{
    int ret = 0;
    if (tree) 
    {
        int lDepth = depth(tree->l);
        int rDepth = depth(tree->r);
        ret = std::max(lDepth + 1, rDepth + 1);
    }
    return ret;
}
 
int main()
{
    node * tree = NULL; //Объявляем переменную, тип которой структура Дерево
    int n; //Количество элементов
    int s; //Число, передаваемое в дерево
    cout << "Vvod kol-vo elementov ";
    cin >> n; //Вводим количество элементов
 
    for (int i = 0; i < n; ++i)
    {
        cout << "Enter Number:";
        cin >> s; //Считываем элемент за элементом
 
        push(s, tree); //И каждый кладем в дерево
    }
    cout << "Tree\n";
    {
        print(tree);
        cout << endl;
    }
    
    //cout << "\ndepth = " << depth(tree);
 
    delete_node(tree, 5);
    {
        print(tree);
        cout << endl;
    }
    push(10, tree);
    push(17, tree);
    {
        print(tree);
        cout << endl;
    }
    
    
    _getch();
    return 0;
}

/***************************************************************************
Я пока тебе так отправлю, потом надо будет дописать блок else в методе 
Remove, ну и еще пару коментов, а и еще нужно из всего этого сделать
шаблон, что бы структура хранила даные разных типов.
****************************************************************************/
 
#include <cstddef>
 
class BinaryTree
{
public:
    // Тип для исключения, если узел не найден
    struct NoElement {};
 
    // Тип для узла дерева
    struct Node
    {
        // Указатель на предка узла
        Node* parent;
 
        // Указатель на левого потомка узла
        Node* left;
        // Указатель на правого потомка узла
        Node* right;
 
        // Значение узла
        int value;
        // Ключ узла
        size_t key;
 
        /*Конструктор по умолчанию, все указатели в структуре nullptr.
          в полях value и key мусор*/
        Node() : left{nullptr}, right{nullptr}, parent{nullptr}
        {
            // ...
        }
 
        // Рекурсивный метод поиска узла по ключу
        int Find(size_t k) const
        {
            /*Если k > key поверяем указатель на правого потомка,
              если right != nullptr рекурсивно вызываем Find для
              правого потомка, если right == nullptr бросаем
              исключение NoElement*/
            if (k > key)
            {
                if (right) return right->Find(k);
                else throw NoElement();
            }
            /*Если k < key поверяем указатель на левого потомка,
              если left != nullptr рекурсивно вызываем Find для
              левого потомка, если left == nullptr бросаем
              исключение NoElement*/
            else if (k < key)
            {
                if (left) return left->Find(k);
                else throw NoElement();
            }
            // Если k == key возвращаем value
            else
            {
                return value;
            }
        }
        // Рекурсивный метод вставки значения v по ключу k
        void Insert(size_t k, int v)
        {
            /*Если k > key поверяем указатель на правого потомка,
              если right != nullptr рекурсивно вызываем Insert для
              правого потомка, если right == nullptr создаем нового
              потомка и присваеваем его полям новые значения*/
            if(k > key)
            {
                if (right) right->Insert(k, v);
                else
                {
                    right = new Node();
                    right->key = k;
                    right->value = v;
                    right->parent = this;
                }
 
            }
            /*Если k < key поверяем указатель на левого потомка,
              если left != nullptr рекурсивно вызываем Insert для
              левого потомка, если left == nullptr создаем нового
              потомка и присваеваем его полям новые значения*/
            else if (k < key)
            {
                if (left) left->Insert(k, v);
                else
                {
                    left = new Node();
                    left->key = k;
                    left->value = v;
                    left->parent = this;
                }
            }
            // Если k == key присваеваем его полям новые значения
            else
            {
                key = k;
                value = v;
            }
        }
        // Рекурсивный метод удаления узла по ключу
        void Remove(std::size_t k)
        {
            /*Если k > key поверяем указатель на правого потомка,
              если right != nullptr рекурсивно вызываем Remove для
              правого потомка, если right == nullptr бросаем
              исключение NoElement*/
            if (k > key)
            {
                if (right) return right->Remove(k);
                else throw NoElement();
            }
            /*Если k < key поверяем указатель на левого потомка,
              если left != nullptr рекурсивно вызываем Remove для
              левого потомка, если left == nullptr бросаем
              исключение NoElement*/
            else if (k < key)
            {
                if (left) return left->Remove(k);
                else throw NoElement();
            }
            // Если k == key расмотрим четыре варианта
            else
            {
                // Если нет ни правого ни левого потомка
                if (!left && !right)
                {
                    /* Проверяем является ли узел левым потомком родителя,
                       если да то обнуляем указатель родител на левого
                       потомка */
                    if (IsLeft() )
                        parent->left = nullptr;
                    /* В противном случае обнуляем указатель родителя на
                       правого потомка */
                    else
                        parent->right = nullptr;
 
                    // Удаляем узел
                    delete this;
                }
                // Если есть левый потомок, но нет правого
                else if (left && !right)
                {
                    /* Проверяем является ли узел левым потомком родителя,
                       если да то присваиваем родителю в левый узел
                       указатель на левый узел текущего узла */
                    if (IsLeft() )
                        parent->left = left;
                    else
                        parent->right = left;
 
                    left->parent = parent;
                    // Удаляем узел
                    delete this;
                }
                else if (!left && right)
                {
                    if (IsRight() )
                        parent->right = right;
                    else
                        parent->left = right;
 
                    right->parent = parent;
                    // Удаляем узел
                    delete this;
                }
                else
                {
                    // тут пока хз...)))
                }
            }
        }
 
        // Проверка является ли узел левым поддеревом
        bool IsLeft()
        {
            return parent->left && parent->left->key == key;
        }
        // Проверка является ли узел правым поддеревом
        bool IsRight()
        {
            return parent->right && parent->right->key == key;
        }
        
        // Глубина левого поддерева
        size_t CountLeft(size_t count)
        {
            if (left) return left->CountLeft(++count);
            else return count;
        }
        // Глубина правого поддерева
        size_t CountRight(size_t count)
        {
            if (right) return right->CountRight(++count);
            else return count;
        }
    };
 
    // Корневой узел дерева
    Node* root;
 
public:
    // По умолчанию конструктор (этим вроде как все сказанно)
    BinaryTree() : root(nullptr) {}
 
    // Интерфейс для связи с Node (далее все методы тоже самое...)
    int Find(std::size_t k)
    {
        if (root == nullptr)
            throw NoElement();
 
        return root->Find(k);
    }
    void Insert(std::size_t k, int v)
    {
        if(root == nullptr)
        {
            root = new Node();
            root->key = k;
            root->value = v;
 
            return;
        }
 
        root->Insert(k, v);
    }
    void Remove(std::size_t k)
    {
        if(root == nullptr)
            throw NoElement();
 
        root->Remove(k);
    }
 
    size_t CountLeft(size_t count = 0)
    {
        return root->CountLeft(count);
    }
    size_t CountRight(size_t count = 0)
    {
        return root->CountRight(count);
    }
};
 
int main(int argv, char* argc[] )
{
    BinaryTree binaryTree;
 
    binaryTree.Insert(15, 15 * 2);
    binaryTree.Insert(14, 14 * 2);
    binaryTree.Insert(13, 13 * 2);
    binaryTree.Insert(12, 12 * 2);
    binaryTree.Insert(18, 18 * 2);
    binaryTree.Insert(17, 17 * 2);
 
    size_t left = binaryTree.CountLeft();
    size_t right = binaryTree.CountRight();
 
    int value = binaryTree.Find(18);
    binaryTree.Remove(18);
 
    return 0;
}

/***************************************************************************
/Binary search tree/ Copyright (c) by P.S. Gennadevich. All rights reserved.
 V 0.1                                                           30.01.2018.
****************************************************************************/
 
#include <iostream>
 
template<typename TKey, typename TValue> class BinaryTree
{
public:
    // Тип для исключения, если узел не найден
    struct NoElement {};
 
    // Тип для узла дерева
    struct Node
    {
        // Указатель на предка узла
        Node* parent;
 
        // Указатель на левого потомка узла
        Node* left;
        // Указатель на правого потомка узла
        Node* right;
 
        // Ключ узла
        TKey key;
        // Значение узла
        TValue value;
 
        /* Указатель на BinaryTree, служит для обнуления указателя
           BinaryTree::root */
        BinaryTree* pProprietor;
 
        /* Конструктор */
        Node(
                TKey k = 0,
                TValue v = 0,
                Node* l = nullptr,
                Node* r = nullptr,
                Node* p = nullptr,
                BinaryTree* pP = nullptr
            ) :
                key{k},
                value{v},
                left{l},
                right{r},
                parent{p},
                pProprietor{pP}
        {
            std::cout << "Node::Node"
                << std::endl;
        }
        // Деструктор
        ~Node()
        {
            std::cout << "Node::~Node key: "
                << key << std::endl;
        }
 
        // Рекурсивное уничтожение дерева
        void Destroy()
        {
            if (left) left->Destroy();
            if (right) right->Destroy();
 
            delete this;
        }
 
        // Рекурсивный метод поиска узла по ключу
        int Find(TKey k) const
        {
            /* Если k > key поверяем указатель на правого потомка,
               если right != nullptr рекурсивно вызываем Find для
               правого потомка, если right == nullptr бросаем
               исключение NoElement */
            if (k > key)
            {
                if (right) return right->Find(k);
                else throw NoElement();
            }
            /* Если k < key поверяем указатель на левого потомка,
               если left != nullptr рекурсивно вызываем Find для
               левого потомка, если left == nullptr бросаем
               исключение NoElement */
            else if (k < key)
            {
                if (left) return left->Find(k);
                else throw NoElement();
            }
            // Если k == key возвращаем value
            else
            {
                return value;
            }
        }
        // Рекурсивный метод вставки значения v по ключу k
        void Insert(TKey k, TValue v)
        {
            /* Если k > key поверяем указатель на правого потомка,
               если right != nullptr рекурсивно вызываем Insert для
               правого потомка, если right == nullptr создаем нового
               потомка и присваеваем его полям новые значения */
            if(k > key)
            {
                if (right) right->Insert(k, v);
                else
                    right = new Node(k, v, nullptr, nullptr,
                        this, pProprietor);
            }
            /* Если k < key поверяем указатель на левого потомка,
               если left != nullptr рекурсивно вызываем Insert для
               левого потомка, если left == nullptr создаем нового
               потомка и присваеваем его полям новые значения */
            else if (k < key)
            {
                if (left) left->Insert(k, v);
                else
                {
                    left = new Node(k, v, nullptr, nullptr,
                        this, pProprietor);
                }
            }
            // Если k == key присваеваем его полям новые значения
            else
            {
                key = k;
                value = v;
            }
        }
        // Рекурсивный метод удаления узла по ключу
        void Remove(TKey k)
        {
            /* Если k > key поверяем указатель на правого потомка,
               если right != nullptr рекурсивно вызываем Remove для
               правого потомка, если right == nullptr бросаем
               исключение NoElement */
            if (k > key)
            {
                if (right) return right->Remove(k);
                else throw NoElement();
            }
            /* Если k < key поверяем указатель на левого потомка,
               если left != nullptr рекурсивно вызываем Remove для
               левого потомка, если left == nullptr бросаем
               исключение NoElement */
            else if (k < key)
            {
                if (left) return left->Remove(k);
                else throw NoElement();
            }
            // Если k == key рассматривается четыре варианта
            else
            {
                // Если нет ни правого ни левого потомка
                if (!left && !right)
                {
                    if (IsRoot() )
                        pProprietor->root = nullptr;
 
                    else if (IsLeftHeir() )
                        parent->left = nullptr;
 
                    else if (IsRightHeir() )
                        parent->right = nullptr;
 
                }
                // Если есть левый потомок, но нет правого
                else if (left && !right)
                {
                    if (IsRoot() )
                        pProprietor->root = left;
 
                    else if (IsLeftHeir() )
                        parent->left = left;
 
                    else if (IsRightHeir() )
                        parent->right = left;
 
                    left->parent = parent;
                }
                // Если есть правый потомок но нет левого
                else if (!left && right)
                {
                    if (IsRoot() )
                        pProprietor->root = right;
 
                    else if (IsLeftHeir() )
                        parent->left = right;
 
                    else if (IsRightHeir() )
                        parent->right = right;
 
                    right->parent = parent;
                }
                // Если есть оба потомка
                else
                {
                    // Если у правого потомка нет левого узла
                    if (!right->left)
                    {
                        right->parent = parent;
                        right->left = left;
                        left->parent = right;
 
                        if (IsRoot() )
                            pProprietor->root = right;
                    }
                    // Если у правого потомка есть левый узел
                    else
                    {
                        Node* lastLeft = right;
                        while (lastLeft->left)
                            lastLeft = lastLeft->left;
 
                        lastLeft->parent->left = nullptr;
 
                        lastLeft->left = left;
                        lastLeft->right = right;
                        lastLeft->parent = parent;
 
                        if (IsRoot() )
                            pProprietor->root = lastLeft;
                    }
                }
 
                // Удалить текущий узел
                delete this;
            }
        }
 
        // Проверка является ли узел левым потомком
        bool IsLeftHeir()
        {
            return parent->left && parent->left->key == key;
        }
        // Проверка является ли узел правым потомком
        bool IsRightHeir()
        {
            return parent->right && parent->right->key == key;
        }
        // Проверка является ли узел корнем
        bool IsRoot()
        {
            return !parent;
        }
    };
 
    // Указатель на корневой узел дерева
    Node* root;
 
public:
    // Конструктор по умолчанию root = nullptr
    BinaryTree() : root{nullptr}
    {
        // ...
    }
    // Деструктор
    ~BinaryTree()
    {
        root->Destroy();
    }
 
    // Интерфейс Find для связи с Node
    int Find(TKey k)
    {
        if (root == nullptr)
            throw NoElement();
 
        return root->Find(k);
    }
    // Интерфейс Insert для связи с Node
    void Insert(TKey k, TValue v)
    {
        if(root == nullptr)
        {
            root = new Node(k, v, nullptr, nullptr,
                nullptr, this);
 
            return;
        }
 
        root->Insert(k, v);
    }
    // Интерфейс Remove для связи с Node
    void Remove(TKey k)
    {
        if(root == nullptr)
            throw NoElement();
 
        root->Remove(k);
    }
};
 
#include <cstddef>
#include <string>
 
int main(int argv, char* argc[] )
{
    BinaryTree<std::size_t, int>* p1 = new BinaryTree<std::size_t, int>();
 
    p1->Insert(10, 10 * 2);
    p1->Insert(20, 20 * 2);
    p1->Insert(30, 30 * 2);
    p1->Insert(19, 19 * 2);
    p1->Insert(18, 18 * 2);
    p1->Insert(17, 17 * 2);
    p1->Insert(16, 16 * 2);
 
    p1->Insert(9, 9 * 2);
 
    p1->Remove(9);
 
    delete p1;
 
    BinaryTree<std::string, double>* p2 = new BinaryTree<std::string, double>();
 
    p2->Insert("One", 1.1);
    p2->Insert("Two", 2.2);
    p2->Insert("Three", 3.3);
    p2->Insert("Four", 4.4);
    p2->Insert("Five", 5.5);
    p2->Insert("Six", 6.6);
    p2->Insert("Seven", 7.7);
 
    p2->Insert("Eight", 8.8);
 
    p2->Remove("Eight");
 
    delete p2;
 
    return 0;
}