0
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define BUFF 256

typedef struct node {
    char *pnomber;
    int count;
    struct node *left;
    struct node *right;
} Node;

Node *AddNode(Node *Root, char *w) {
    int cond;
    if(Root == NULL) { 
        Node *Root = malloc(sizeof(Node));
        Root->count = 1;
        Root->pnomber = strdup(w);
        Root->left = Root->right = NULL;
        return Root;
        } else if((cond = strcmp(w, Root->pnomber)) == 0) {
            Root->count++;
        } else if(cond < 0) 
            Root->left = AddNode(Root->left, w);
        else
            Root->right = AddNode(Root->right, w);
    return Root;
}

Node *PrintWood(Node *Root) {
    if(Root != NULL) { 
        PrintWood(Root->right);
        printf("pnomber-->%s, count-->%d\n", Root->pnomber, Root->count);
        PrintWood(Root->left);
    } else return 0;
}

Node *SearchCount(Node *Root) {
    Node *SC = Root;
    
    if(SC == NULL) {return SC;}
    else { 
        if(SC->count >= 2)
            printf("pnomber-->%s, count->%d", SC->pnomber, SC->count);
            //printf("\n");
        return SearchCount(SC->left);
        return SearchCount(SC->right);
    }
}

Node *RootDelete(Node *Root) {
    Node *LM = NULL; // Локальный минимум
    Node *SN = NULL; // Найденый узел
    Node *TMP = NULL;
    SN = SearchCount(Root); //Удаляемый элемент 
    if(SN == NULL) return NULL; // Дерево пустое
    if(SN != NULL) { // Дерево не пустое
        if((SN->left == NULL) && (SN->right == NULL)) { // Нет ответвлений
            free(SN);
            return NULL;
        } else if(SN->left == NULL) { // Есть только RIGHT потомок
            TMP = SN->right; // TMP правый для SN 
            free(SN); // Стираем старый SN 
            return TMP;
        } else if(SN->right == NULL) { // Есть только LEFT потомок
            TMP = SN->left; // TMP левый для SN
            free(SN); // Стираем старый SN 
            return TMP;
        } else if((SN->left != NULL) && (SN->right != NULL)) { // Есть обе ветки
            LM = SN->right; // Перезаписываю  на правый потомок LM(лм стал правым для сн)
            //Node *PAR = SN; // Задаем родителя для LM
            while(LM->left != NULL) {
                //PAR = LM;
                LM = LM->left; // Влево до упора находим минимум
            }
            SN->pnomber = LM->pnomber; // Меняем значение узла на занчение лок мин
            SN->count = 1; // Значение счетчика приводим к единице
            SN = LM; // Перезаписываем самый малый элемент на место того, котор надо удалить
            //LMM = PAR;
            printf("pnomberSN-->%s, count-->%d\n", SN->pnomber, SN->count);
            printf("\n");
            printf("pnomberLM-->%s, count-->%d\n", LM->pnomber, LM->count);
            printf("\n");
            free(LM); // Стираем старый LM
            return SN; // Возвращаем новое значение верщины 
            
        } 
        //free(SN);
    }
} 
/*
void DeleteWood(Node *Root) {
    if(Root != NULL) { 
        DeleteWood(Root->left);
        DeleteWood(Root->right);
        free(Root);
    }
} 
*/
int main() {
    const char *text = "Number.txt";
    Node *Root = NULL;
    char LineBuffer[BUFF];
    char*p;
    FILE *fp = fopen(text, "rb");
    if(!fp){
        printf("file not open\n");
        return -1;
    } 
    while(fgets(LineBuffer, sizeof(LineBuffer), fp)) {
        if(p = strchr(LineBuffer, '\n')) *p = 0;
        Root = AddNode(Root, LineBuffer);
    }
    PrintWood(Root);
    printf("\n");
    printf("\n");
    SearchCount(Root);
    printf("\n");
    RootDelete(Root);
    printf("After delete------\n");
    PrintWood(Root);
    //DeleteWood(Root);

    return 0;
}

Здравствуйте, подскажите пожалуйста как работает функция удаления узла из дерева, пробовал несколько вариантов,ничего не выходит.Функция должна удалять из дерева все элементы, количество которых в файле - два и более:(

2
  • Так в ней же всё комментариями написано. Каждый шаг. Что ещё тут можно пояснить? А о каких элементах из каких файлов идет речь? Функция работает просто - выбирается узел при помощи функции SN = SearchCount(Root);, потом этот узел удаляется из дерева.
    – DmitryK
    29 сен 2022 в 7:50
  • Я то-же так думал. Старательно все расписывал, комментировать, рисовал деревья на листочке. Не работает. А файл подгрузить не могу. 29 сен 2022 в 11:48

1 ответ 1

1

У вас ничего не удаляется, потому что функция SearchCount() всегда возвращает NULL. Она вызывается рекурсивно по левой ветке, пока не дойдет до SC->left == NULL. И кстати, если бы вы хоть раз прошли по программе дебаггером, вы бы это сразу увидели.

Node *SearchCount(Node *Root) 
{
    Node *SC = Root;
    if(SC == NULL) 
    { return SC; }
    else 
    {  
        ....
        return SearchCount(SC->left);
        return SearchCount(SC->right);
    }
}

Ну а уже в функции удаления, срабатывает условие на выход из нулевого дерева.

Node *RootDelete(Node *Root) {
    ....
    SN = SearchCount(Root); // !!! SN всегда == NULL
    if(SN == NULL) return NULL; // Дерево пустое

PS для тестирования работы программы заполняйте дерево вот так, без всяких файлов

int main()
{
    Root = AddNode(Root, "Number5");
    Root = AddNode(Root, "Number3");
    Root = AddNode(Root, "Number7");
    Root = AddNode(Root, "Number7");
3
  • Спасибо), вы очень помогли. Я не мог выкурить, почему удаляет первый элемент дерева, остальное оставляет как есть... 29 сен 2022 в 14:43
  • Вообще-то она ничего не удаляет. Спасибо здесь - принятый ответ! :) Нажмите галочку слева от ответа.
    – DmitryK
    29 сен 2022 в 14:44
  • Это сейчас не удаляет))), до этого вариант был - удалял первый элемент. 29 сен 2022 в 15:23

Ваш ответ

By clicking “Отправить ответ”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.