tree8

#include <iostream>
#include <sstream>
#include <exception>
#include <cmath>
#include <unordered_set>
#include <vector>
#include <unordered_map>
#include <algorithm>
using namespace std;

const int inf = 2e9;

struct node{
    node* self;
    node* parent;
    node* l;
    node* r;
    int val;
    node(node *par) : parent(par), l(nullptr), r(nullptr), self(this), val(inf) {}
    node() : parent(nullptr), l(nullptr), r(nullptr), self(this),val (inf) {}
    node(node *par, node *L, node *R) : parent(par), l(L), r(R), self(this), val(inf) {}
};

struct tree{
    vector <int> arr; //используется ТОЛЬКО для инициализациидерева
    node main_root;
    node create_subtree(node* par, int Li, int Ri) {
        /*Ri == Li + 2 - работает по алгоритмы
        Ri == Li + 1 - особ случ
        Ri == Li - особ случ*/
        node root(par);
        root.val = this->arr[(Ri + Li) / 2];
        cout << "creating\n";
        cout << "Li Ri: " << Li << ' ' << Ri << "\n";
        cout << root.val << "\n";
        node left_root;
        node right_root;
        if (Ri == Li) {
            return root;
        }
        if (Ri == Li + 1) { //Ri - root, Li - left_root
            root.val = this->arr[(Ri + Li) / 2 + 1];
            cout << "change val: " << root.val << "\n";
            left_root = create_subtree(root.self, Li, Li);
            root.l = left_root.self;
            return root;
        }
        cout << "\n";
        left_root = create_subtree(root.self, Li, (Ri + Li) / 2 - 1);
        right_root = create_subtree(root.self, (Ri + Li) / 2 + 1, Ri);
        root.l = left_root.self;
        root.r = right_root.self;
        return root;
    }
    void create(vector <int> a) {
        arr = a;
        if (a.size() == 0) {
            return;
        }
        int len = a.size();
        main_root = create_subtree(nullptr, 0, len - 1);
        cout << "created\n";
        return;
    }
    /*node find_first(node  v) {
        node res = v;
        while (v.l != nullptr) {
            res = &(res.l);
        }
        return res;
    }
    node find_next(node v) {
        return;
    }*/
    void trav(node root) {
        cout << "trav\n";
        cout << root.val << "\n";
        if (root.l == nullptr && root.r == nullptr) {
            cout << root.val << " ";
            return;
        }
        if (root.l != nullptr) {
            trav(*(root.l));
        }
        cout << root.val << " ";
        if (root.r != nullptr) {
            trav(*(root.r));
        }
    }
    void insert_after(node v) { //а insert_defore надо?
        return;
    }
};

int main() {
    tree T;
    vector <int> a = {1, 2, 3, 4, 5};
    T.create(a);
    cout << "TRAVERSAL ORDER\n";
    T.trav(T.main_root);
}