---

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

struct Node {
    int key;
    Node* left;
    Node* right;
    int height;
    Node(int k) : key(k), left(nullptr), right(nullptr), height(1) {}
};

int height(Node* n) { return n ? n->height : 0; }
int bfactor(Node* n) { return n ? height(n->left) - height(n->right) : 0; }
void fixHeight(Node* n) {
    if (n) n->height = 1 + max(height(n->left), height(n->right));
}

Node* rotateRight(Node* p) {
    Node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixHeight(p);
    fixHeight(q);
    return q;
}

Node* rotateLeft(Node* p) {
    Node* q = p->right;
    p->right = q->left;
    q->left = p;
    fixHeight(p);
    fixHeight(q);
    return q;
}

Node* balance(Node* p) {
    fixHeight(p);
    if (bfactor(p) == 2) {
        if (bfactor(p->left) < 0) p->left = rotateLeft(p->left);
        return rotateRight(p);
    }
    if (bfactor(p) == -2) {
        if (bfactor(p->right) > 0) p->right = rotateRight(p->right);
        return rotateLeft(p);
    }
    return p;
}

Node* insert(Node* p, int key) {
    if (!p) return new Node(key);
    if (key < p->key) p->left = insert(p->left, key);
    else if (key > p->key) p->right = insert(p->right, key);
    else return p;
    return balance(p);
}

void deleteSubtree(Node* p) {
    if (!p) return;
    deleteSubtree(p->left);
    deleteSubtree(p->right);
    delete p;
}

// Вывод дерева с отступами (чтобы видеть структуру)
void printTree(Node* p, int level = 0, char dir = ' ') {
    if (!p) return;
    printTree(p->right, level + 1, 'R');
    for (int i = 0; i < level; i++) cout << "    ";
    cout << dir << "--" << p->key << endl;
    printTree(p->left, level + 1, 'L');
}

// Задание 5: подсчёт узлов с ровно одним потомком
int countOneChild(Node* p) {
    if (!p) return 0;
    int leftCount = countOneChild(p->left);
    int rightCount = countOneChild(p->right);
    bool hasOneChild = (p->left == nullptr) != (p->right == nullptr);
    return leftCount + rightCount + (hasOneChild ? 1 : 0);
}

int main() {
    srand(time(0));
    Node* root = nullptr;

    // Создаём дерево из 10 случайных чисел [-50, 50]
    cout << "Создание дерева из 10 случайных чисел:\n";
    for (int i = 0; i < 10; i++) {
        int val = rand() % 101 - 50;
        root = insert(root, val);
    }

    cout << "\nСтруктура дерева (R - правый, L - левый):\n";
    printTree(root);

    cout << "\nДерево (возрастание): ";
    inorder(root);  // нужно добавить inorder, если её нет — добавлю ниже
    cout << endl;

    int result = countOneChild(root);
    cout << "\nКоличество узлов с ровно одним потомком: " << result << endl;

    deleteSubtree(root);
    return 0;
}