for Nastya

template <typename T>
struct treenode {
    T data;
    int kids;
    treenode *leftkid;
    treenode *rightkid;


};

template <typename T>
class tree {
    treenode<T> *root;

    void destroytree(treenode<T> *node) {
        if (node != nullptr) {
            destroytree(node->leftkid);
            destroytree(node->rightkid);
            delete node;
        }
    }

    void rootRightLeft_print(treenode<T> *node) {
        if (node != nullptr) {
            cout << node->data << " ";
            rootRightLeft_print(node->rightkid);
            rootRightLeft_print(node->leftkid);
        }
    }

    void leftRootRight_print(treenode<T> *node) {
        if (node != nullptr) {
            leftRootRight_print(node->leftkid);
            cout << node->data << " ";
            leftRootRight_print(node->rightkid);
        }
    }

    int get_value_of_function (treenode<void*> *node) {
        return ((int(*)(int))(node->data))(5);
    }

    void print_value_of_function (treenode<void*> *node) {
        if (node != nullptr) {
            cout << get_value_of_function(node) << endl;
            print_value_of_function(node->leftkid);
            print_value_of_function(node->rightkid);
        }
    }


    // 1. map
    void map (treenode<T> *node, T value) {
        if (node != nullptr) {
            node->data = value;
            map (node->leftkid, value);
            map (node->rightkid, value);
        }
    }

    bool check (treenode<string> *node) {
        if ((node->data).length() < 5) return true;
        else return false;
    }

    bool check (treenode<void*> *node) {
        if (get_value_of_function(node) < 10) return true;
        else return false;
    }

    // 2. where
    void where (treenode<T> *node, tree<T> *new_tree) { // УКАЗАТЕЛЬ  на новое дерево
        if (node != nullptr) {
            if (check(node)) {
                new_tree->insert(node->data);
            }
            where (node->leftkid, new_tree);
            where (node->rightkid, new_tree);
        }
    }


    // 3. слияние
    void merge_trees (treenode<T> *node_of_1st_tree, tree<T> *second_tree) {
        // к дереву second_tree прибавляем все элементы дерева для к-ого вызвана ф-ия
        if (node_of_1st_tree != nullptr) {
            second_tree->insert(node_of_1st_tree->data);
            merge_trees(node_of_1st_tree->leftkid, second_tree);
            merge_trees(node_of_1st_tree->rightkid, second_tree);
        }
    }

    // 4. извлечение поддерева по заданному элементу
    void subtree_extraction (treenode<T> *node, T value, tree<T> *res_tree, int *flag) {
        if (node != nullptr && *flag == 0) {
            if(node->data == value) {
                res_tree->root = node;
                *flag = 1;
            }
            subtree_extraction(node->leftkid, value, res_tree, flag);
            subtree_extraction(node->rightkid, value, res_tree, flag);
        }
    }


    // 5. поиск элемента на вхождение
    void if_element_contain (treenode<T> *node, T value, bool* check_ptr) {
        if (node != nullptr && *check_ptr == false) {
            if (node->data == value) {
                *check_ptr = true;
            }
            if_element_contain(node->leftkid, value, check_ptr);
            if_element_contain(node->rightkid, value, check_ptr);
        }
    }


    void print_mentioned_level (treenode<T> *node, int level) {
        if (node == nullptr) return;
        else {
            print_mentioned_level(node->leftkid, level - 1);
            if (level == 0) cout << node->data << " ";
            print_mentioned_level (node->rightkid, level - 1);
        }
    }

    void compare_trees(treenode<T> *first, treenode<T> *second, bool *if_same) {
        if (second != nullptr) {
            if ((first == nullptr) || (first->data != second->data)) *if_same = 0;
            if ((*if_same != 0)&&(first != nullptr)) {
                compare_trees(first->leftkid, second->leftkid, if_same);
                compare_trees(first->rightkid, second->rightkid, if_same);
            }
        }
    }

    void if_tree_contain(treenode<T> *big_node, treenode<T> *small_node, bool *check_ptr, bool *if_same) {
        if (big_node != nullptr) {
            if ((big_node->data == small_node->data) && (!(*check_ptr))) {
                compare_trees(big_node, small_node, if_same);
                if (*if_same) {
                    *check_ptr = 1;
                }
            }
            if (!(*check_ptr)) {
                if_tree_contain(big_node->leftkid, small_node, check_ptr, if_same);
                if_tree_contain(big_node->rightkid, small_node, check_ptr, if_same);
            }
        }
    }







////////////////////////////////////////////////////////////

public:
    tree() {
        root = nullptr;
    }

    ~tree() {
        cout << "destructor" << endl;
        destroytree(root);
    }

    void insert(T data);

    void rootRightLeft_print() { // КПЛ обход
        cout << "КПЛ обход ->" << endl;
        rootRightLeft_print(root);
        cout << endl;
        cout << endl;
    }
    void leftRootRight_print() {    // ЛКП обход
        cout << "ЛКП обход ->" << endl;
        leftRootRight_print(root);
        cout << endl;
        cout << endl;
    }
    void map (T value) {
        map (root, value);
    }
    void print_value_of_function () {
        cout << "Значения функций от x=5 " << endl;
        print_value_of_function (root);
    }
    void where (tree<T> *new_tree) {
        where (root, new_tree);
    }
    void merge_trees (tree<T> *second_tree) { //
        merge_trees(root, second_tree);
    }
    void subtree_extraction (T value, tree<T> *res_tree) {
        int *flag = new int; *flag = 0;
        subtree_extraction(root, value, res_tree, flag);
        delete flag;
    }
    bool if_element_contain (T value) {
        bool* check_ptr = new bool; *check_ptr = false;
        if_element_contain(root, value, check_ptr);
        bool check = *check_ptr;
        delete check_ptr;
        return check;
    }

    void print_by_levels () {
        cout << "Печать по строкам -> " << endl;

        int max_level = 0;
        while (pow(2, max_level) - 2 <= root->kids)  max_level ++;
        for (int i = 0; i < max_level; i ++) {
            print_mentioned_level(root, i);
            cout << endl;
        }
    }

    bool if_tree_contain(tree<T> *smallTree) {
        bool *check_ptr = new bool; *check_ptr = 0;
        bool *if_same = new bool; *if_same = 1;
        if_tree_contain(root, smallTree->root,check_ptr, if_same);
        delete if_same;
        bool to_return = *check_ptr;
        delete check_ptr;
        return to_return;
    }



    //////////////////
    void set_tree () {
        cout << "Введите количество элементов в дереве: ";
        int amount_of_elements;
        do {cin >> amount_of_elements; } while (amount_of_elements < 1);
        cout << "Введите " << amount_of_elements << " строки: " << endl;
        for (int i = 0; i < amount_of_elements; i ++) {
            cout << "  " << i + 1 << ": " ;
            string str; cin >> str;
            this->insert(str);
        }
    }

    void set_function_tree (void **ptr) {
        cout << "Список функций: " << endl;
        cout << " 1: x * 2\n 2: x^3\n 3: x + 1\n 4: x^2\n 5: x + 2\n";
        cout << "Введите количество элементов в дереве: ";
        int amount_of_elements;
        do {cin >> amount_of_elements; } while (amount_of_elements < 1);
        cout << "Выберите " << amount_of_elements << " функций из списка выше " << endl;
        for (int i = 0; i < amount_of_elements; i ++) {
            int func_number;
            do {
                cout << "  " << i + 1 << ": " ;
                cin >> func_number;
            } while (func_number != 1 && func_number != 2 && func_number != 3 && func_number != 4 && func_number != 5);
            this->insert(ptr[func_number-1]);
        }
    }


};