Удалить из дерева все узлы, в текстах которых заданное слово, и указать количество удалений - C (СИ)
Формулировка задачи:
Доброго времени суток. Помогите, пожалуйста, с деревом
1) поля записей (структуры): <Ключ>, <Текст> - упорядочение за ключами;
2) прямой (от корня) слева направо,
3) удалить из дерева все узлы, в текстах которых заданное слово, и указать количество удалений
4) симметричный справа налево;
5) вытирания всего дерева.
Решение задачи: «Удалить из дерева все узлы, в текстах которых заданное слово, и указать количество удалений»
textual
Листинг программы
#include<stdio.h>
#include<ctype.h>
#include<string.h>
#include<stdlib.h>
#include <locale>
#define N 100
typedef struct info{
int key;
char *text;
} INFO;
typedef struct tree_node{
INFO elem;
struct tree_node *right, *left;
} TreeNode;
TreeNode* CreateNode(int ind, char *buf); // ГґГіГ*êö³ÿ ñòâîðþº îäèГ* åëåìåГ*ГІ äåðåâГ*
void AddNode(TreeNode* pnew, TreeNode** root_adr); // ГґГіГ*êö³ÿ ïðèºäГ*ГіВє åëåìåГ*ГІ äî äåðåâГ*
void PrintTreeNode(TreeNode* proot); // äðóê ГўГ±ВіГµ åëåìåГ*ГІВіГў äåðåâГ*
void ShowTreeNode(TreeNode *proot, int lev);
void ShowLevels(void); // ГґГіГ*êö³ÿ âèâîäèòü Г*Г* ГҐГЄГ°Г*Г* Г*îìåðè ð³âГ*ВіГў äåðåâГ*
int TreeNodeHeight(TreeNode* proot); // ГўГЁГ§Г*Г*Г·Г*Вє âèñîòó äåðåâГ*
void Del(char *word, TreeNode **pot);
void FreNod(TreeNode*p);
void FreeDer(TreeNode *p);
TreeNode *root;
int main(void) {
setlocale (LC_ALL, "rus");
FILE *fp; // ГўГЄГ*ç³âГ*ГЁГЄ Г*Г* ГґГ*éëîâèé ïîò³ê
TreeNode *node; // ГўГЄГ*ç³âГ*ГЁГЄ çáåð³ãГ*òèìå Г*äðåñó îäГ*îãî åëåìåГ*ГІГі äåðåâГ*
char name[15]="D:\\NEW.txt", buf[100], word[N];;
int b, n;
//printf("ÂâåäiГІГј iГ¬\'Гї ГґГ*éëó: ");
//gets(name);
if((fp = fopen(name, "r")) == NULL) {
puts("Г”Г*éë Г*ГҐ Г§Г*Г*éäåГ*Г®!!!");
system ("pause");
return 0;
}
while(fscanf(fp, "%d %s", &b, buf) == 2) { // ç÷èòóâГ*Г*Г*Гї Г¤Г*Г*ГЁГµ Г§ ГґГ*éëó
node = CreateNode(b, buf); // ïåðåäГ*ºìî Г¤Г*Г*Ві äëÿ ñòâîðåГ*Г*Гї åëåìåГ*ГІГі äåðåâГ*, îòðèìóºìî Г*Г* Г*üîãî ГўГЄГ*ç³âГ*ГЁГЄ
AddNode(node, &root); // ïåðåäГ*ºìî öåé ГўГЄГ*ç³âГ*ГЁГЄ Ві ГўГЄГ*ç³âГ*ГЁГЄ Г*Г* êîð³Г*Гј äåðåâГ* Гі ГґГіГ*êö³þ, ГїГЄГ* ïðèºäГ*Г*Вє Г*Г*Гё åëåìåГ*ГІ Гі ïîòð³áГ*ГҐ ì³ñöå äåðåâГ*
}
fclose(fp);
puts("\nÑôîðìîâГ*Г*ГҐ äåðåâî:\n");
PrintTreeNode(root); // äðóêóºìî Г¤Г*Г*Ві äåðåâГ* ïðÿìèì Г±ГЇГ°Г*ГўГ* Г*Г* ë³âî ïîðÿäêîì ïðîõîäæåГ*Г*Гї
puts("\nÑòðóêòóðГ* äåðåâГ*:\n");
ShowTreeNode(root,1); // âèâîäèìî Г¤Г*Г*Ві Гі âèãëÿä³ äåðåâГ* ïîâåðГ*óòîãî Г*Г* 90 ГЈГ°Г*äóñ³â âë³âî
puts("\nÑëîâî äëÿ ГўГЁГ¤Г*ëåГ*Г*Гї: ");
gets(word);
n = TreeNodeHeight(root);
while (n){
Del(word, &root);
n--;
}
ShowTreeNode(root,1);
getchar ();
return 0;
}
TreeNode* CreateNode(int ind, char *buf){ // ГґГіГ*êö³ÿ ñòâîðþº îäèГ* åëåìåГ*ГІ äåðåâГ*
TreeNode *pel; // ГўГЄГ*ç³âГ*ГЁГЄ Г*Г* îäèГ* åëåìåГ*ГІ äåðåâГ*
pel = (TreeNode*)malloc(sizeof(TreeNode)); // âèä³ëÿºìî äëÿ Г*üîãî äèГ*Г*ì³÷Г*Гі ГЇГ*ìÿòü
pel->left = pel->right = NULL;
pel->elem.text = (char*)malloc(strlen(buf)+1); // âèä³ëÿºìî äèГ*Г*ì³÷Г*Гі ГЇГ*ìÿòü äëÿ Г*Г*çâè
strcpy(pel->elem.text, buf);
pel->elem.key = ind;
return pel; // ïîâåðòГ*ºìî ГўГЄГ*ç³âГ*ГЁГЄ Г*Г* Г*îâèé åëåìåГ*ГІ
}
void AddNode(TreeNode* pnew, TreeNode** root_adr){ // ïðèºäГ*Г*Г*Г*Гї åëåìåГ*ГІГі äî âïîðÿäêîâГ*Г*îãî äåðåâГ*
TreeNode *proot = *root_adr; // ГўГЄГ*ç³âГ*ГЁГЄ Г*Г* êîð³Г*Г*ГЁГ© åëåìåГ*ГІ
if (proot == NULL) { // ГїГЄГ№Г® åëåìåГ*ГІГі Г*ГҐ ВіГ±Г*ГіВє, Г*îâèé åëåìåГ*ГІ Г§Г*éìГ*Вє öå ì³ñöå
*root_adr = pnew;
return;
}
if(proot->elem.key == pnew->elem.key) free(pnew);
if(proot->elem.key < pnew->elem.key) AddNode(pnew,&proot->right);
if(proot->elem.key > pnew->elem.key) AddNode(pnew,&proot->left);
}
void PrintTreeNode(TreeNode* proot) // äðóêóºìî äåðåâî Гў ïðÿìîìó ïîðÿäêó çë³âГ* Г*Г*ГЇГ°Г*ГўГ®
{
if (proot == NULL)
return; // ГїГЄГ№Г® åëåìåГ*ГІГ* Г*ГҐ ВіГ±Г*ГіВє âèõ³ä
printf(" %d. %s\n", proot->elem.key, proot->elem.text);
PrintTreeNode(proot->left);
PrintTreeNode(proot->right);
}
void ShowTreeNode(TreeNode *proot, int lev){ // âèâîäèòü Г¤Г*Г*Ві Гі âèãëÿä³ äåðåâГ* ïîâåðГ*óòîãî Г*Г* 90 ГЈГ°Г*äóñ³â âë³âî
if (lev == 1)
ShowLevels(); // ГїГЄГ№Г® öå êîð³Г*Гј âèâîäèìî Г*îìåðè ð³âГ*ВіГў äåðåâГ*
if (proot == NULL)
return;
ShowTreeNode (proot->right, lev+1); // ðóõГ*ºìîñü ГЇГ® ГЇГ°Г*âîìó ï³ääåðåâ³
printf("%*c%d. %s\n", lev*8, ' ', proot->elem.key, proot->elem.text);
ShowTreeNode (proot->left, lev+1); // ðóõГ*ºìîñü ГЇГ® ë³âîìó ï³ääåðåâ³
}
void ShowLevels(void){ // âèâîäèòü Г*îìåðè ð³âГ*ВіГў äåðåâГ*
int level;
printf("ГђiГўГҐГ*Гј: ");
for(level = 1; level <= TreeNodeHeight(root); level++)
printf("%-8d", level);
printf("\n");
}
int TreeNodeHeight(TreeNode* proot) // ГґГіГ*êö³ÿ ГўГЁГ§Г*Г*Г·Г*Вє âèñîòó äåðåâГ*
{
int lht, rht;
if (proot == NULL)
return 0;
lht = TreeNodeHeight(proot->left); // ðóõГ*ºìîñü ГЇГ® ë³âîìó ï³ääåðåâ³
rht = TreeNodeHeight(proot->right); // ðóõГ*ºìîñü ГЇГ® ГЇГ°Г*âîìó ï³ääåðåâ³
if (lht > rht)
return lht+1;
else
return rht+1;
}
void Del(char *word, TreeNode **pot){
TreeNode *proot = *pot, *pnewr, *ppar;
if(proot==NULL) return;
int subtr;
int cmp = strcmp(root->elem.text, word);
if(cmp==0){
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): *pot=NULL; break;
case(-1): *pot=proot->left; break;
case(1): *pot= proot->right; break;
case(2):
pnewr=proot->left;
ppar=proot;
while(pnewr->right!=NULL){
ppar = pnewr;
pnewr = pnewr->right;
}
pnewr->right = proot->right;
if (pnewr != proot->left){
ppar->right = pnewr->left;
pnewr->left = proot->left;
}
*pot = pnewr;
}
FreeDer(root);
return;
}
if(cmp>0)
Del(word,&root->left);
else
Del(word,&root->right);
}
void FreNod(TreeNode*p){
free(p->elem.text);
free(p);
}
void FreeDer(TreeNode *p){
FreeDer(p->left);
FreeDer(p->right);
FreNod(p);
}