Удалить все листья 2-3–дерева, попадающие в заданный диапазон значений - C (СИ)
Формулировка задачи:
помогите пожалуйста описать процедуру, которая удаляет все листья 2-3–дерева, попадающие в заданный
диапазон значений.
мб по поводу решения как нибуть по другому договоримся, ПЛИЗ ПОМОГИТЕ. сроки ((((
народ помогите плиз. кто шарит в 2-3 деревьях пм плиз
Решение задачи: «Удалить все листья 2-3–дерева, попадающие в заданный диапазон значений»
textual
Листинг программы
#include <stdio.h>
#include <stdlib.h>
#include <malloc.h>
// (теория) [url]http://cifragor.narod.ru/balanced_tree.html[/url]
// 2-3 дерево
// по определению расстояние от корня до любого листа одинаково
// в *left элементы меньшие *a
// *a наименьший элемент (center)
// *b наименьший элемент (right)
// Пусть задан диапазон [g1, g2]
// - если g2 меньше *a то элементов из диапазона по ветви *center нет
// - если g2 меньше *b то элементов из диапазона по ветви *right нет
// если g2 меньше *a то элементы из диапазона могут быть только по ветви *left
// если g2 меньше *b то элементы из диапазона могут быть по ветвям *left и *center
// - если g1 больше *a то элементов из диапазона по ветви *left нет
// - если g1 больше *b то элементов из диапазона по ветвям *left и *center нет
// - если g1 больше *a и g2 меньше *b то элементы из диапазона по ветви *center
// если g1 больше *a и g2 не меньше *b то элементы из диапазона по ветвям *center и *right
struct node
{
int *a, *b;
struct node* top;
struct node* left;
struct node* center;
struct node* right;
};
void create_node1(struct node* t, int c1)
{
t->top = NULL;
t->left = NULL;
t->center = NULL;
t->right = NULL;
t->a = (int*) malloc(sizeof(int));
*(t->a) = c1;
t->b = NULL;
}
void create_node2(struct node* t, int c1, int c2)
{
t->top = NULL;
t->left = NULL;
t->center = NULL;
t->right = NULL;
t->a = (int*) malloc(sizeof(int));
*(t->a) = c1;
t->b = (int*) malloc(sizeof(int));
*(t->b) = c2;
}
struct node* add_left1(struct node* t, int c1)
{
t->left = (struct node* ) malloc(sizeof(struct node));
create_node1(t->left, c1);
t->left->top = t;
return t->left;
}
struct node* add_left2(struct node* t, int c1, int c2)
{
t->left = (struct node* ) malloc(sizeof(struct node));
create_node2(t->left, c1, c2);
t->left->top = t;
return t->left;
}
struct node* add_center1(struct node* t, int c1)
{
t->center = (struct node* ) malloc(sizeof(struct node));
create_node1(t->center, c1);
t->center->top = t;
return t->center;
}
struct node* add_center2(struct node* t, int c1, int c2)
{
t->center = (struct node* ) malloc(sizeof(struct node));
create_node2(t->center, c1, c2);
t->center->top = t;
return t->center;
}
struct node* add_right1(struct node* t, int c1)
{
//right = new node(c1);
t->right = (struct node* ) malloc(sizeof(struct node));
create_node1(t->right, c1);
t->right->top = t;
return t->right;
}
struct node* add_right2(struct node* t, int c1, int c2)
{
t->right = (struct node* ) malloc(sizeof(struct node));
create_node2(t->right, c1, c2);
t->right->top = t;
return t->right;
}
/* проверка корня:
Пусть задан диапазон [g1, g2] в котором нужно удалить из дерева листья.
Рассмотрим все возможные случаи отношения диапазона к узлу дерева
1 случай: g1, g2 меньше *a
элементы из диапазона могут быть только по ветви *left
-> переход на ветвь *left и проверяется
2 случай: g2 меньше *b
2.1 g1 больше *a
элементы из диапазона по ветви *center
-> переход на ветвь *center и проверяется
2.2 g1 меньше *a
элементы из диапазона могут быть по ветвям *left и *center
-> ветвь *left проверяется на диапазон [g1, *a]
-> ветвь *center проверяется на диапазон [*a, g2]
3 случай: g2 больше *b
3.1 g1 больше *a
элементы из диапазона по ветвям *center и *right
3.1.1 g1 больше *b
элементы из диапазона по ветви *right
-> переход на ветвь *right и проверяется
3.1.2 g1 меньше *b
-> ветвь *center проверяется на диапазон [g1, *b]
-> ветвь *right проверяется на диапазон [*b, g2]
3.2 g1 меньше *a
элементы из диапазона могут быть по ветвям *left и *center и *right
-> ветвь *center удаляется
-> ветвь *left проверяется на диапазон [g1, *a]
-> ветвь *right проверяется на диапазон [*b, g2]
-----------------------
Пусть задан диапазон [g1, g2] в котором нужно удалить из дерева листья.
Если задано только *a (ветви *left и *center)
1 случай: g1 больше *a и g2 больше *a
элементы из диапазона по ветви *center
-> переход на ветвь *center и проверяется
2 случай: g1 меньше *a и g2 меньше *a
элементы из диапазона по ветви *left
-> переход на ветвь *left и проверяется
3 случай: g1 меньше *a и g2 больше *a
-> ветвь *left проверяется на диапазон [g1, *a]
-> ветвь *center проверяется на диапазон [*a, g2]
*/
// this_node_p->recursive_change();
// this_node_p уже обновлен при вызове функции
// подняться до корня
void recursive_change(struct node* t)
{
int h; // минимальный элемент ветви
struct node* l;
l = t->left;
// спуск по левым до конца ( т.к. дерево сбалансированное)
while (l->left)
{
l = l->left;
}
h = *(l->a);
printf("h: %d\n", h);
printf("t: %x\n", t);
printf("t->top: %x\n", t->top);
if (t->top)
{
*(t->top->a) = h;
recursive_change(t->top);
}
}
struct node* del(struct node* t, int g1, int g2)
{
struct node* ret; // для удаления элементов
struct node* this_node;
struct node* this_node_p;
ret = NULL;
if (t->left == NULL && t->center == NULL && t->right == NULL )
{
if (*(t->a) >= g1 && *(t->a) <= g2)
{
// удалить элемент this
// подзадача: обновить информацию о разбиении у предков (рекурсивно)
this_node = t->top;
// у родителя три сына - удаляется средний
// (this_node)
// / | \
// (this_node->left) (this_node->center) (this_node->right)
if (this_node->right && t == this_node->center )
{
*((t->top)->a) = *((t->top)->b);
free ((t->top)->b); (t->top)->b = NULL;
*(t->a) = *(((t->top)->right)->a);
free (((t->top)->right)->a); ((t->top)->right)->a = NULL;
free (((t->top)->right)); ((t->top)->right) = NULL;
}
else if (t == this_node->right)
{
free ((t->top)->b); (t->top)->b = NULL;
free (t->a); t->a = NULL;
// delete this; this = NULL;
// отсюда нельзя удалить this
return t; // для удаления this
}
else
{
if (this_node->top)
this_node_p = this_node->top;
// 1. есть ли у родителя p другой сын, расположенный слева или справа от node?
if ( this_node_p) // если есть родитель p
{
if (this_node == this_node_p->left)
{
if ( this_node_p->center)
{
// если у другого сына родителя p трое сыновей
if ( this_node_p->center->left && this_node_p->center->center && this_node_p->center-> right)
{
if (t == this_node->left)
{
// сделать одного из сыновей другого сына родителя p сыном node
*(t->a) = *((this_node->center)->a);
*((this_node->center)->a) = *(this_node_p->center->left->a);
*(this_node->a) = *((this_node->center)->a);
*(this_node_p->center->left->a) = *(this_node_p->center->center->a);
*(this_node_p->center->center->a) = *(this_node_p->center->right->a);
*(this_node_p->center->a)= *(this_node_p->center->b);
free (this_node_p->center->b); this_node_p->center->b = NULL;
free (this_node_p->center->right->a); this_node_p->center->right->a = NULL;
free (this_node_p->center->right); this_node_p->center->right = NULL;
*(this_node_p->a) = *(this_node_p->center->left->a);
// рекурсивно подняться до корня изменяя информацию
recursive_change(this_node_p);
}
else if ( t == this_node->center)
{
*(t->a) = *(this_node_p->center->left->a);
*(this_node->a) = *(t->a);
*(this_node_p->center->left->a) = *(this_node_p->center->center->a);
*(this_node_p->center->center->a) = *(this_node_p->center->right->a);
*(this_node_p->center->a)= *(this_node_p->center->b);
free (this_node_p->center->b); this_node_p->center->b = NULL;
free (this_node_p->center->right->a); this_node_p->center->right->a = NULL;
free (this_node_p->center->right); this_node_p->center->right = NULL;
*(this_node_p->a) = *(this_node_p->center->left->a);
}
}
else // два сына у this_node_p->center
{
// смежный узел имеет два сына
// узел становиться третьим сыном смежного узла
if (t == this_node->left)
{
//this_node_p->center->b = new int( *(this_node_p->center->a) ) ;
this_node_p->center->b = (int*) malloc(sizeof(int));
*(this_node_p->center->b) = *(this_node_p->center->a);
add_right1(this_node_p, *(this_node_p->center->center->a) ) ;
*(this_node_p->center->center->a) = *(this_node_p->center->left->a) ;
*(this_node_p->center->a) = *(this_node_p->center->center->a) ;
*(this_node_p->center->left->a) = *(this_node->center->a) ;
}
else if ( t == this_node->center)
{
//this_node_p->center->b = new int( *(this_node_p->center->a) ) ;
this_node_p->center->b = (int*) malloc(sizeof(int));
*(this_node_p->center->b) = *(this_node_p->center->a);
add_right1(this_node_p, *(this_node_p->center->center->a) ) ;
*(this_node_p->center->center->a) = *(this_node_p->center->left->a) ;
*(this_node_p->center->a) = *(this_node_p->center->center->a) ;
*(this_node_p->center->left->a) = *(this_node->left->a) ;
}
//
if (this_node_p->top)
{
// где эта ветвь в отношении this_node_p->top ?
// + проблема с удалением
}
}
}
else // this_node_p->center равен NULL
{
// невозможно, так как left один и значит дерево не 2-3 дерево
printf("\nerror: ! 2-3 tree\n");
}
}
else if (this_node == this_node_p->center)
{
if ( this_node_p->right)
{
// если у другого сына родителя p трое сыновей
if ( this_node_p->right->left && this_node_p->right->center && this_node_p->right-> right)
{
if (t == this_node->left)
{
// сделать одного из сыновей другого сына родителя p сыном node
*(t->a) = *((this_node->center)->a);
*((this_node->center)->a) = *(this_node_p->right->left->a);
*(this_node->a) = *((this_node->center)->a);
*(this_node_p->right->left->a) = *(this_node_p->right->center->a);
*(this_node_p->right->center->a) = *(this_node_p->right->right->a);
*(this_node_p->right->a)= *(this_node_p->right->b);
free (this_node_p->right->b); this_node_p->right->b = NULL;
free (this_node_p->right->right->a); this_node_p->right->right->a = NULL;
free (this_node_p->right->right); this_node_p->right->right = NULL;
*(this_node_p->b) = *(this_node_p->right->left->a);
*(this_node_p->a) = *(this_node_p->center->left->a);
// ? рекурсивно подняться до корня изменяя информацию
//this_node_p->recursive_change();
}
else if ( t == this_node->center)
{
*(t->a) = *(this_node_p->right->left->a);
*(this_node->a) = *(t->a);
*(this_node_p->right->left->a) = *(this_node_p->right->center->a);
*(this_node_p->right->center->a) = *(this_node_p->right->right->a);
*(this_node_p->right->a)= *(this_node_p->right->b);
free (this_node_p->right->b); this_node_p->right->b = NULL;
free (this_node_p->right->right->a); this_node_p->right->right->a = NULL;
free (this_node_p->right->right); this_node_p->right->right = NULL;
*(this_node_p->b) = *(this_node_p->right->left->a);
*(this_node_p->a) = *(this_node_p->center->left->a);
}
}
else // два сына у this_node_p->center
{
//
// не сделано
//
}
}
else // this_node_p->center равен NULL
{
// невозможно, так как left один и значит дерево не 2-3 дерево
printf("\nerror: ! 2-3 tree\n");
}
}
else if (this_node == this_node_p->right)
{
// не сделано
}
}
else // this_node_p равен NULL
{
// не сделано
}
}
/*
// конкретный случай удаления элемента 10
struct node* t1 = this->top; struct node* tt1 = t1->top; struct node* ttt1 = tt1->top;
int tmp; int tmp2;
*(this->a) = *((t1->center)->a);//2
*((t1->center)->a) = *((tt1->center)->left->a);//3
*(t1->a) = *(tt1->a);//1
*((tt1->center)->left->a)= *((tt1->center)->center->a);//4
delete (tt1->center)->center; //5
(tt1->center)->center = NULL; //5
tmp = *((tt1->center)->a); //6
*((tt1->center)->a) = *((tt1->center)->b);//6
delete (tt1->center)->b; //6
(tt1->center)->b = NULL; //6
tmp2 = *(tt1->a);
*(tt1->a) = tmp;
tmp = *(t1->left->a);
*(ttt1->a) = tmp;
*/
}
}
if (t->a && t->b)
{
/*
1 случай: g1 меньше *a и g2 меньше *a
элементы из диапазона могут быть только по ветви *left -> переход на ветвь *left и проверяется
*/
if (g2 < *(t->a))
{
if (t->left) ret = del (t->left, g1, g2);
}
else // g2 >= *a
{
/*
2 случай: g2 меньше *b
*/
if (g2 < *(t->b))
{
/*
2.1 g1 больше *a и g2 меньше *b
элементы из диапазона по ветви *center -> переход на ветвь *center и проверяется
*/
if (g1 > *(t->a))
{
if (t->center) ret = del (t->center, g1, g2);
}
/*
2.2 g1 меньше *a и g2 меньше *b
элементы из диапазона могут быть по ветвям *left и *center
-> ветвь *left проверяется на диапазон [g1, *a]
-> ветвь *center проверяется на диапазон [*a, g2]
*/
else
{
if (t->left) ret = del (t->left, g1, *(t->a));
if (t->center) ret = del (t->center, *(t->a), g2);
}
}
/*
3 случай: g2 больше *b
*/
else
{
/*
3.1 g1 больше *a и g2 больше *b
элементы из диапазона по ветвям *center и *right
*/
if (g1 > *(t->a))
{
/*
3.1.1 g1 больше *b и g2 больше *b
элементы из диапазона по ветви *right-> переход на ветвь *right и проверяется
*/
if (g1 > *(t->b))
{
if (t->right) ret = del (t->right, g1, g2);
}
/*
3.1.2 g1 меньше *b и g2 больше *b
-> ветвь *center проверяется на диапазон [g1, *b]
-> ветвь *right проверяется на диапазон [*b, g2]
*/
else
{
if (t->center) ret = del (t->center, g1, *(t->b));
if (t->right) ret = del (t->right, *(t->b), g2);
}
}
/*
3.2 g1 меньше *a
элементы из диапазона могут быть по ветвям *left и *center и *right
-> ветвь *center удаляется
-> ветвь *left проверяется на диапазон [g1, *a]
-> ветвь *right проверяется на диапазон [*b, g2]
*/
else
{
if (t->center) { free (t->center); t->center = NULL; }
if (t->left) ret = del (t->left, g1, *(t->a));
if (t->right) ret = del (t->right, *(t->b), g2);
}
}
}
/* */
}
else if (t->a)
{
if (g1 >= *(t->a))
{
if (t->center) ret = del (t->center, g1, g2);
}
else // g1 < *a
{
if (g2 < *(t->a))
{
if (t->left) ret = del (t->left, g1, g2);
}
else // g2 >= *a ? (g2 == *a)
{
if (t->left) ret = del (t->left, g1, *(t->a));
if (t->center) ret = del (t->center, *(t->a), g2);
}
}
}
else if (t->b){ printf("error"); exit(0);}
if (ret != NULL)
{
free (ret); ret = NULL;
}
return NULL;
}
// вывод дерева
void print(struct node* t)
{
printf("%x %x %x %x\n", t, t->left, t->center, t->right);
if (t->a != NULL)
printf("a: %d ", *(t->a));
if (t->b != NULL)
printf("b: %d ", *(t->b));
printf("\n");
if (t->left != NULL ) { printf("left\n"); print(t->left);}
if (t->center != NULL) { printf("center\n"); print(t->center);}
if (t->right != NULL) { printf("right\n"); print(t->right);}
}
int main()
{
struct node* p;
struct node* l1;
struct node* l2;
struct node* r1;
struct node* r2;
// создание дерева ( рисунок 3б, [url]http://cifragor.narod.ru/balanced_tree.html[/url] )
//p = new node(10);
p = (struct node*) malloc(sizeof(struct node));
create_node1(p, 10);
l1 = add_left1(p, 7);
l2 = add_left1(l1, 5);
add_left1(l2, 2);
add_center1(l2, 5);
r2 = add_center1(l1, 8);
add_left1(r2, 7);
add_center1(r2, 8);
r1 = add_center1(p, 16);
l2 = add_left1(r1, 12);
add_left1(l2, 10);
add_center1(l2, 12);
r2 = add_center2(r1, 18, 19);
add_left1(r2, 16);
add_center1(r2, 18);
add_right1(r2, 19);
// вывод дерева
print(p);
//
del(p, 9, 11);
printf("----------------------------------\n");
print(p);
}
ИИ поможет Вам:
- решить любую задачу по программированию
- объяснить код
- расставить комментарии в коде
- и т.д