tree4

#include <iostream>
#include <vector>
using namespace std;

const int inf = 2e9;

struct node {
    node* parent;
    node* l;
    node* r;
    int val;

    node(node* par) : parent(par), l(nullptr), r(nullptr), val(inf) {}
    node() : parent(nullptr), l(nullptr), r(nullptr), val(inf) {}
};

struct tree {
    //vector<int> arr; // используется ТОЛЬКО для инициализации дерева
    node* main_root; // Изменен на указатель для удобства
    int cur_size = 0;

    // Создает поддерево
    node* create_subtree(node* par, int Li, int Ri, const vector <int> &arr) {
        if (Li > Ri) return nullptr; // Проверка на правильные границы

        node* root = new node(par);
        root->val = arr[(Ri + Li) / 2]; // устанавливаем значение корня

        // Создание левого и правого поддеревьев
        root->l = create_subtree(root, Li, (Ri + Li) / 2 - 1, arr);
        root->r = create_subtree(root, (Ri + Li) / 2 + 1, Ri, arr);

        return root; // Возвращаем указатель на созданный узел
    }

    // Инициализация дерева
    void create(const vector <int> &arr) {
        cur_size = arr.size();
        if (arr.size() == 0) {
            main_root = nullptr; // В случае пустого массива
        } else {
            main_root = create_subtree(nullptr, 0, arr.size() - 1, arr);
        }
        cout << "Tree created\n";
    }

    // Обход дерева (in-order)
    void trav(node* root) {
        if (root == nullptr) return; // Проверка на nullptr
        trav(root->l); // Обход левого поддерева
        cout << root->val << " "; // Обработка текущего узла
        trav(root->r); // Обход правого поддерева
    }

    void replace_el(node* root, int Li, int Ri, int i, int x) {
        if (root == nullptr) return;

        int mid = (Li + Ri) / 2;
        if (i == mid) {  // Нашли узел, который нужно заменить
            root->val = x;
            return;
        }

        if (i < mid) {
            replace_el(root->l, Li, mid - 1, i, x);  // Ищем в левом поддереве
        } else {
            replace_el(root->r, mid + 1, Ri, i, x);  // Ищем в правом поддереве
        }
    }
};

int main() {
    tree T;
    vector<int> a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21};
    T.create(a);
    cout << "TRAVERSAL ORDER:\n";
    T.trav(T.main_root); cout << "\n";
    /*T.replace_el(T.main_root, 0, T.cur_size - 1, 0, 999);
    T.trav(T.main_root); cout << "\n";
    T.replace_el(T.main_root, 0, T.cur_size - 1, 18, 999);
    T.trav(T.main_root); cout << "\n";*/
    for (int i = 0; i < 21; ++i) {
        T.replace_el(T.main_root, 0, T.cur_size - 1, i, 999);
        T.trav(T.main_root); cout << "\n";
    }

    // Освобождение памяти
    // Здесь может быть реализована функция для удаления дерева и освобождения памяти
    return 0;
}