123

#include <iostream>
#include <iomanip>
#include <fstream>
#include <string.h>
#include <windows.h>
using namespace std;


struct Countries {
    string name; //название страны
    string capital; //столица
    double population; //численность населения
    double populationPercent; //процент населения от общемирового
    double area; //площадь
};


struct node {
    Countries countries;
    node* left, * right;
};


//очередь
struct qnode {
    Countries info;
    qnode* next;
};


//добавляем элемент в очередь
void push(qnode** start, qnode** end, Countries& d) {
    qnode* p = new qnode;
    p->info = d;
    p->next = nullptr;
    if (*end) {
        (*end)->next = p;
    }
    else {
        (*start) = p;
    }
    *end = p;
}

void inputcountries(Countries& countries)//ввод данных о студенте
{
    cout << "Info aboit one country" << endl;
//    cout << "Введите название страны: " << endl;
    cin >> countries.name;
//    cout << "Введите столицу:" << endl;
    cin >> countries.capital;
//    cout << "Введите численность населения:" << endl;
    cin >> countries.population;
//    cout << "Введите процент населения от общемирового:" << endl;
    cin >> countries.populationPercent;
//    cout << "Введите площадь:" << endl;
    cin >> countries.area;

}


//ввод массива с клавиатуры
void inputMasFromKeyboard(qnode*& s, qnode*& e, unsigned int& size)
{
    cout << "size" << endl;
    cin >> size;
    if (size == 0) return;
    int i;
    for (i = 0; i < size; i++)
    {

        cout << "info:" << endl;
        Countries cs;
        inputcountries(cs);
        push(&s, &e, cs);
//        s = s->next;
    }
}

void printStudent(Countries countries)//печать данных о стране
{
    cout << left << setw(10) << countries.name << setw(15) << countries.capital << setw(10) << countries.population << setw(9)
         << countries.populationPercent << setw(5) << countries.area << endl;;

}

void printMas(qnode* q1, unsigned int size)
{
    if (!size) return;
    cout << "our country array:" << endl;
    cout << left << setw(10) << "a" << setw(15) << "b" << setw(10) << "c" << setw(9)
         << "d" << setw(5) << "e" << endl;
    for (int i = 0; i < size; i++)
    {
        printStudent(q1->info);
        q1 = q1->next;
    }
}


void insert(node** p, Countries countries) // добавление узла в дерево поиска
{
    if (*p == NULL)
    { //создаём новый узел дерева на найденном месте
        *p = new node;
        (*p)->countries = countries;
        (*p)->left = NULL;
        (*p)->right = NULL;
    }
    else
    {
        if (countries.name < (*p)->countries.name) insert(&(*p)->left, countries);
        if (countries.name > (*p)->countries.name) insert(&(*p)->right, countries);
    }
}


// распечатка дерева в симметричном порядке
void printsim(const node* p)
{
    if (p != NULL)
    {
        printsim(p->left);
        printStudent(p->countries);
        printsim(p->right);
    }
}
void clear(node** p) // очистка дерева
{
    if ((*p) != NULL)
    {
        clear(&(*p)->left);
        clear(&(*p)->right);
        delete* p;
        *p = NULL;
    }
}


//функция создания деревьев из массива
void createTrees(qnode* q1, unsigned int size, node** root1, node** root2)
{
    if (!size) return;
    for (int i = 0; i < size; i++)
    {
        if (q1->info.population > 100000000) insert(root1, q1->info);
        else insert(root2, q1->info);
        q1 = q1->next;
    }
}



// высота дерева
int height(const node* p)
{
    if (p == NULL) return 0;
    int h1 = height(p->left);//считаем высоту левого поддерева
    int h2 = height(p->right);//считаем высоту правого поддерева
    if (h1 >= h2) return h1 + 1;//возвращаем высоту большего из них+1 - так как добавляем наш узел
    return h2 + 1;
}





double sayminarea(const node* p) {
    if (p != NULL)
    {

        double s1 = sayminarea(p->left); // печатаем левое поддерево
        double s2 = sayminarea(p->right); // печатаем правое поддерево
        return min(p->countries.area, min(s1, s2)); // минимальная площадь поддеревьев.
    }

    return 100000000; //
}
int saymaxlevel(const node* p, string s) {
    //height

    if (p != NULL)
    {

        int s1 = saymaxlevel(p->left, s); // печатаем левое поддерево
        int s2 = saymaxlevel(p->right, s); // печатаем правое поддерево
        if (p->countries.name[0] == s[0]) {
            return max(height(p), max(s1, s2)); // минимальная площадь поддеревьев
        }
        return max(s1, s2);
    }
    return 0;

}

// очистка очереди
void clear(qnode** pbeg)
{
    qnode* temp;
    while (*pbeg != nullptr)
    {
        temp = (*pbeg)->next; //устанавливаем temp на следующий узел
        delete* pbeg; // удаляем текущий узел
        *pbeg = temp; // устанавливаем указатель начала pbeg на temp
    }
}

int main() {
    SetConsoleCP(1251);
    SetConsoleOutputCP(1251);
    unsigned int size = 0;
    qnode* s1 = NULL, * e1 = NULL;
    inputMasFromKeyboard(s1, e1, size);

    if (size) {

        node* root1 = NULL, * root2 = NULL;
        printMas(s1, size);
        cout << endl;

        createTrees(s1, size, &root1, &root2);

        cout << "first in simm" << endl;
        printsim(root1);
        cout << endl;
        cout << "second in simm" << endl;
        printsim(root2);
        cout << endl;
        // ------------ задача 5--------------

        cout << "min array from 1 tree: " << endl;
        sayminarea(root1);
        // ------------ задача 6--------------
        string s;
        cout << "insert letter  " << endl;
        cin >> s;
        cout << "max level from 2 tree:  " << endl;
        cout << saymaxlevel(root2, s) << endl;


        // ------------ задача 7--------------

        clear(&root1);
        if (!root1) cout << "cleared!" << endl;
        clear(&root2);
        if (!root2) cout << "cleared!" << endl;


        clear(&s1);
    }
    else cout << "Размер массива равен 0" << endl;
    return 0;
}
/*
 *
 *
 *
 *
 rsssia    m1skow         1.488e+081.94     1705.2rsssia    m1skow         1.488e+081.94     1705.2

 */