---

#include <iostream>
#include <cstring>
using namespace std;

struct ttree {
    char inf[100];
    ttree *left;
    ttree *right;
};

ttree *addtree(ttree *proot, char *inf) {
    ttree *nl = new ttree;
    strcpy(nl->inf, inf);
    nl->left = NULL;
    nl->right = NULL;
    if (proot == NULL) return nl;
    ttree *ps = proot, *pr;
    bool b;
    while (ps != NULL) {
        pr = ps;
        b = (strcmp(inf, ps->inf) < 0);
        if (b) ps = ps->left;
        else ps = ps->right;
    }
    if (b) pr->left = nl;
    else pr->right = nl;
    return proot;
}

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

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

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

bool searchtree(ttree *p, char *key, char *inf) {
    if (p == NULL) return false;
    if (strcmp(p->inf, key) == 0) {
        strcpy(inf, p->inf);
        return true;
    }
    if (strcmp(key, p->inf) < 0) return searchtree(p->left, key, inf);
    else return searchtree(p->right, key, inf);
}

int count_chars(ttree *p) {
    if (p == NULL) return 0;
    return strlen(p->inf) + count_chars(p->left) + count_chars(p->right);
}

ttree *delete_node(ttree *proot, char *inf) {
    ttree *ps = proot, *pr = proot, *w, *v;
    while ((ps != NULL) && (strcmp(ps->inf, inf) != 0)) {
        pr = ps;
        if (strcmp(inf, ps->inf) < 0) ps = ps->left;
        else ps = ps->right;
    }
    if (ps == NULL) return proot;
    if ((ps->left == NULL) && (ps->right == NULL)) {
        if (ps == pr) {
            delete ps;
            return NULL;
        }
        if (pr->left == ps) pr->left = NULL;
        else pr->right = NULL;
        delete ps;
        return proot;
    }
    if (ps->left == NULL) {
        if (ps == pr) {
            ps = ps->right;
            delete pr;
            return ps;
        }
        if (pr->left == ps) pr->left = ps->right;
        else pr->right = ps->right;
        delete ps;
        return proot;
    }
    if (ps->right == NULL) {
        if (ps == pr) {
            ps = ps->left;
            delete pr;
            return ps;
        }
        if (pr->left == ps) pr->left = ps->left;
        else pr->right = ps->left;
        delete ps;
        return proot;
    }
    w = ps->left;
    if (w->right == NULL) {
        w->right = ps->right;
    } else {
        while (w->right != NULL) {
            v = w;
            w = w->right;
        }
        v->right = w->left;
        w->left = ps->left;
        w->right = ps->right;
    }
    if (ps == pr) {
        delete ps;
        return w;
    }
    if (pr->left == ps) pr->left = w;
    else pr->right = w;
    delete ps;
    return proot;
}

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

int main() {
    ttree *root = NULL;
    char strings[][100] = {"hello", "world", "tree", "binary", "search", "string", "count", "chars", "lab", "work"};
    for (int i = 0; i < 10; i++) {
        root = addtree(root, strings[i]);
    }

    cout << "Прямой обход (возрастание): ";
    wrtree(root);
    cout << endl;

    cout << "Обратный обход (убывание): ";
    wrtree_desc(root);
    cout << endl;

    cout << "Обход в порядке возрастания: ";
    wrtree(root);
    cout << endl;

    int total_chars = count_chars(root);
    cout << "Количество символов во всех строках дерева: " << total_chars << endl;

    char searchKey[100] = "binary";
    char foundInf[100];
    if (searchtree(root, searchKey, foundInf))
        cout << "Найдена строка: " << foundInf << endl;
    else
        cout << "Строка " << searchKey << " не найдена" << endl;

    char deleteKey[100] = "search";
    cout << "Удаление узла со строкой: " << deleteKey << endl;
    root = delete_node(root, deleteKey);

    cout << "Прямой обход после удаления: ";
    wrtree(root);
    cout << endl;

    total_chars = count_chars(root);
    cout << "Количество символов после удаления: " << total_chars << endl;

    root = deltree(root);
    return 0;
}