Удалить из дерева все узлы, в текстах которых заданное слово, и указать количество удалений - C (СИ)

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

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

Доброго времени суток. Помогите, пожалуйста, с деревом 1) поля записей (структуры): <Ключ>, <Текст> - упорядочение за ключами; 2) прямой (от корня) слева направо, 3) удалить из дерева все узлы, в текстах которых заданное слово, и указать количество удалений 4) симметричный справа налево; 5) вытирания всего дерева.

Решение задачи: «Удалить из дерева все узлы, в текстах которых заданное слово, и указать количество удалений»

textual
Листинг программы 
  1. #include<stdio.h>
  2. #include<ctype.h>  
  3. #include<string.h> 
  4. #include<stdlib.h>
  5. #include <locale>
  6. #define N 100
  7.  
  8.  
  9.  
  10. typedef struct info{
  11.     int key;
  12.     char *text;
  13. } INFO;
  14. typedef struct tree_node{
  15.     INFO elem;
  16.     struct tree_node *right, *left;
  17. } TreeNode;
  18.  
  19. TreeNode* CreateNode(int ind, char *buf);           // ГґГіГ*êö³ÿ ñòâîðþº îäèГ* åëåìåГ*ГІ äåðåâГ*
  20. void AddNode(TreeNode* pnew, TreeNode** root_adr);  // ГґГіГ*êö³ÿ ïðèºäГ*ГіВє åëåìåГ*ГІ äî äåðåâГ*
  21. void PrintTreeNode(TreeNode* proot);                // äðóê ГўГ±ВіГµ åëåìåГ*ГІВіГў äåðåâГ*
  22. void ShowTreeNode(TreeNode *proot, int lev);
  23. void ShowLevels(void);                              // ГґГіГ*êö³ÿ âèâîäèòü Г*Г* ГҐГЄГ°Г*Г* Г*îìåðè ð³âГ*ВіГў äåðåâГ*
  24. int TreeNodeHeight(TreeNode* proot);                // ГўГЁГ§Г*Г*Г·Г*Вє âèñîòó äåðåâГ*
  25. void Del(char *word, TreeNode **pot);
  26. void FreNod(TreeNode*p);
  27. void FreeDer(TreeNode *p);
  28.  
  29. TreeNode *root; 
  30.  
  31. int main(void) {
  32.     setlocale (LC_ALL, "rus");
  33.     FILE *fp;                   // ГўГЄГ*ç³âГ*ГЁГЄ Г*Г* ГґГ*éëîâèé ïîò³ê
  34.     TreeNode *node;             // ГўГЄГ*ç³âГ*ГЁГЄ çáåð³ãГ*òèìå Г*äðåñó îäГ*îãî åëåìåГ*ГІГі äåðåâГ*
  35.     char name[15]="D:\\NEW.txt", buf[100], word[N];;    
  36.     int b, n;           
  37.     //printf("ÂâåäiГІГј iГ¬\'Гї ГґГ*éëó: ");
  38.     //gets(name);               
  39.     if((fp = fopen(name, "r")) == NULL) {
  40.         puts("Г”Г*éë Г*ГҐ Г§Г*Г*éäåГ*Г®!!!");
  41.         system ("pause");
  42.         return 0; 
  43.     }
  44.     while(fscanf(fp, "%d %s", &b, buf) == 2) {      // ç÷èòóâГ*Г*Г*Гї Г¤Г*Г*ГЁГµ Г§ ГґГ*éëó
  45.         node = CreateNode(b, buf);                  // ïåðåäГ*ºìî Г¤Г*Г*Ві äëÿ ñòâîðåГ*Г*Гї åëåìåГ*ГІГі äåðåâГ*, îòðèìóºìî Г*Г* Г*üîãî ГўГЄГ*ç³âГ*ГЁГЄ
  46.         AddNode(node, &root);                       // ïåðåäГ*ºìî öåé ГўГЄГ*ç³âГ*ГЁГЄ Ві ГўГЄГ*ç³âГ*ГЁГЄ Г*Г* êîð³Г*Гј äåðåâГ* Гі ГґГіГ*êö³þ, ГїГЄГ* ïðèºäГ*Г*Вє Г*Г*Гё åëåìåГ*ГІ Гі ïîòð³áГ*ГҐ ì³ñöå äåðåâГ*
  47.     }
  48.     fclose(fp);         
  49.  
  50.     puts("\nÑôîðìîâГ*Г*ГҐ äåðåâî:\n");
  51.     PrintTreeNode(root);        // äðóêóºìî Г¤Г*Г*Ві äåðåâГ* ïðÿìèì Г±ГЇГ°Г*ГўГ* Г*Г* ë³âî ïîðÿäêîì ïðîõîäæåГ*Г*Гї
  52.     puts("\nÑòðóêòóðГ* äåðåâГ*:\n");
  53.     ShowTreeNode(root,1);       // âèâîäèìî Г¤Г*Г*Ві Гі âèãëÿä³ äåðåâГ* ïîâåðГ*óòîãî Г*Г* 90 ГЈГ°Г*äóñ³â âë³âî
  54.     puts("\nÑëîâî äëÿ ГўГЁГ¤Г*ëåГ*Г*Гї: ");
  55.     gets(word);
  56.     n = TreeNodeHeight(root);
  57.     while (n){
  58.           Del(word, &root);
  59.           n--;
  60.     }
  61.     ShowTreeNode(root,1);
  62.     getchar ();
  63.     return 0;
  64. }
  65.     
  66. TreeNode* CreateNode(int ind, char *buf){   // ГґГіГ*êö³ÿ ñòâîðþº îäèГ* åëåìåГ*ГІ äåðåâГ*
  67.     TreeNode *pel;                                                              // ГўГЄГ*ç³âГ*ГЁГЄ Г*Г* îäèГ* åëåìåГ*ГІ äåðåâГ*
  68.     
  69.     pel = (TreeNode*)malloc(sizeof(TreeNode));  // âèä³ëÿºìî äëÿ Г*üîãî äèГ*Г*ì³÷Г*Гі ГЇГ*ìÿòü
  70.     pel->left = pel->right = NULL;              
  71.     
  72.     pel->elem.text = (char*)malloc(strlen(buf)+1);  // âèä³ëÿºìî äèГ*Г*ì³÷Г*Гі ГЇГ*ìÿòü äëÿ Г*Г*çâè
  73.     strcpy(pel->elem.text, buf);                        
  74.     pel->elem.key = ind;    
  75.  
  76.     return pel; // ïîâåðòГ*ºìî ГўГЄГ*ç³âГ*ГЁГЄ Г*Г* Г*îâèé åëåìåГ*ГІ
  77. }
  78.  
  79. void AddNode(TreeNode* pnew, TreeNode** root_adr){  // ïðèºäГ*Г*Г*Г*Гї åëåìåГ*ГІГі äî âïîðÿäêîâГ*Г*îãî äåðåâГ*
  80.     TreeNode *proot = *root_adr;    // ГўГЄГ*ç³âГ*ГЁГЄ Г*Г* êîð³Г*Г*ГЁГ© åëåìåГ*ГІ
  81.     if (proot == NULL) {            // ГїГЄГ№Г® åëåìåГ*ГІГі Г*ГҐ ВіГ±Г*ГіВє, Г*îâèé åëåìåГ*ГІ Г§Г*éìГ*Вє öå ì³ñöå
  82.         *root_adr = pnew;
  83.         return;
  84.     }
  85.     if(proot->elem.key == pnew->elem.key) free(pnew);
  86.     if(proot->elem.key < pnew->elem.key) AddNode(pnew,&proot->right);
  87.     if(proot->elem.key > pnew->elem.key) AddNode(pnew,&proot->left);
  88. }
  89. void PrintTreeNode(TreeNode* proot)                 // äðóêóºìî äåðåâî Гў ïðÿìîìó ïîðÿäêó çë³âГ* Г*Г*ГЇГ°Г*ГўГ®
  90. {
  91.     if (proot == NULL) 
  92.         return;             // ГїГЄГ№Г® åëåìåГ*ГІГ* Г*ГҐ ВіГ±Г*ГіВє âèõ³ä
  93.     printf(" %d. %s\n", proot->elem.key, proot->elem.text); 
  94.     PrintTreeNode(proot->left);     
  95.     PrintTreeNode(proot->right);    
  96. }
  97.  
  98. void ShowTreeNode(TreeNode *proot, int lev){    // âèâîäèòü Г¤Г*Г*Ві Гі âèãëÿä³ äåðåâГ* ïîâåðГ*óòîãî Г*Г* 90 ГЈГ°Г*äóñ³â âë³âî
  99.     if (lev == 1)   
  100.         ShowLevels();               // ГїГЄГ№Г® öå êîð³Г*Гј âèâîäèìî Г*îìåðè ð³âГ*ВіГў äåðåâГ*
  101.     if (proot == NULL) 
  102.         return; 
  103.     ShowTreeNode (proot->right, lev+1);             // ðóõГ*ºìîñü ГЇГ® ГЇГ°Г*âîìó ï³ääåðåâ³
  104.     printf("%*c%d. %s\n", lev*8, ' ', proot->elem.key, proot->elem.text);   
  105.     ShowTreeNode (proot->left, lev+1);              // ðóõГ*ºìîñü ГЇГ® ë³âîìó ï³ääåðåâ³
  106. }
  107.  
  108. void ShowLevels(void){      // âèâîäèòü Г*îìåðè ð³âГ*ВіГў äåðåâГ*
  109.     int level;
  110.     printf("ГђiГўГҐГ*Гј:  ");
  111.     for(level = 1; level <= TreeNodeHeight(root); level++)  
  112.         printf("%-8d", level);
  113.     printf("\n");
  114. }
  115.  
  116. int TreeNodeHeight(TreeNode* proot)     // ГґГіГ*êö³ÿ ГўГЁГ§Г*Г*Г·Г*Вє âèñîòó äåðåâГ*
  117. {
  118.     int lht, rht;
  119.     if (proot == NULL) 
  120.         return 0;   
  121.     lht = TreeNodeHeight(proot->left);  // ðóõГ*ºìîñü ГЇГ® ë³âîìó ï³ääåðåâ³
  122.     rht = TreeNodeHeight(proot->right); // ðóõГ*ºìîñü ГЇГ® ГЇГ°Г*âîìó ï³ääåðåâ³
  123.     if (lht > rht)
  124.         return lht+1;
  125.     else
  126.         return rht+1;
  127. }
  128.  
  129. void Del(char *word, TreeNode **pot){
  130.     TreeNode *proot = *pot, *pnewr, *ppar;
  131.     if(proot==NULL) return;
  132.     int subtr;
  133.     int cmp = strcmp(root->elem.text, word);
  134.     if(cmp==0){
  135.         if(proot->left==NULL && proot->right==NULL)
  136.             subtr=0;
  137.         else if( proot->left == NULL)
  138.                  subtr= 1;
  139.              else if( proot->right == NULL)
  140.                       subtr = -1;
  141.                   else subtr = 2;
  142.         switch(subtr){
  143.                       case(0): *pot=NULL; break;
  144.                       case(-1): *pot=proot->left; break;
  145.                       case(1): *pot= proot->right; break;
  146.                       case(2):
  147.                               pnewr=proot->left;
  148.                               ppar=proot;
  149.                               while(pnewr->right!=NULL){
  150.                                      ppar = pnewr;
  151.                                      pnewr = pnewr->right;
  152.                               }
  153.                               pnewr->right = proot->right;
  154.                               if (pnewr != proot->left){
  155.                                         ppar->right = pnewr->left;
  156.                                         pnewr->left = proot->left;
  157.                               }
  158.                               *pot = pnewr;
  159.         }
  160.         FreeDer(root);
  161.         return;
  162.     }
  163.     if(cmp>0)
  164.          Del(word,&root->left);
  165.     else
  166.          Del(word,&root->right);
  167. }
  168.  
  169. void FreNod(TreeNode*p){
  170.         free(p->elem.text);
  171.         free(p);
  172. }
  173.  
  174. void FreeDer(TreeNode *p){
  175.         FreeDer(p->left);   
  176.         FreeDer(p->right);
  177.         FreNod(p);
  178. }

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

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

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

6   голосов , оценка 4.333 из 5

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

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

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