include iostream include fstream using namespace std struct Node int d

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#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;
}