#include <iostream>
#include <string>  // для строк
using namespace std;
struct Node  // стрктура дерево
{
    string d;  // узел
    Node *left ;  // ссссылка на левое 
    Node *right ;  // и правое поддеревья
};
Node * first (string d);  // функция формирования корня 
void insert(Node *root, string d); // функция добавления нового элемента
void print_tree (Node *root, int l);  // вывод на экран
void sear (Node *root, string d);   // функция поиска места для вставки
 
 
void main()  // главная функция
{
    string b[] = {"anton","ryc9","petr","olog","anton","tania","gala","badik"};  // массив данных
    Node *root = first(b[0]);  // формирования е 1 жлемента
    for (int i=1; i<8 ; i++) // цикл добавления элементов
        {
            sear(root , b[i]); // функуция поиска места для вставки (внутри вызов функции вставки) 
        }
    print_tree (root, 0); // распечатка дерева
}
 
Node * first (string d) // формирование 1 жлемента дерева
{
    Node *pv = new Node; // создание узла pv типа структура
    pv->d = d;  // данные в узле
    pv->left = 0;  // ссылка на левое
    pv->right = 0; // и правое поддеревья
    return pv;  // возвращаем корень
}
void print_tree (Node *p , int level)  // распечатка дерева  рекурсивная функция обхода дерева с лева на право
{
    if (p)  // пока p
    {
        print_tree (p->left, level +1);  // вызов вывода для левого поддерева
            for (int i=0; i<level; i++ ) 
                    cout << "   "; // уровень
        cout << p->d << endl;  // вывод данных из узла
        print_tree (p->right, level + 1); // ввод правого пооддерева
    }
}
void insert(Node *root, string d)  // функция вставки
{    
    Node *pv = root;  // pv корень
    Node *pnewr = new Node;  // новая структура новое лево
    Node *pnewl = new Node;  // новое право
    string buf = pv->d;  // данные из узла в буфер
    pv->d = "*";  // данные в узле заменяем на знак указателя
    pv->left = pnewl;  // для левог новая структура
    pv->right = pnewr;  // для правого новая структура
    pnewr->d = buf;  // в правое поддерево в узел дынные из буфера
    pnewr->left = 0;  // лево 0
    pnewr->right = 0; // право 0
    pnewl->d = d;  // в правое поддерево в узел новые данные
    pnewl->left = 0;  // лево 0
    pnewl->right = 0;  // право 0
}
void sear (Node *p, string d)  // поиск
{   
    if (p)  //пока p
    {
        sear (p->left, d );  //рекурсия на лево 
        int t = p->d.compare(d);
            if (t == 0) 
            {
                return;
            }
        int pr = 0, se = 0, se1 = 0; // переменные
        int co1 = p->d.find('*'); // смотрим чтобы * не попадалось
        if (  co1 != 0 && t == -1)
            {
                insert(p , d); // вызов вставки
                return;
            }
        sear (p->right, d ); // рекурсия в право
    }
}