---

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

struct ttree
{
    string inf;
    ttree *left;
    ttree *rigth;
};

ttree *addtree(ttree *proot, const string &inf)
{
    ttree *nl, *pr = NULL, *ps;
    bool b = false;

    nl = new ttree;
    nl->inf = inf;
    nl->left = NULL;
    nl->rigth = 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->rigth;
    }

    if (b) pr->left = nl;
    else pr->rigth = nl;

    return proot;
}

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

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

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

bool poisktree(ttree *p, const string &key)
{
    if (p == NULL) return false;
    if (p->inf == key) return true;
    if (key < p->inf) return poisktree(p->left, key);
    return poisktree(p->rigth, key);
}

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

int countStartsWith(ttree *p, char letter)
{
    if (p == NULL) return 0;
    int count = 0;
    if (!p->inf.empty() && p->inf[0] == letter) count = 1;
    return count + countStartsWith(p->left, letter) + countStartsWith(p->rigth, letter);
}

void addBalanced(ttree *&root, string a[], int l, int r)
{
    if (l > r) return;
    int m = (l + r) / 2;
    root = addtree(root, a[m]);
    addBalanced(root, a, l, m - 1);
    addBalanced(root, a, m + 1, r);
}

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

    ttree *proot = NULL;
    string a[10] = {"apple", "banana", "orange", "grape", "apricot", "pear", "peach", "plum", "avocado", "melon"};

    for (int i = 0; i < 9; i++)
    {
        for (int j = i + 1; j < 10; j++)
        {
            if (a[i] > a[j])
            {
                string t = a[i];
                a[i] = a[j];
                a[j] = t;
            }
        }
    }

    addBalanced(proot, a, 0, 9);

    cout << "Список слов: ";
    for (int i = 0; i < 10; i++) cout << a[i] << " ";
    cout << endl;

    cout << "Прямой обход: ";
    pretree(proot);
    cout << endl;

    cout << "Обратный обход: ";
    posttree(proot);
    cout << endl;

    cout << "В порядке возрастания: ";
    wrtree(proot);
    cout << endl;

    char letter = 'a';
    cout << "Число слов, начинающихся с буквы '" << letter << "': " << countStartsWith(proot, letter) << endl;

    string key = "peach";
    if (poisktree(proot, key)) cout << "Слово " << key << " найдено" << endl;
    else cout << "Слово " << key << " не найдено" << endl;

    proot = deltree(proot);
    return 0;
}