0

Элемент дерева:

typedef struct tree{
    char * word;
    struct tree *left,*right;
}TREE;

#define NL 7

Нужно удалить все элементы, для которых длина word >= NL Функция удаления одного элемента:

#define NoSubTree    0
#define LeftSubTree -1
#define RightSubTree 1
#define TwoSubTrees  2

void deleteNode(char* word, TREE** his_root)
{
    TREE* proot = *his_root, * new_root, *ppar;
    int cmp, substr, word_l, root_l;

    if (proot == NULL)
    {
        return;
    }

    cmp = strcmp(proot->word, word);
    word_l = strlen(word);
    root_l = strlen(proot->word);

    if (cmp == 0)
    {
        if (proot->left == NULL && proot->right == NULL)
        {
            substr = NoSubTree;
        }
        else if (proot->right == NULL)
        {
            substr = LeftSubTree;
        }
        else if (proot->left == NULL)
        {
            substr = RightSubTree;
        }
        else
        {
            substr = TwoSubTrees;
        }

        switch (substr)
        {
            case NoSubTree:
                *his_root  = NULL;
                break;

            case LeftSubTree:
                *his_root = proot->left;
                break;

            case RightSubTree:
                *his_root = proot->right;
                break;

            case TwoSubTrees:
                new_root = proot->left;
                ppar = proot;

                while (new_root->right != NULL)
                {
                    ppar = new_root;
                    new_root = new_root->right;
                }

                new_root->right = proot->right; // присоединяем правое поддерево

                if (new_root != proot->left)  //если не вершина левого поддерева
                {
                    ppar->right = new_root->left;
                    new_root->left = proot->left; // присоединяем левое поддерево
                }

                *his_root = new_root;//замена корня
                freeNode(proot);
                return;
        }
    }

    if (root_l > word_l || (cmp > 0 && root_l == word_l))
    {
        deleteNode(word, &proot->left);
    }

    if (word_l > root_l || (cmp < 0 && root_l == word_l))
    {
        deleteNode(word, &proot->right);
    }
}

Проход по дереву и поиск подходящих слов (root - глобальный указатель на корень).

void search_words(TREE* proot)
{
    if (proot == NULL)
    {
        return;
    }

    search_words(proot->right);

    if (strlen(proot->word) >= NL)
    {
        deleteNode(proot->word, &root);
    }

    search_words(proot->right);
}

Удаление 1 элемента работает, как я понимаю, проблема именно в поиске слов.

1 ответ 1

1

Не вдаваясь в само удаление...

Вы рекурсивно дважды ищете только в правом поддереве? Левое не интересует?

search_words(proot->right);         /////////

if (strlen(proot->word) >= NL) ...

search_words(proot->right);         /////////

И еще - не принципиально, но это плохой стиль - назвать функцию функцией поиска, но в ней еще и удалять...

1
  • Действительно, забыл заменить после копипаста, теперь все работает, спасибо.
    – Hardc0re
    13 янв 2017 в 6:20

Ваш ответ

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

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