tree9

#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; // Изменен на указатель для удобства

    // Создает поддерево
    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;
        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); // Обход правого поддерева
    }
};

int main() {
    tree T;
    vector<int> a = {1, 2, 3, 4, 5, 6, 7,8, 9, 10, 11};
    T.create(a);
    cout << "TRAVERSAL ORDER:\n";
    T.trav(T.main_root);
    cout << endl;

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