#include <iostream>

class elem{                             // класс узла
public:
    int m_data;
    elem* m_left;
    elem* m_right;
    elem(int val){
        m_left = NULL;
        m_right = NULL;
        m_data = val;
    }
};

class binary_tree{                      // класс дерева
public:
    binary_tree(int);
    ~binary_tree();
    void print();
    bool find(int);
    void insert(int);
    void erase(int);
    int size() { return m_size; }
private:
    elem* m_root;
    int m_size;
    void print_tree(elem*, int);
    void delete_tree(elem*);

};

binary_tree::binary_tree(int key)                        // конструктор
{
    m_root = new elem(key);
    m_size = 1;
}

binary_tree::~binary_tree(){                              // деструктор
    delete_tree(m_root);
}
void binary_tree::delete_tree(elem* curr){
    if (curr){
        delete_tree(curr->m_left);
        delete_tree(curr->m_right);
        delete curr;
    }
}

void binary_tree::print(){                                 // вывод
    print_tree(m_root, 0);
    std::cout <<'\n';
}

void binary_tree::print_tree(elem* p, int lvl){
    if (p){
        print_tree(p->m_left, lvl + 1);
        for (int i = 0; i < lvl; i++) std::cout << "   ";
        std::cout << p->m_data << std::endl;
        print_tree(p->m_right, lvl + 1);
    }
}

void binary_tree::insert(int key){                         // добавление
    elem* curr = m_root;
    while (curr && curr->m_data != key){
        if (curr->m_data > key && curr->m_left == NULL){
            curr->m_left = new elem(key);
            ++m_size;
            return;
        }
        if (curr->m_data < key && curr->m_right == NULL){
            curr->m_right = new elem(key);
            ++m_size;
            return;
        }
        if (curr->m_data > key) curr = curr->m_left;
        else curr = curr->m_right;
    }
}

bool binary_tree::find(int key){                              // поиск
    elem* curr = m_root;
    while (curr && curr->m_data != key){
        if (curr->m_data > key) curr = curr->m_left;
        else curr = curr->m_right;
    }
    return curr != NULL;
}

void binary_tree::erase(int key){
    elem* curr = m_root;
    elem* parent = NULL;
    while (curr && curr->m_data != key){
        parent = curr;
        if (curr->m_data > key){
            curr = curr->m_left;
        }else {
            curr = curr->m_right;
        }
    }
    if (!curr) return;
    if (curr->m_left == NULL){
        if (parent && parent->m_left == curr) parent->m_left = curr->m_right;
        if (parent && parent->m_right == curr) parent->m_right = curr->m_right;
        --m_size;
        delete curr;
        return;
    }
    if (curr->m_right == NULL){
        if (parent && parent->m_left == curr) parent->m_left = curr->m_left;
        if (parent && parent->m_right == curr) parent->m_right = curr->m_left;
        --m_size;
        delete curr;
        return;
    }
    elem* replace = curr->m_right;
    while (replace->m_left) replace = replace->m_left;
    int replace_value = replace->m_data;
    erase(replace_value);
    curr->m_data = replace_value;
}

int main(){
    setlocale(LC_ALL, "russian");
    int val;
    std::cout << "введите значение корневого узла дерева:\n>";
    std::cin >> val;
    binary_tree tr(val);
    int choice;


    while (true) {
        std::cout << "введите:\n1 - для добавления узлов в дерево\n2 - для удаления узла из дерева\n3 - для поиска узла в дереве\n4 - для вывода дерева\n0 - для выхода из программы\n>";

        std::cin >> choice;
        if (choice == 1) {
            if (tr.size() == 0) {
                std::cout << "введите значение корневого узла дерева:\n>";
                std::cin >> val;
                binary_tree tr(val);
            }
            std::cout << "введите значения узлов через пробел, -1 для конца ввода:\n>";
            int temp;
            while (true) {
                std::cin >> temp;
                if (temp != -1)  tr.insert(temp);
                else break;
            }
            std::cout << "\n";
        }
        else if (choice == 2) {
            int temp;
            std::cout << "введите узел для удаления:\n>";
            std::cin >> temp;
            if (tr.find(temp)) tr.erase(temp);
            else std::cout << "такого узла нет\n";
            std::cout << "\n";
        }
        else if (choice == 3) {
            int temp;
            std::cout << "введите узел для поиска:\n>";
            std::cin >> temp;
            if (tr.find(temp)) std::cout << "узел " << temp << " найден\n";
            else std::cout << "узел " << temp << " не найден\n";
            std::cout << "\n";
        }
        else if (choice == 4) {
            if (tr.size() == 0) std::cout << "в дереве нет элементов\n";
            else tr.print();
            std::cout << "\n";
        }
        else if (choice == 0) {
            return 0;
        }
        else std::cout << "некоректный ввод\n\n";
    }
}