Сиаод 3 Вариант 7

#include <iostream>
using namespace std;

struct node {
    unsigned char data;
    node* left, * right;
    unsigned char height;
    int level;
    node(char in) { data = in; left = right = NULL; height = 1; level = 0; }
};

void Print(node* Tree, int l) {
    int i;
    if (Tree != NULL) {
        Print((*Tree).right, l + 1);

        for (i = 1; i <= l; i++) cout << "   "; {
            cout << Tree->data << endl;
        }
        Print(((*Tree).left), l + 1);
    }
}

void print(node* t, int u) {
    //cout << "PRINT!\n";
    if (t == NULL) {
        //`cout << "T = NULL!\n";
        return;
    }
    else {
        print(t->left, u++);
        for (int i = 0; i < u; i++) cout << "|";
        cout << t->data << endl;
        u--;
    };
    print(t->right, u++);
}

unsigned char height(node* t) {
    if (t) {
        return t->height;
    }
    else {
        return 0;
    }
}

void fixheight(node* p) {
    unsigned char hl = height(p->left);
    unsigned char hr = height(p->right);
    if (hl > hr) p->height = hl + 1;
    else p->height = hr + 1;
}

int bf(node* p) {
    return height(p->right) - height(p->left);
}

node* rotateright(node* p) {
    node* q = p->left;
    p->left = q->right;
    q->right = p;
    fixheight(p);
    fixheight(q);
    return q;
}

node* rotateleft(node* q) {
    node* p = q->right;
    q->right = p->left;
    p->left = q;
    fixheight(q);
    fixheight(p);
    return p;
}

node* balance(node* p) {
    //cout << "BALANCE!\n";
    fixheight(p);
    if (bf(p) == 2) {
        if (bf(p->right) < 0) p->right = rotateright(p->right);
        return rotateleft(p);
    }
    if (bf(p) == -2) {
        if (bf(p->left) > 0) p->left = rotateleft(p->left);
        return rotateright(p);
    }
    return p;
}

node* push(unsigned char in, node** t) {
    if ((*t) == NULL) {
        (*t) = new node(in); return balance((*t));
    }
    if (in < (*t)->data) { (*t)->left = push(in, &(*t)->left); }
    else { (*t)->right = push(in, &(*t)->right);;
        }
    return balance((*t));
}

void leveller(node* t, int x) {
    t->level = x;
    if (t->left != NULL)
    {
        leveller(t->left, x + 1);
    }
    if (t->right != NULL)
    {
        leveller(t->right, x + 1);
    }
}

void search(node* root, unsigned char key) {
    leveller(root, 0);
    if (!root) return;
    while (root->data != key) {
        if (key < root->data)  root = root->left;
        else root = root->right;
        if (root == NULL) break;
    }
    cout << " Уровень узла " << key << " = " << root->level << endl;
}

void leftsum(node* t) {
    int count = 0;
    node* tmp = t;
    while (tmp != NULL) {
        count++;
        tmp = tmp->left;
    } count--;
    cout << "Количество символов в левой ветви = " << count << endl;
}

int main() {
    setlocale(0, "");
    int n;
    unsigned char s;
    node* tree = NULL;
    cout << "Введите количество элементов > "; cin >> n;
    for (int i = 0; i < n; i++) {
        cout << "Введите число >";
        cin >> s;
        push(s, &tree);
    }
    cout << "Дерево:\n";
    Print(tree, 0);
    n = -1;
    cout << "\nЧтобы вывести дерево вертикально, введите 1.\nЧтобы определить уровень, на котором находится нужное значение, введите 2.\n Чтобы Определить количество цифр в левом поддереве исходного дерева, введите 3.\nЧтобы завершить выполнение программы, введите 0.\n";
    while (n != 0) {
        cin >> n;
        switch (n) {
        case 1:
            print(tree, 0);
            break;
        case 2:
            cout << "Введите значение для поиска: ";
            s = 0;
            cin >> s;
            search(tree, s);
            break;
        case 3:
            leftsum(tree);
            break;
        default:
            break;
        }
    }
    return 0;
}