#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) {
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);
root->r = create_subtree(root, (Ri + Li) / 2 + 1, Ri);
return root; // Возвращаем указатель на созданный узел
}
// Инициализация дерева
void create(vector<int> a) {
arr = a;
cur_size = a.size();
if (a.size() == 0) {
main_root = nullptr; // В случае пустого массива
} else {
main_root = create_subtree(nullptr, 0, arr.size() - 1);
}
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;
}