#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();
}