#include <iostream>
#include <fstream>
using namespace std;
struct Node
{
int data;
int balance;
Node * left, * right;
};
struct Node * tree = NULL;
struct Node * NewNode(int data)
{
struct Node * pTree = new Node;
pTree->data = data;
pTree->balance = 0;
pTree->left = pTree->right = NULL;
return pTree;
}
int AddNode(struct Node * & pTree, int data)
{
/* Если указатель равен нулю */
if (!pTree)
{
pTree = NewNode(data);
return 1;
}
/* Если добавляемый элемент уже существует */
if (data == pTree->data)
return 0;
/* Добавление в левое поддерево */
if (data < pTree->data)
{
if(AddNode(pTree->left,data))
{
pTree->balance++;
return 1;
}
return 0;
}
/* Добавление в правое поддерево */
if (AddNode(pTree->right,data))
{
pTree->balance--;
return 1;
}
return 0;
}
/*
** Обход и печать в прямом порядке
*/
void PrintPre(struct Node * pTree)
{
if (pTree)
{
cout << pTree->data << " ";
PrintPre(pTree->left);
PrintPre(pTree->right);
}
}
/*
** Обход и печать в симметричном порядке
*/
void PrintSim(struct Node * pTree)
{
if (pTree)
{
PrintSim(pTree->left);
cout << pTree->data << " ";
PrintSim(pTree->right);
}
}
/*
** Значение баланса
*/
bool Balance(struct Node * pTree)
{
if (pTree)
{
if(pTree->balance <= 1 && pTree->balance >= -1 && Balance(pTree->left) && Balance(pTree->right))
return true;
else
return false;
}
}
/*
** Удаление дерева
*/
void DelTree(struct Node * pTree)
{
if (pTree->left)
DelTree(pTree->left);
if (pTree->right)
DelTree(pTree->right);
delete pTree;
}
void ReadFile(char *nameFile, struct Node * pTree)
{
int data; // Переменная будет считывать значение
ifstream in; // Связь с потоком
in.open(nameFile, ios::in);
while(in >> data)
{
AddNode(tree, data);
}
in.close(); // Закрываем файл
}
int main()
{
char nameFile[100];
cout << "Введите имя файла" << endl;
cin >> nameFile;
ReadFile(nameFile, tree);
cout << "Обход Дерева в симметричном порядке" << endl;
PrintSim(tree);
cout << endl << "Обход Дерева в прямом порядке" << endl;
PrintPre(tree);
if(Balance(tree))
cout << endl << "Дерево идеально сбалансированно" << endl;
else
cout << endl << "Дерево не сбалансированно" << endl;
return 0;
}