---

#include <iostream>
#include <ctime>
#include <cstdlib>
using namespace std;

struct ttree {
    int inf;
    ttree *left;
    ttree *right;
};

ttree *addtree(ttree *proot, int inf) {
    ttree *nl, *pr = proot, *ps;
    bool b = false;
    nl = new ttree;
    nl->inf = inf;
    nl->left = NULL;
    nl->right = NULL;
    if (proot == NULL) return nl;
    ps = proot;
    while (ps != NULL) {
        pr = ps;
        b = (inf < ps->inf);
        if (b) ps = ps->left;
        else ps = ps->right;
    }
    if (b) pr->left = nl;
    else pr->right = nl;
    return proot;
}

void wrtree(ttree *p) {
    if (p == NULL) return;
    wrtree(p->left);
    cout << p->inf << " ";
    wrtree(p->right);
}

void preorder(ttree *p) {
    if (p == NULL) return;
    cout << p->inf << " ";
    preorder(p->left);
    preorder(p->right);
}

void postorder(ttree *p) {
    if (p == NULL) return;
    postorder(p->left);
    postorder(p->right);
    cout << p->inf << " ";
}

void poisktree(ttree *p, int key, bool &b, int &inf) {
    if ((p != NULL) && (b != true)) {
        if (p->inf != key) {
            poisktree(p->left, key, b, inf);
            poisktree(p->right, key, b, inf);
        } else {
            b = true;
            inf = p->inf;
        }
    }
}

int poiskmaxtree(ttree *p) {
    while (p->right != NULL) p = p->right;
    return p->inf;
}

ttree *deltree(ttree *p) {
    if (p == NULL) return NULL;
    deltree(p->left);
    deltree(p->right);
    delete p;
    return NULL;
}

ttree *dellist(ttree *proot, int inf) {
    ttree *ps = proot, *pr = proot, *w = NULL, *v = NULL;
    while ((ps != NULL) && (ps->inf != inf)) {
        pr = ps;
        if (inf < ps->inf) ps = ps->left;
        else ps = ps->right;
    }
    if (ps == NULL) return proot;
    if ((ps->left == NULL) && (ps->right == NULL)) {
        if (ps == pr) {
            delete ps;
            return NULL;
        }
        if (pr->left == ps) pr->left = NULL;
        else pr->right = NULL;
        delete ps;
        return proot;
    }
    if (ps->left == NULL) {
        if (ps == pr) {
            ps = ps->right;
            delete pr;
            return ps;
        }
        if (pr->left == ps) pr->left = ps->right;
        else pr->right = ps->right;
        delete ps;
        return proot;
    }
    if (ps->right == NULL) {
        if (ps == pr) {
            ps = ps->left;
            delete pr;
            return ps;
        }
        if (pr->left == ps) pr->left = ps->left;
        else pr->right = ps->left;
        delete ps;
        return proot;
    }
    w = ps->left;
    if (w->right == NULL) {
        w->right = ps->right;
    } else {
        while (w->right != NULL) {
            v = w;
            w = w->right;
        }
        v->right = w->left;
        w->left = ps->left;
        w->right = ps->right;
    }
    if (ps == pr) {
        delete ps;
        return w;
    }
    if (pr->left == ps) pr->left = w;
    else pr->right = w;
    delete ps;
    return proot;
}

ttree *build_balanced(int arr[], int start, int end) {
    if (start > end) return NULL;
    int mid = start + (end - start) / 2;
    ttree *root = new ttree;
    root->inf = arr[mid];
    root->left = build_balanced(arr, start, mid - 1);
    root->right = build_balanced(arr, mid + 1, end);
    return root;
}

void countLeavesLevel(ttree *p, int level, int leaves[]) {
    if (p == NULL) return;
    if (p->left == NULL && p->right == NULL) {
        leaves[level]++;
    }
    countLeavesLevel(p->left, level + 1, leaves);
    countLeavesLevel(p->right, level + 1, leaves);
}

int maxLevel(ttree *p) {
    if (p == NULL) return 0;
    int left = maxLevel(p->left);
    int right = maxLevel(p->right);
    return (left > right ? left : right) + 1;
}

void countLeavesOnLevels(ttree *root) {
    if (root == NULL) {
        cout << "The tree is empty.\n";
        return;
    }
    int levels = maxLevel(root);
    int *leaves = new int[levels + 1]();
    countLeavesLevel(root, 1, leaves);
    for (int i = 1; i <= levels; i++) {
        cout << "Level " << i << ": " << leaves[i] << " leaves\n";
    }
    delete[] leaves;
}

int main() {
    srand(time(0));

    const int N = 10;
    int vals[N];
    bool used[101] = {false};

    for (int i = 0; i < N; ++i) {
        int num;
        do {
            num = rand() % 101 - 50; // диапазон -50..50
        } while (used[num + 50]);
        used[num + 50] = true;
        vals[i] = num;
    }

    for (int i = 0; i < N - 1; ++i)
        for (int j = i + 1; j < N; ++j)
            if (vals[i] > vals[j]) {
                int t = vals[i];
                vals[i] = vals[j];
                vals[j] = t;
            }

    ttree *root = build_balanced(vals, 0, N - 1);

    cout << "Исходное сбалансированное дерево:\n";
    cout << "Прямой обход: "; preorder(root); cout << "\n";
    cout << "По возрастанию: "; wrtree(root); cout << "\n";
    cout << "Обратный обход: "; postorder(root); cout << "\n";

    cout << "\nДобавляем элемент 55\n";
    root = addtree(root, 55);
    cout << "По возрастанию: "; wrtree(root); cout << "\n";

    cout << "\nУдаляем элемент " << vals[N/2] << "\n";
    root = dellist(root, vals[N/2]);
    cout << "По возрастанию: "; wrtree(root); cout << "\n";

    cout << "\nИщем элемент " << vals[0] << ":\n";
    bool found = false;
    int res;
    poisktree(root, vals[0], found, res);
    if (found) cout << "Найден: " << res << "\n";
    else cout << "Не найден\n";

    cout << "\n--- Число листьев на каждом уровне дерева ---\n";
    countLeavesOnLevels(root);

    root = deltree(root);
    return 0;
}