---

#include <iostream>
#include <cstdlib>
#include <ctime>
#include <cmath>
#include <vector>
#include <algorithm>

using namespace std;

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

// Функция создания сбалансированного дерева поиска
ttree* createBalancedTree(int arr[], int start, int end) {
    if (start > end) return NULL;
    int mid = (start + end) / 2;
    ttree *root = new ttree;
    root->inf = arr[mid];
    root->left = createBalancedTree(arr, start, mid - 1);
    root->right = createBalancedTree(arr, mid + 1, end);
    return root;
}

// Добавление нового элемента
ttree* addtree(ttree *proot, int inf) {
    ttree *nl = new ttree;
    nl->inf = inf;
    nl->left = NULL;
    nl->right = NULL;
    if (proot == NULL) return nl;
    
    ttree *ps = proot, *pr;
    bool b;
    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 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 inorder(ttree *p) {
    if (p == NULL) return;
    inorder(p->left);
    cout << p->inf << " ";
    inorder(p->right);
}

// Поиск элемента с заданным ключом
bool search(ttree *p, int key) {
    if (p == NULL) return false;
    if (p->inf == key) return true;
    if (key < p->inf) return search(p->left, key);
    else return search(p->right, key);
}

// Удаление всего дерева
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, *v;
    
    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;
}

// Задание 3: Удаление ветви с вершиной, имеющей заданный ключ
ttree* deleteBranch(ttree *root, int key) {
    if (root == NULL) return NULL;
    if (root->inf == key) {
        deltree(root);
        return NULL;
    }
    if (key < root->inf) {
        if (root->left != NULL && root->left->inf == key) {
            root->left = deltree(root->left);
        } else {
            root->left = deleteBranch(root->left, key);
        }
    } else {
        if (root->right != NULL && root->right->inf == key) {
            root->right = deltree(root->right);
        } else {
            root->right = deleteBranch(root->right, key);
        }
    }
    return root;
}

// Задание 9: Определить число узлов, у которых есть указатель только на одну ветвь
int countSingleChildNodes(ttree *root) {
    if (root == NULL) return 0;
    int count = 0;
    if ((root->left == NULL && root->right != NULL) || 
        (root->left != NULL && root->right == NULL)) {
        count = 1;
    }
    return count + countSingleChildNodes(root->left) + countSingleChildNodes(root->right);
}

// Вспомогательная функция для задания 12: сбор всех значений
void collectValues(ttree *root, vector<int>& values) {
    if (root == NULL) return;
    collectValues(root->left, values);
    values.push_back(root->inf);
    collectValues(root->right, values);
}

// Задание 12: Найти среднее значение всех ключей и узел с ближайшим ключом
void findClosestToAverage(ttree *root, double avg, int &closestKey, double &minDiff) {
    if (root == NULL) return;
    double diff = abs(root->inf - avg);
    if (diff < minDiff) {
        minDiff = diff;
        closestKey = root->inf;
    }
    findClosestToAverage(root->left, avg, closestKey, minDiff);
    findClosestToAverage(root->right, avg, closestKey, minDiff);
}

pair<double, int> task12(ttree *root) {
    vector<int> values;
    collectValues(root, values);
    
    double sum = 0;
    for (int v : values) sum += v;
    double avg = sum / values.size();
    
    int closestKey = values[0];
    double minDiff = abs(values[0] - avg);
    findClosestToAverage(root, avg, closestKey, minDiff);
    
    return {avg, closestKey};
}

// Задание 14: Определить количество узлов в левой ветви дерева
int countLeftBranch(ttree *root) {
    if (root == NULL || root->left == NULL) return 0;
    return 1 + countLeftBranch(root->left) + countNodes(root->left->right);
}

// Вспомогательная функция для подсчета всех узлов поддерева
int countNodes(ttree *root) {
    if (root == NULL) return 0;
    return 1 + countNodes(root->left) + countNodes(root->right);
}

int main() {
    srand(time(0));
    
    // 1. Создание сбалансированного дерева из чисел [-50, 50] с шагом 10
    int arr[] = {-50, -40, -30, -20, -10, 0, 10, 20, 30, 40, 50};
    int n = sizeof(arr) / sizeof(arr[0]);
    ttree *root = createBalancedTree(arr, 0, n - 1);
    
    cout << "Сбалансированное дерево создано из чисел: ";
    for (int i = 0; i < n; i++) cout << arr[i] << " ";
    cout << endl;
    
    // Вывод обходов
    cout << "\nПрямой обход: ";
    preorder(root);
    cout << "\nОбратный обход: ";
    postorder(root);
    cout << "\nСимметричный обход (возрастание): ";
    inorder(root);
    cout << endl;
    
    // Демонстрация основных операций
    cout << "\n=== Демонстрация операций ===" << endl;
    
    // Добавление
    root = addtree(root, 25);
    root = addtree(root, -35);
    cout << "После добавления 25 и -35: ";
    inorder(root);
    cout << endl;
    
    // Поиск
    cout << "Поиск 25: " << (search(root, 25) ? "найден" : "не найден") << endl;
    
    // Удаление
    root = dellist(root, 25);
    cout << "После удаления 25: ";
    inorder(root);
    cout << endl;
    
    // Задание 3: Удаление ветви с вершиной -30
    cout << "\n=== Задание 3: Удаление ветви с ключом -30 ===" << endl;
    root = deleteBranch(root, -30);
    cout << "Дерево после удаления ветви: ";
    inorder(root);
    cout << endl;
    
    // Задание 9: Узлы с одной дочерью
    cout << "\n=== Задание 9: Узлы с одной дочерью ===" << endl;
    cout << "Количество узлов с одной дочерью: " << countSingleChildNodes(root) << endl;
    
    // Задание 12: Среднее и ближайший узел
    cout << "\n=== Задание 12: Ближайший к среднему ===" << endl;
    auto [avg, closest] = task12(root);
    cout << "Среднее значение: " << avg << endl;
    cout << "Ближайший ключ: " << closest << endl;
    
    // Задание 14: Узлы в левой ветви
    cout << "\n=== Задание 14: Левая ветвь ===" << endl;
    cout << "Узлов в левой ветви: " << countLeftBranch(root) << endl;
    
    // Освобождение памяти
    root = deltree(root);
    
    return 0;
}