---

#include <iostream>
#include <cstdlib>
#include <ctime>

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

ttree* addtree(ttree *proot, int inf) {
    ttree *nl = new ttree{inf, NULL, 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;
}

// Задание №9: подсчёт узлов с ровно одним потомком
int countSingleChild(ttree *p) {
    if (p == NULL) return 0;
    int leftCount = countSingleChild(p->left);
    int rightCount = countSingleChild(p->right);
    bool hasLeft = (p->left != NULL);
    bool hasRight = (p->right != NULL);
    int current = (hasLeft ^ hasRight) ? 1 : 0;
    return leftCount + rightCount + current;
}

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

void printSingleNodes(ttree *p) {
    if (p == NULL) return;
    printSingleNodes(p->left);
    if ((p->left != NULL) ^ (p->right != NULL))
        std::cout << p->inf << " ";
    printSingleNodes(p->right);
}

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

int main() {
    setlocale(LC_ALL, "Russian");
    srand(time(0));
    
    ttree *root = NULL;
    
    std::cout << "Исходные числа: ";
    for (int i = 0; i < 10; i++) {
        int num = rand() % 100;  // 0..99
        std::cout << num << " ";
        root = addtree(root, num);
    }
    
    std::cout << "\nДерево (по возрастанию): ";
    printTree(root);
    
    std::cout << "\nУзлы с одним потомком: ";
    printSingleNodes(root);
    
    int count = countSingleChild(root);
    std::cout << "\nКоличество узлов с ровно одним потомком: " << count << std::endl;
    
    deltree(root);
    return 0;
}