Здравствуйте , есть программа реализующая бинарное дерево поиска , нужно проверить является ли дерево идеально сбалансированным . Помогите разобраться хоть с примерным алгоритмом проверки .
/*//////////////////////////////////////////
** Построить бинарное дерево поиска, данными в узлах которого являются целые числа.
** Проверить, является ли полученное дерево идеально сбалансированным.
** Обойти дерево в прямом и симметричном порядке.
**
** Реализация дерева – по выбору студента (выбор обосновать!)
** Все структуры данных оформить в виде классов. Все данные считывать из файлов
*///////////////////////////////////////////
#include <iostream>
using namespace std;
struct Node
{
int data;
int height_left, height_right;
Node * left, * right;
};
typedef struct Node *tree;
struct Node * NewNode (int data) //создание нового узла
{
struct Node * pTree = new Node;
pTree->data = data;
pTree->height_left = pTree->height_right = 0;
pTree->left = pTree->right = NULL;
return pTree;
}
/*
** Добавление данных в дерево
*/
int AddNode (tree & pTree, int data) //функция добавления узла в дерево, возвращается 1, если увеличивается высота дерева
{
/* Если указатель равен нулю */
if (!pTree)
{
pTree = NewNode(data);
return 1;
}
/* Если добавляемый элемент уже существует */
if (data == pTree->data)
return 0;
/* Добавление в левое поддерево */
if (data < pTree->data)
{
if (AddNode(pTree->left,data))
{
pTree->height_left++;
if (pTree->height_left > pTree->height_right)
return 1;
}
return 0;
}
/* Добавление в правое поддерево */
if (AddNode(pTree->right,data))
{
pTree->height_right++;
if (pTree->height_right > pTree->height_left)
return 1;
}
return 0;
}
/*
** Обход и печать в симметричном порядке
*/
void PrintSim(tree pTree)
{
if (pTree)
{
PrintSim(pTree->left);
cout << pTree->data << '(' << pTree->height_left << '/' << pTree->height_right << ") ";//значение узла (высота левого поддерева/высота правого поддерева)
PrintSim(pTree->right);
}
}
/*
** Обход и печать в прямом порядке
*/
void PrintPre(tree pTree)
{
if (pTree)
{
cout << pTree->data << '(' << pTree->height_left << '/' << pTree->height_right << ") ";//значение узла (высота левого поддерева/высота правого поддерева)
PrintPre(pTree->left);
PrintPre(pTree->right);
}
}
/*
** Удаление дерева
*/
void DelTree(tree pTree)
{
if (pTree->left)
DelTree(pTree->left);
if (pTree->right)
DelTree(pTree->right);
delete pTree;
}
int main()
{
tree pTree = NULL;
int mas[15]={14, 8, 1, 13, 7, 12, 6, 2, 9, 0, 11, 10, 4, 3, 5}, i;
for (i = 0; i < 15; i++)
AddNode(pTree, mas[i]);
cout << "Обход Дерева в симметричном порядке" << endl;
PrintSim(pTree);
cout << endl << "Обход Дерева в прямом порядке" << endl;
PrintPre(pTree);
DelTree(pTree);
return 0;
}
