include stdlib include stdio include conio include string include wind

#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
#include <string.h>
#include <windows.h>
#include <locale>

struct rec
{
    rec *l, *r;
    int n;
    int inf;
};

void add(rec **root, int info)  // добавление элемента в дерево
{
    rec *cur, *tree;

    //если дерево не существует
    if (!*root)
    {
        if (!(cur = (rec *)calloc(1, sizeof(rec))))
            return;
        *root = cur;
        cur->inf = info;
        cur->n = 1;
        return;
    }

    tree = *root;

    // нахождение элемента для добавления
    do
    {
        // если такой элемент уже есть, то увеличиваем счетчик
        if (info == tree->inf)
        {
            tree->n++;
            return;
        }
        else
        {
            if (info < tree->inf)
                if (tree->l) tree=tree->l; else break;
            else
                if (tree->r) tree=tree->r; else break;
        }
    } while(1);

    //добавляем узел
    if (!(cur = (rec *)calloc(1, sizeof(rec))))
        return;
    if (info < tree->inf)
        tree->l = cur;
    else 
        tree->r = cur;
    cur->inf = info;
    cur->n=1;
}

void see(rec *root)
{
    static int i;   // счетчик уровней
    i++;            // увеличиваем на 1, т.к. следуюющий уровень
    int i2 = i;     // текуший уровень
    if(root)
    {
        if (root->r) 
        {
            see(root->r);
            i = i2;
        }

        // отступ
        for(int j = 0; j < i; j++)
        {
            printf("%3s", "");
        }

        // вывод информации
        printf("%3d", root->inf);
		if(root->n>1) printf("[%d]",root->n);
        
        // если текущий узел - лист
		if(!root->l && !root->r) printf("   lvl%d", i);
        printf("\n");
        if (root->l)
        {
            see(root->l);
            i = i2;
        }
    }
    i = 0;
}

bool balancedTree(rec *root)  // проверка на сбалансированность дерева
{
    static int i = 0, max = -1, first = -1;
    i++;
    int i2 = i;
    bool result;

    // проход по левой ветке
    if (root->l) 
    {
        if (!balancedTree(root->l))
        {
            return false;
        }
        i = i2; 
    }

    // текущий элемент - лист
    if (!root->l && !root->r)
    {
        //если первая ветка
        if (first == -1)
        {
            first = i;
        }
        //не первая пройденная ветка
        if (max != -1)
            result = (abs(max-i) < 2) && (abs(first-i) < 2);        
        else
            result = true;
        max = i;
        return result;
    }

    //проверка на наличие 2ух веток у всех узлов, кроме листов и узлов с листами
    if (abs(max - i) > 1 && max != -1)
    {
        if (!root->l || !root->r)
        {
            return false;
        }
    }

    //идем по 2ой ветке
    if  (root->r) 
    {
        if (!balancedTree(root->r))
        {
            return false;
        }
        i = i2;
    }

    return true;
}


//дерево в массив
void treeToArray(rec *root, int **arr, int *n) // запись дерева в массив
{
    int *arr2 = *arr, n2 = *n; //указатель на массив и количество
    if(root)
    {
        if (root->r) // проход по правой ветви
            treeToArray(root->r, &arr2, &n2);
       
        //записываем в массив
        if (!arr2) // если массив еще не создан
        {
            n2 = 1;
            arr2 = (int *)malloc(sizeof(int));
        }
        else // добавление в массив
        {
			n2++;
            arr2 = (int *)realloc(arr2, n2 * sizeof(int));
        }
        *(arr2 + n2 - 1) = root->inf;  // запись в массив

        if (root->l)
            treeToArray(root->l, &arr2, &n2);
    }
    //возвращаем значения указателя на массив и количество
    *arr = arr2;
    *n = n2;
}

void arrayToTree(int *arr, int n, rec **root)  // запись массива в дерево
{
    rec *root2 = *root;
    if (!n || !arr) return;
    //добавляем средний элемент
    add(&root2, *(arr + n/2));
    // Передаем левую половину массива на обработку
    arrayToTree(arr, n/2, &root2);

    // Правая...
    if (n % 2)
        arrayToTree(arr + n/2 + 1, n/2, &root2);
    else
        arrayToTree(arr + n/2 + 1, n/2 - 1, &root2);

    *root = root2;
}

void balanceTree(rec *root, rec **newRoot) // создание сбалансированного дерева из несбалансированного
{
	int *arr=NULL;
    int n = 0;
    treeToArray(root, &arr, &n);  // записываем дерево в массив
    arrayToTree(arr, n, newRoot); // создаем из массива дерево
}

void main()
{
    setlocale(LC_ALL, "rus");
    rec *root = NULL, *root2 = NULL;
    int n = 0;

	puts("Нажмите любую клавишу для автоматического заполнения дерева,\nлибо Esc для ручного ввода:");
	if(getch()==27)
	{
		do
		{
			system("cls");
			printf("Значение: ");
			scanf("%d",&n);
			add(&root, n);
			printf("Продолжить добавление? (y/n): ");
		} while(getch()=='y');
	}
	else
	{
		printf("Введите количество добавляемых узлов ");
		scanf("%d", &n);
		for (int i = 0; i < n; i++)  // заполнение случайными значениями
			add(&root, rand()%100);
	}
	fflush(stdin);
	system("cls");
    see(root);
    puts("\n");
    if (balancedTree(root))
    {
        printf("Дерево сбалансировано");
    }
    else
    {
        printf("Дерево не сбалансировано\n\n");
        balanceTree(root, &root2);
        see(root2);
    }
    getch();
}