5 практика
.pdf//0 - успешно выполненная операция
//1 - вращение невозможно
int rotate_right(node* n)
{
node* root = n;
node* newroot = root->left; node* perebros = newroot->right; newroot->parent = root->parent; if(root->parent != NULL)
{
if(root->parent->value > root->value)
{
root->parent->left = newroot;
}
else
{
root->parent->right = newroot;
}
}
if(perebros!=NULL)
{
21
perebros->parent = root;
}
root->left = perebros; root->parent = newroot; newroot->right = root; return 0;
}
//Выполнить левое вращение поддерева, корнем которого является n:
//0 - успешно выполненная операция
//1 - вращение невозможно
int rotate_left(node* n)
{
node* root = n;
node* newroot = root->right; node* perebros = newroot->left;
newroot->parent = root->parent; if(root->parent != NULL)
{
if(root->parent->value > root->value)
{
root->parent->left = newroot;
22
}
else
{
root->parent->right = newroot;
}
}
if(perebros!=NULL)
{
perebros->parent = root;
}
root->right = perebros; root->parent = newroot; newroot->left = root; return 0;
}
int rotate_root_left(tree* t)
{
rotate_left(t->root);
if (t->root->parent != NULL)
{
t->root = t->root->parent;
23
}
return 0;
}
int rotate_root_right(tree* t)
{
rotate_right(t->root);
if (t->root->parent != NULL)
{
t->root = t->root->parent;
}
return 0;
}
// получение кол-во уровней в дереве int get_levels(node* tmp)
{
if (tmp == NULL)
{
return 0;
}
int leftmax = 1 + get_levels(tmp->left);
24
int rightmax = 1 + get_levels(tmp->right); if (leftmax > rightmax)
{
return leftmax;
}
else
{
return rightmax;
}
}
//функция для вывода уровня
void print_level(node* tmp, int curl, int d, int first)
{
if (curl == d)
{
if (first > 0)
{
printf(" ");
}
if (tmp == NULL) {
25
printf("_");
}
else
{
printf("%d", tmp->value);
}
}
else if (tmp != NULL)
{
print_level(tmp->left, curl + 1, d, first); print_level(tmp->right, curl + 1, d, first + 1);
}
else
{
print_level(tmp, curl + 1, d, first); print_level(tmp, curl + 1, d, first + 1);
}
}
//функция для вывода уровня
void print_levelbeztire(node* tmp, int curl, int d, int first)
{
26
if (curl == d)
{
if (first > 0)
{
}
if (tmp == NULL) {
}
else
{
printf("%d", tmp->value);
}
}
else if (tmp != NULL)
{
print_levelbeztire(tmp->left, curl + 1, d, first); print_levelbeztire(tmp->right, curl + 1, d, first + 1);
}
else
{
print_levelbeztire(tmp, curl + 1, d, first); print_levelbeztire(tmp, curl + 1, d, first + 1);
27
}
}
//Вывести все значения из поддерева, корнем которого является n
//по уровням начиная с корня.
//Каждый уровень выводится на своей строке.
//Элементы в строке разделяются пробелом. Если элемента нет, заменить на
_.
//Если дерево пусто, вывести - void print(node* n)
{
int num = get_levels(n);
for (int i = 1; i <= num; i++)
{
print_level(n, 1, i, 0); printf("\n");
}
}
//Вывести все значения дерева t, аналогично функции print
void print_tree(tree* t)
{
node* n = t->root;
28
if (n == NULL)
{
printf("-"); printf("\n");
}
print(t->root);
}
//Функция, возвращающая указатель на корень node* rootret(tree* t)
{
return t->root;
}
//Вывод количества элементов в списке void print_num(tree* t)
{
printf("%d", t->numbers);
}
int main()
{
29
int a, i, n1, n2; struct tree t; init(&t);
//ввод первых 4х чисел for (i=0; i<4; i++)
{
scanf("%d", &a); insert(&t, a);
}
print_tree(&t); printf("\n");
//ввод ещё 3х чисел for (i=0; i<3; i++)
{
scanf("%d", &a); insert(&t, a);
}
print_tree(&t); printf("\n");
30