Удалить все листья 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);
 
}

Оцени полезность:

10   голосов , оценка 4.2 из 5
Похожие ответы