Удаление элемента из бинарного дерева

@ihor · Регистрация: 10.04.2012

Author24 — интернет-сервис помощи студентам

в программе выполняется пару ф-й, не работает удаление элемента (в меню пункт 1), должен удалить узел где длина кода более 5, при попытке удалить крайней листок не имеющий потомков выдает, а ежели удалять элементы имеющие потомков, то когда печатает дерево выдает ту же ошибку, даю файл с деревом и ВЕСЬ код программы.

т.е. не работают: void DeleteNode (Tree ** root_adr);

код сбалансированного дерева " balanced[1]":
h 001 d 002 l 003 b 004 f 005 j 006 n 007 a 008 c 009 e 010 g 011 i 0121212 k 013 m 014 o 015
код не сбалансированного дерева "not balanced[2]" :
d 01 b 02 j 03 a 04 c 05 g 06 m 007 f 080808 h 09 l 10 n 11 e 12 o 13

C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
 
typedef struct key_combinations
{
    char *key;
    char *combination;
} KEY_COMBINATION;
 
 
typedef struct tree
{
    KEY_COMBINATION kc;
    struct tree *left,*right;
}Tree;
 
Tree *root;
Tree ** stack;   
 
void AddNode (Tree * proot, Tree * pnew) ;
void GetData ();
void PrintTree();
    void ShowTree(Tree *rooot, int lvl);
    void PutTree(Tree *rooot);
void ifMore(Tree *rooot);
    void DeleteNode (Tree ** root_adr);
        void FreeNode (Tree * node) ;
int TreeHeight(Tree * proot);
void DigitNumber(Tree * proot);
void RightToTop(Tree **root_adr);
void DeleteTree(Tree *rooot) ;
 
int main()
{ 
    
    GetData ();
    PrintTree();
    int menu=1,len=0;
     while(menu>0)
     {
    printf("\n\n delete where len>5 [1]\n right ot top [2] \n iteretion funk [3] \n free && exit [0] \n ");
        scanf("%d",&menu);
    switch(menu)
    {
    case 1:
        ifMore(root);
        PrintTree();
    break;
    case 2:
            
            len=TreeHeight(root);
            printf("\n Tree height = %d with root : %s",len,root->kc.key);
            RightToTop(&root);
            len=TreeHeight(root);
            printf("\n Tree height = %d with root : %s",len,root->kc.key);
    break;
    case 3:
            stack=(Tree **)calloc(TreeHeight(root), sizeof(Tree *));
            DigitNumber(root); 
    break;
    case 0:
        DeleteTree(root);
    
    break;  
    }
    }
 
return 0;
}
 
void GetData ()
{
    Tree * pel;
    KEY_COMBINATION * pkc;
 
    char bufk[3],bufc[25];
    FILE* f;
    
    pkc = (KEY_COMBINATION *)malloc(sizeof(KEY_COMBINATION));
    
    int choise;
    printf("choose file balanced[1] not balanced[2] :   ");
    scanf("%d",&choise);
         
    if(choise==2)
        f = fopen("TreeNB","r");
    else
        f = fopen("TreeB","r");
 
    while(fscanf(f,"%s%s",bufk,bufc)!=EOF)
    {   
        //printf("\n %s %s",bufk,bufc);
        pkc->key = (char * ) malloc(strlen(bufk)+1);
        strcpy(pkc->key, bufk);
 
        pkc->combination =(char * ) malloc(strlen(bufc)+1);
        strcpy(pkc->combination, bufc);
 
        pel = (Tree *)malloc(sizeof(Tree));
        pel->kc = * pkc;
 
        pel->left = NULL;
        pel->right = NULL;
 
        AddNode(root,pel);
    }
}
 
void AddNode (Tree * proot, Tree * pnew)
{
        if (root == NULL)
           root = pnew;
        else
            if (strcmp(proot->kc.key, pnew->kc.key)>0)
                if (proot->left == NULL)
                    proot->left = pnew;
                else
                    AddNode(proot->left, pnew);
            else
                if (proot->right == NULL)
                    proot->right = pnew;
                else
                    AddNode(proot->right, pnew);
    }
 
void PrintTree()
{
    puts("\n===============================");
    PutTree(root);
    puts("\n===============================\n");
    ShowTree(root,1);
    puts("===============================");
}
 
void ShowTree(Tree *rooot, int lvl)
{
    if(rooot==NULL)
        return;
 
    ShowTree(rooot->right,lvl+1);
          printf("%*c%s\n", lvl*3,' ', rooot->kc.key);
    ShowTree(rooot->left,lvl+1);
}
 
void PutTree(Tree *rooot)
{
    if(rooot==NULL)
        return;
             printf("\n\t%s -\t%s", rooot->kc.key, rooot->kc.combination);
    PutTree(rooot->left);
    PutTree(rooot->right);
}
 
void ifMore(Tree *rooot)
{
 
    if(rooot==NULL)
        return;
    if(strlen(rooot->kc.combination)>5)
        {
            printf("found %s",rooot->kc.key);
            printf("\n %s-%s", rooot->kc.key, rooot->kc.combination);
           DeleteNode(&rooot);
           ifMore(rooot);
        }
    ifMore(rooot->left);
    ifMore(rooot->right);
}
 
void FreeNode (Tree * node)
{   
    free(node->kc.key);
    free(node->kc.combination);
    free(node);
}
 
int TreeHeight(Tree * proot) 
    {  
            int lh,rh;
            if (proot == NULL) 
            return 0;
           lh = TreeHeight(proot->left);        
           rh = TreeHeight(proot->right);      
           return  lh > rh ? lh+1 : rh+1;  
    }
 
void DigitNumber(Tree * proot)
{
int i=0;
Tree  * pdel = root, * pnext;
 
  while (pdel!= NULL) {  
       if (pdel->left!= NULL) 
  {         pnext = pdel->left;      
        if (pdel->right!= NULL)                 
               stack[++i] = pdel->right;  
                 }
                  else  
        if (pdel->right!= NULL)
           pnext = pdel->right;         
        else
            pnext = stack[i--];   
    int n = strlen(pdel->kc.combination);
    printf("%s -%s - digit number =  %d\n ",pdel->kc.key,pdel->kc.combination,n);
     pdel = pnext;                    
  }
 
}
 
void RightToTop(Tree **root_adr)
    {
 
        Tree *proot = *root_adr,*pright = *root_adr,*prev;
 
        while(pright->right!=NULL)
            {
                prev=pright;
                pright=pright->right;
            }
 
        prev->right=NULL;
        pright->left=proot;
        *root_adr=pright;
 
    }
 
void DeleteNode (Tree ** root_adr)
{ 
   Tree * proot = *root_adr, * pright, * padd;
     int cmp, subtr;
  if (proot == NULL)   return;       
    
  if (proot->left == NULL && proot->right == NULL) 
       subtr = 0;                      
    else if (proot->left == NULL)
           subtr = 1;
        else if (proot->right == NULL)
                subtr = -1;
             else
                subtr = 2;
    switch (subtr) 
    {                         
      case 0:                         
        *root_adr = NULL;  
         break;
      case -1:              
        *root_adr = proot->left; 
         break;
      case 1:           
         *root_adr = proot->right; 
        break;
      case 2:                   
        *root_adr = proot->left; 
            pright = proot->left->right;  
        padd = proot->left->right=proot->right ;
        proot->right=NULL;     
        while (padd->left!= NULL)
            padd = padd->left;
        padd->left = pright;  
        break;   
    }    
    FreeNode(proot);
    printf(" free..");    
  }
 
void DeleteTree(Tree *rooot)  
{
    if(rooot==NULL)
        return;
    DeleteTree(rooot->left);
    DeleteTree(rooot->right);
    free(rooot);
}

@lowercase · 24.01.2013, 18:28

у меня в прошлом семестре была лаба в которой нужно было реализировать некое подобие базы данных основанную на деревьях.
так вот, для удаления я добавил в структуру еще одно поле, которое обозначало удален ли элемент из дерева.
то есть, фактически информация не удалялась, и, при желании ее можно было востановить.
ну и соответсвенно, когда выполнялся поиск, вывод, редактирование все основывалось на этом флажке. если он установлен - увы нету такого элемента, если неустановлен - все ок - ищим, выводим, редактируем.

может я просто ленивый, но помоему сделать удаление для односвязного дерева(то есть когда есть указатели left, right, но нету parent(указатель на родительский элемент) довольно сложно.

@ihor · 24.01.2013, 18:47 **[ТС]**

Мне такое не подойдет, у меня преподаватель очень придирчивый поэтому имеет следовать в ТС. Кстати удаления ф-я как бы правильная, просто где-то не происходит правильно удаление или замена и комп обращается к несуществующему элемента, но где ошибка не знаю ..

Добавлено через 11 минут
забыл дописать, выдает ошибку segmentation fault 11

MrGluck · 24.01.2013, 19:04

ihor, нужно связать предыдущее звено с текущим а потом освободить память. Это делается так: если след. левый потомок == значению нашего удал. элемента, то правое поддерево тек. элемента становится текущим левым потомком (встает на место удал. элемента), а указатель на левое ищет место в новом дереве начиная с правого поддерева удал. узла. После всех операций память под удал. элемент освобождается.
Лучше всего, попробуйте нарисовать это на бумаге, представить как должно быть.

@ihor · 25.01.2013, 22:52 **[ТС]**

Да даже если я удаляю крайней элемент, у которого нет потомков, все равно выдает ошибку segmentetion fault 11

MrGluck · 25.01.2013, 22:58

ihor, покажите, как удаляете. Вы указатель то хоть на него обнуляете?

@ihor · 26.01.2013, 17:50 **[ТС]**

вот ф-я удаления

C

void DeleteNode (Tree ** root_adr)
{ 
   Tree * proot = *root_adr, * pright, * padd;
     int cmp, subtr;
  if (proot == NULL)   return;       
    
  if (proot->left == NULL && proot->right == NULL) 
       subtr = 0;                      
    else if (proot->left == NULL)
           subtr = 1;
        else if (proot->right == NULL)
                subtr = -1;
             else
                subtr = 2;
    switch (subtr) 
    {                         
      case 0:                         
        *root_adr = NULL;  
         break;
      case -1:              
        *root_adr = proot->left; 
         break;
      case 1:           
         *root_adr = proot->right; 
        break;
      case 2:                   
        *root_adr = proot->left; 
            pright = proot->left->right;  
        padd = proot->left->right=proot->right ;
        proot->right=NULL;     
        while (padd->left!= NULL)
            padd = padd->left;
        padd->left = pright;  
        break;   
    }    
    FreeNode(proot);
    printf(" free..");    
  }

и ф-я фри

C

void FreeNode (Tree * node)
{   
    free(node->kc.key);
    free(node->kc.combination);
    free(node);
}

@ihor · 29.01.2013, 19:45 **[ТС]**

Ну народ ! HELP !

@ПЬюПИК · 15.05.2016, 15:29

C

void Del(ELT *q)
{
     if(q!=NULL)
      {
        Del(q->left);
        Del(q->reght);
        free(q);
      }
}

@lowercase 213 / 202 / 85 Регистрация: 09.05.2012 Сообщений: 494
	24.01.2013, 18:28	2
	у меня в прошлом семестре была лаба в которой нужно было реализировать некое подобие базы данных основанную на деревьях. так вот, для удаления я добавил в структуру еще одно поле, которое обозначало удален ли элемент из дерева. то есть, фактически информация не удалялась, и, при желании ее можно было востановить. ну и соответсвенно, когда выполнялся поиск, вывод, редактирование все основывалось на этом флажке. если он установлен - увы нету такого элемента, если неустановлен - все ок - ищим, выводим, редактируем. может я просто ленивый, но помоему сделать удаление для односвязного дерева(то есть когда есть указатели left, right, но нету parent(указатель на родительский элемент) довольно сложно. 0

@ihor 2 / 2 / 3 Регистрация: 10.04.2012 Сообщений: 22
	24.01.2013, 18:47 [ТС]	3
	Мне такое не подойдет, у меня преподаватель очень придирчивый поэтому имеет следовать в ТС. Кстати удаления ф-я как бы правильная, просто где-то не происходит правильно удаление или замена и комп обращается к несуществующему элемента, но где ошибка не знаю .. Добавлено через 11 минут забыл дописать, выдает ошибку segmentation fault 11 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	24.01.2013, 19:04	4
	ihor, нужно связать предыдущее звено с текущим а потом освободить память. Это делается так: если след. левый потомок == значению нашего удал. элемента, то правое поддерево тек. элемента становится текущим левым потомком (встает на место удал. элемента), а указатель на левое ищет место в новом дереве начиная с правого поддерева удал. узла. После всех операций память под удал. элемент освобождается. Лучше всего, попробуйте нарисовать это на бумаге, представить как должно быть. 1

@ihor 2 / 2 / 3 Регистрация: 10.04.2012 Сообщений: 22
	25.01.2013, 22:52 [ТС]	5
	Да даже если я удаляю крайней элемент, у которого нет потомков, все равно выдает ошибку segmentetion fault 11 0

MrGluck Форумчанин 8215 / 5045 / 1437 Регистрация: 29.11.2010 Сообщений: 13,453
	25.01.2013, 22:58	6
	ihor, покажите, как удаляете. Вы указатель то хоть на него обнуляете? 0

@ihor 2 / 2 / 3 Регистрация: 10.04.2012 Сообщений: 22
	29.01.2013, 19:45 [ТС]	8
	Ну народ ! HELP ! 0

	15.05.2016, 15:29