Добавил:
FluffyUnicorn
Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз:
Предмет:
Файл:Структуры данных примеры / Дерево бинарного поиска / tree_balance
.cpp#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;
}
Соседние файлы в папке Дерево бинарного поиска