Загвоздка с деревом, динамические структуры данных - C (СИ)

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

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

Всем доброго времени суток.
Столкнулся с такой проблемой. В языке С новичок и нужно написать программу с динамическими структурами данных. Программу, реализующую структуру данных и методы работы с ней, а также дополнительный метод обработки (1) Элементом структуры должно быть целое число. (1) Двоичное дерево, минимальное значение, пример результата = 57, для следующих элементов 10, 5, 6, 23, 11, 2. Также нужно вставить обязательно в программу следующие блоки кода. 1) Вставка элемента
Листинг программы
  1. void tree_insert(
  2. node* root,
  3. int x
  4. );
2) Печать всех элементов
Листинг программы
  1. void tree_print(
  2. node* root
  3. );
3) Удаление элемента
Листинг программы
  1. void tree_remove(
  2. node* root,
  3. int x
  4. );
4) Удаление всех элементов
Листинг программы
  1. void tree_erase (
  2. node* root
  3. );
Смог написать для списка, но на дереве загвоздка. Вот пример списка.
Листинг программы
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3.  
  4. struct node {
  5. int data;
  6. struct node * next;
  7. };
  8. void CreateList(node * list) {
  9. list->next=NULL;
  10. };
  11. void list_insert(node *list, int x) {
  12. node *uzel;
  13. if (list->next == NULL) {
  14. list->next = (node *) malloc(sizeof(uzel));
  15. list->next->data = x;
  16. list->next->next = NULL;
  17. return;
  18. };
  19. if (list->next->data >= x) {
  20. uzel = (node *) malloc(sizeof(uzel));
  21. uzel->data = x;
  22. uzel->next = list->next;
  23. list->next = uzel;
  24. } else {
  25. list_insert(list->next, x);
  26. }
  27. };
  28. void list_remove(node *list, int x) {
  29. node * tmp;
  30. if(list->next->data == x) {
  31. tmp = list->next->next;
  32. free(list->next);
  33. list->next = tmp;
  34. } else {
  35. list_remove(list->next, x);
  36. }
  37. };
  38. void list_erase(node *list){
  39. node * tmp;
  40. tmp = list->next;
  41. int ms[100]={0};
  42. int ix=0;
  43. while(tmp !=NULL) {
  44. node* next=tmp->next;
  45. free(tmp);
  46. tmp=next;
  47. }
  48. list->next=NULL;
  49. }
  50. void list_print(node *list) {
  51. node * tmp;
  52. if(list->next == NULL) {
  53. printf("List is empty");
  54. return;
  55. }
  56. tmp = list->next;
  57. while(tmp !=NULL) {
  58. printf("%d ",tmp->data);
  59. tmp=tmp->next;
  60. };
  61. };
  62. int difference(node *list) {
  63. int i = 0 ;
  64. node * tmp = list;
  65. int max=tmp->next->data;
  66. int min=tmp->next->data;
  67. while(tmp->next != NULL) {
  68. if(tmp->next->data >max){
  69. max=tmp->next->data;
  70. }
  71. if(tmp->data <min){
  72. min=tmp->data;
  73. }
  74. i++;
  75. tmp=tmp->next;
  76. };
  77. return max-min;
  78. };
  79. int main () {
  80. node list;
  81. CreateList(&list);
  82. int i=0;
  83. while(i<15){
  84. list_insert(&list, rand() % 111);
  85. i++;
  86. }
  87. printf("\nPrinting all of the elements....\n");
  88. list_print(&list);
  89. list_remove(&list, 7);
  90. list_remove(&list, 41);
  91. list_remove(&list, 44);
  92. list_remove(&list, 54);
  93. list_remove(&list, 62);
  94. printf("\n\nPrinting all of the elements after removing 5 of them....\n");
  95. list_print(&list);
  96. printf("\n\nThe difference between maximum and minimum : %d\n", difference(&list));
  97.  
  98. return 0;
  99. };

Решение задачи: «Загвоздка с деревом, динамические структуры данных»

textual
Листинг программы
  1. #include <stdio.h>
  2. #include <stdlib.h>
  3. #include <malloc.h>
  4.  
  5. typedef struct _node {
  6.     int x;
  7.     struct _node* left;
  8.     struct _node* right;
  9. } node;
  10.  
  11. node* tree_insert(node** root, int x);
  12. void  tree_remove(node** root, int x);
  13. void  tree_print(FILE* _out, const node* root);
  14. void  tree_erase(node* root);
  15.  
  16.  
  17. int main(void){
  18.     int   i;
  19.     node* tr = NULL;
  20.  
  21.     for(i = 0; i < 30; ++i)
  22.         tree_insert(&tr, rand() % 10);
  23.  
  24.     tree_print(stdout, tr);
  25.     putchar('\n');
  26.  
  27.     tree_remove(&tr, 5);
  28.     tree_remove(&tr, 6);
  29.     tree_remove(&tr, 7);
  30.     tree_print(stdout, tr);
  31.     tree_erase(tr);
  32.     return 0;
  33. }
  34.  
  35. //вставка
  36. node* tree_insert(node** root, int x){
  37.     node* p = *root;
  38.     while(p != NULL){
  39.         if(x == p->x)
  40.             return p;
  41.         else if(x < p->x){
  42.             root = &p->left;
  43.             p    = p->left;
  44.         } else {
  45.             root = &p->right;
  46.             p    = p->right;
  47.         }
  48.     }
  49.  
  50.     p = (node*)malloc(sizeof(node));
  51.     if(p != NULL){
  52.         p->x    = x;
  53.         p->left = p->right = NULL;
  54.         *root   = p;
  55.     }
  56.     return p;
  57. }
  58.  
  59. //удаление
  60. void tree_remove(node** root, int x){
  61.     node* p1, *p2, *p = *root;
  62.     while(p != NULL){
  63.         if(x == p->x)
  64.             break;
  65.         else if(x < p->x){
  66.             root = &p->left;
  67.             p    = p->left;
  68.         } else {
  69.             root = &p->right;
  70.             p    = p->right;
  71.         }
  72.     }
  73.  
  74.     if(p == NULL)
  75.         return;
  76.     else if(p->right == NULL)
  77.         *root = p->left;
  78.     else {
  79.         p2 = p->right;
  80.         if(p2->left == NULL){
  81.             p2->left = p->left;
  82.             *root    = p2;
  83.         } else {
  84.             for(p1 = p2->left; p1->left != NULL; p1 = p2->left)
  85.                 p2 = p1;
  86.  
  87.             p2->left  = p1->right;
  88.             p1->left  = p->left;
  89.             p1->right = p->right;
  90.             *root     = p1;
  91.         }
  92.     }
  93.     free(p);
  94. }
  95.  
  96. //печать
  97. void tree_print(FILE* _out, const node* root){
  98.     if(root != NULL){
  99.         if(root->left != NULL)
  100.             tree_print(_out, root->left);
  101.  
  102.         fprintf(_out, "%d ", root->x);
  103.  
  104.         if(root->right != NULL)
  105.             tree_print(_out, root->right);
  106.     }
  107. }
  108.  
  109. //удаление всех
  110. void tree_erase(node* root){
  111.     if(root != NULL){
  112.         if(root->left != NULL)
  113.             tree_erase(root->left);
  114.         if(root->right != NULL)
  115.             tree_erase(root->right);
  116.         free(root);
  117.     }
  118. }

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

  1. Создание дерева из 30 элементов со случайными значениями от 0 до 9.
  2. Вставка элемента 5 в дерево.
  3. Вставка элемента 6 в дерево.
  4. Вставка элемента 7 в дерево.
  5. Печать дерева на экран.
  6. Удаление элементов 5, 6, 7 из дерева.
  7. Печать дерева на экран.
  8. Удаление всех элементов из дерева.

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


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

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

10   голосов , оценка 4.1 из 5

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

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

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