include iostream include conio using namespace std struct node int dat

  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
#include <iostream>
#include <conio.h>
using namespace std;
struct node
{
int data;
int height_left, height_right; //высота левого и правого поддеревьев
node * left, * right;
};
typedef struct node * tree;
struct node * new_node (int x) //создание нового узла
{
struct node * t = new node;
t->data = x;
t->height_left = t->height_right = 0;
t->left = t->right = NULL;
return t;
}
int add_node (tree & t, int x) //функция добавления узла в дерево, возвращается 1, если увеличивается высота дерева
{
if (!t) {t=new_node(x); return 1;}
if (x==t->data) return 0; //если узел с таким значением есть, он не добавляется повторно
if (x<t->data)
{
if (add_node(t->left,x)) //если при добавлении элемента в левое поддерево высота поддерева увеличилась
{
t->height_left++; //то увеличиваем соответствующее поле
if (t->height_left>t->height_right) return 1;
}
return 0;
}
if (add_node(t->right,x)) //аналогично левому поддереву
{
t->height_right++;
if (t->height_right > t->height_left) return 1;
}
return 0;
}
void print_sim (tree t) //печать в симметричном порядке
{
if (t->left) print_sim(t->left);
cout<<t->data<<'('<<t->height_left<<'/'<<t->height_right<<") ";//значение узла (высота левого поддерева/высота правого поддерева)
if (t->right) print_sim(t->right);
}
void leftrotation (tree & t) //левый поворот
{
node * temp = t->right;
t->right = temp->left;
t->height_right = temp->height_left;
temp->left=t;
temp->height_left=1+((t->height_left>t->height_right)?t->height_left:t->height_right); //пересчет высоты
t=temp;
}
void rightrotation (tree & t) //правый поворот
{
node * temp = t->left;
t->left = temp->right;
t->height_left = temp->height_right;
temp->right=t;
temp->height_right=1+((t->height_left>t->height_right)?t->height_left:t->height_right); //пересчет высоты
t=temp;
}
int balance_tree (tree & t, int bal) //функция балансировки, возвращается высота дерева, bal - баланс отца
{
int b;
b=t->height_left - t->height_right; //баланс текущего узла
if (t->left) //если есть левое поддерево
{
t->height_left=1+balance_tree (t->left, b); //вычисление высоты левого поддерева после его балансировки
b=t->height_left - t->height_right; // перевычисление баланса
}
if (t->right) //если есть правое поддерево
{
t->height_right=1+balance_tree (t->right, b); //вычисление высоты правого поддерева после его балансировки
b=t->height_left - t->height_right; //перевычисление баланса
}
if (b>0 && bal<0 || b>1) //если баланс сугубо положительный или положительный, но баланс отца отрицательный
{
rightrotation (t); //выполняем правый поворот
print_sim (t); //отладочная печать
cout<<endl;
getch();
b=t->height_left - t->height_right; //пересчет баланса
balance_tree (t,bal); //контрольная балансировка
}
else if (b<-1 || b<0 && bal>0)//если баланс сугубо отрицательный или отрицательный, но баланс отца положительный
{
leftrotation (t); //выполняем левый поворот
print_sim (t); //отладочная печать
cout<<endl;
getch();
b=t->height_left - t->height_right; //пересчет баланса
balance_tree (t,bal); //контрольная балансировка
}
return (t->height_left>t->height_right)?t->height_left:t->height_right; //возвращается высота дерева
}
void del_tree (tree t) //функция удаления дерева
{
if (t->left) del_tree (t->left);
if (t->right) del_tree (t->right);
delete t;
}
main()
{
tree t=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++)
{
add_node (t, mas[i]);
print_sim (t);
cout<<endl;
}
print_sim (t);
getch();
cout<<endl;
balance_tree (t,0);
print_sim (t);
del_tree (t);
getch();
return 0;
}