Удаление элемента из бинарного дерева - C (СИ)

Узнай цену своей работы

Формулировка задачи:

в программе выполняется пару ф-й, не работает удаление элемента (в меню пункт 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
#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);
}

Решение задачи: «Удаление элемента из бинарного дерева»

textual
Листинг программы
void Del(ELT *q)
{
     if(q!=NULL)
      {
        Del(q->left);
        Del(q->reght);
        free(q);
      }
}

Объяснение кода листинга программы

  1. В функции Del аргументом является указатель на узел q.
  2. Если q не равен NULL, то выполняется рекурсивный вызов функции Del для левого поддерева q->left.
  3. После этого выполняется рекурсивный вызов функции Del для правого поддерева q->right.
  4. Затем освобождается память, выделенная под узел q, с помощью функции free.
  5. Если q равен NULL, то ничего не происходит.

ИИ поможет Вам:


  • решить любую задачу по программированию
  • объяснить код
  • расставить комментарии в коде
  • и т.д
Попробуйте бесплатно

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

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