Рекурсивное удаление дерева - C (СИ)

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

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

Здравствуйте! Школьная задачка, в общем-то. Написать функцию рекурсивного удаления дерева, начиная с определенного элемента. Суть кода: 1. Вводим исходное дерево. 2. Вводим элемент для удаления. 3. Ищем элемент в дереве. 4. Удаляем сам элемент и всё его поддерево. Я написал, но работает почему-то неправильно - в функции treeprint ошибка. Воспроизвести ее можно на следующих данных(см. вложение). Программа не должна заходить в функцию treeprint после того, как вывела элементы 1 и 2, но почему-то заходит и, естественно, натыкаясь на нулевой указатель, аварийно завершается. Буду благодарен за любую помощь. Подскажите хотя бы, куда копать. Весь код:
Листинг программы 
  1. #include <stdio.h>
  2. #include <conio.h>
  3. struct node // Структура узла
  4. {
  5.     int info; // Информационное поле
  6.     int c; // Счетчик
  7.     node *ll, *rl; // Левый и правый указатели
  8.     node *parent; //Родитель
  9. };
  10. // -------Функция построения дерева---------
  11. node *tree(node *p, node *dad, int w)
  12. {
  13.     if (p == NULL)
  14.     {
  15.         p = new node;
  16.         p->info = w;
  17.         p->ll = NULL;
  18.         p->rl = NULL;
  19.         p->c = 1;
  20.         p->parent=dad;
  21.     }
  22.     else if (w == p->info) // Если такая информация встречалась,
  23.     {
  24.         p->c = p->c + 1; // то счетчик количества увеличивается на 1
  25.     }
  26.     else if (w < p->info) // eсли меньше, то идем по левому указателю
  27.     {
  28.         p->ll = tree(p->ll, p, w);
  29.     }
  30.     else
  31.     {
  32.         p->rl = tree(p->rl, p, w); // иначе по правому
  33.     }
  34.     return p;
  35.  
  36. }
  37.  
  38. //--------- Функция обхода дерева -------------
  39. void treeprint(node *p)
  40. {
  41.     if (p != NULL)
  42.     {
  43.         treeprint(p->ll); // по левому указателю
  44.         printf("%d\t%d", p->c, p->info);
  45.         if(p->parent != NULL)
  46.           printf("\tParent: %d",  p->parent->info);
  47.         else
  48.           printf("\tNo parent!");
  49.         printf("\n");
  50.         treeprint(p->rl); // по правому указателю
  51.     }
  52. }
  53.  
  54. //--------- Функция поиска в дереве по значению узла -------------
  55. node *tree_find(node *&p, int n)
  56. {
  57.   if(p!=NULL)
  58.   {
  59.     if(p->info == n)
  60.       return p;
  61.     else if(p->info < n)
  62.       return tree_find(p->rl, n);
  63.     else
  64.       return tree_find(p->ll, n);
  65.   }
  66.   else
  67.     return NULL;
  68. }
  69.  
  70. //--------- Функция удаления дерева, начиная с заданного элемента-------------
  71. void tree_remove (node *p)
  72. {
  73.   if(p!=NULL)
  74.   {
  75.     tree_remove(p->ll);
  76.     tree_remove(p->rl);
  77.     delete p;
  78.     p=NULL;
  79.   }
  80. }
  81.  
  82. int main()
  83. {
  84.     node *root; // Рабочий указатель на корень дерева
  85.     int w,n,elem; // Буферная переменная, счетчик
  86.     root = NULL; //Дерево пустое
  87.     printf("Enter amount of trees' elems: ");
  88.     scanf("%d", &n);
  89.     
  90.     //вводим дерево    
  91.     for(int i=0; i<n; i++)
  92.     {
  93.         scanf("%d", &w);
  94.         root=tree(root, NULL, w);
  95.     }
  96.     treeprint(root);
  97.     
  98.     //вводим элемент для удаления
  99.     printf("Enter elem for deletion: ");
  100.     scanf("%d", &elem);
  101.     node *fordel;
  102.  
  103.     //если элемент с таким значением есть
  104.     if(tree_find(root, elem) != NULL)
  105.     {
  106.       //удаляем его
  107.       fordel = tree_find(root, elem);
  108.       if(fordel->parent->info < elem)
  109.         tree_remove(fordel->parent->rl);
  110.       else
  111.         tree_remove(fordel->parent->ll);
  112.       printf("After deletion: \n");
  113.       treeprint(root);
  114.     }
  115.     
  116.     getch();
  117.     return 0;
  118. }

Решение задачи: «Рекурсивное удаление дерева»

textual
Листинг программы 
  1. #include <stdio.h>
  2. #include <conio.h>
  3. struct node // Структура узла
  4. {
  5.     int info; // Информационное поле
  6.     int c; // Счетчик
  7.     node *ll, *rl; // Левый и правый указатели
  8.     node *parent; //Родитель
  9. };
  10. // -------Функция построения дерева---------
  11. node *tree(node *p, node *dad, int w)
  12. {
  13.     if (p == NULL)
  14.     {
  15.         p = new node;
  16.         p->info = w;
  17.         p->ll = NULL;
  18.         p->rl = NULL;
  19.         p->c = 1;
  20.         p->parent=dad;
  21.     }
  22.     else if (w == p->info) // Если такая информация встречалась,
  23.     {
  24.         p->c = p->c + 1; // то счетчик количества увеличивается на 1
  25.     }
  26.     else if (w < p->info) // eсли меньше, то идем по левому указателю
  27.     {
  28.         p->ll = tree(p->ll, p, w);
  29.     }
  30.     else
  31.     {
  32.         p->rl = tree(p->rl, p, w); // иначе по правому
  33.     }
  34.     return p;
  35.     
  36.     
  37.     
  38. }
  39.  
  40. //--------- Функция обхода дерева -------------
  41. void treeprint(node *p)
  42. {
  43.     if (p != NULL)
  44.     {
  45.         treeprint(p->ll); // по левому указателю
  46.         printf("%d\t%d", p->c, p->info);
  47.         if(p->parent != NULL)
  48.           printf("\tParent: %d",  p->parent->info);
  49.         else
  50.           printf("\tNo parent!");
  51.         printf("\n");
  52.         treeprint(p->rl); // по правому указателю
  53.     }
  54. }
  55.  
  56. //--------- Функция поиска в дереве по значению узла -------------
  57. node *tree_find(node *&p, int n)
  58. {
  59.   if(p!=NULL)
  60.   {
  61.     if(p->info == n)
  62.       return p;
  63.     else if(p->info < n)
  64.       return tree_find(p->rl, n);
  65.     else
  66.       return tree_find(p->ll, n);
  67.   }
  68.   else
  69.     return NULL;
  70. }
  71.  
  72. //--------- Функция удаления дерева, начиная с заданного элемента-------------
  73. void tree_remove (node *&p)
  74. {
  75.   if(p!=NULL)
  76.   {
  77.     tree_remove(p->ll);
  78.     tree_remove(p->rl);
  79.     delete p;
  80.     p=NULL;
  81.   }
  82. }
  83.  
  84.  
  85. int main()
  86. {
  87.     node *root; // Рабочий указатель на корень дерева
  88.     int w,n,elem; // Буферная переменная, счетчик
  89.     root = NULL; //Дерево пустое
  90.     printf("Enter amount of trees' elems: ");
  91.     scanf("%d", &n);
  92.     
  93.     //вводим дерево    
  94.     for(int i=0; i<n; i++)
  95.     {
  96.         scanf("%d", &w);
  97.         root=tree(root, NULL, w);
  98.     }
  99.     treeprint(root);
  100.     
  101.     //вводим элемент для удаления
  102.     printf("Enter elem for deletion: ");
  103.     scanf("%d", &elem);
  104.     node *fordel;
  105.  
  106.     //если элемент с таким значением есть
  107.     if(tree_find(root, elem) != NULL)
  108.     {
  109.       //удаляем его
  110.       fordel = tree_find(root, elem);
  111.       if(fordel->parent->info < elem)
  112.         tree_remove(fordel->parent->rl);
  113.       else
  114.         tree_remove(fordel->parent->ll);
  115.       printf("After deletion: \n");
  116.       treeprint(root);
  117.     }
  118.     
  119.     getch();
  120.     return 0;
  121. }

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

  1. Структура узла содержит поле info для хранения информации, c для подсчета количества узлов с одинаковой информацией, поля ll и rl для хранения указателей на левое и правое поддерево соответственно, а также поле parent для хранения указателя на родительский узел.
  2. Функция tree создает и возвращает новый узел с заданной информацией. Если узел уже существует, увеличивает счетчик c на 1. Рекурсивно вызывает себя для левого и правого поддеревьев, если информация меньше или больше текущей.
  3. Функция treeprint рекурсивно обходит дерево, печатая информацию, количество потомков и, если есть, родителя каждого узла.
  4. Функция tree_find рекурсивно ищет узел с заданной информацией. Если узел с такой информацией существует, возвращает его. Если узел с такой информацией не найден, возвращает NULL.
  5. Функция tree_remove рекурсивно удаляет дерево, начиная с заданного узла. Если узел пустой, возвращает NULL.
  6. В функции main создается указатель root на корень дерева, который изначально равен NULL. Пользователю предлагается ввести количество элементов для создания дерева, а затем сами элементы. После создания дерева выводится его структура. Затем пользователю предлагается ввести элемент для удаления, и если такой элемент существует, он удаляется из дерева. После удаления выводится обновленная структура дерева.

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

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

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

14   голосов , оценка 3.929 из 5

Нужна аналогичная работа?

Оформи быстрый заказ и узнай стоимость

Бесплатно
Оформите заказ и авторы начнут откликаться уже через 10 минут
Похожие ответы