1

Приветсствую, мне необходимо пройти через все узлы в деструкторе и удалить потомков для каждого и так до рута, но не могу написать правильный алгоритм такого прохода. В каком то месте у меня всегда возникает бесконечный цикл. Мне нужно обойтись без рекурсии.

введите сюда описание изображения

Структура узла

struct node {
    node* children[128] = {};       
    node* parent = nullptr;        
    char payload = 0;                    
    bool is_end = false;            
};

Деструктор дерева

tree::~tree()
{
    node *current_node = m_root;
    bool flag = false;
    bool flag2;
    size_t tmp;

    while(!flag) {
        tmp = 0;
        for (auto j: current_node->children) {
            if (j != nullptr) tmp++;
        }
        if (tmp == 0) {
            if (current_node->parent == nullptr) {
                delete m_root;
                flag = true;
            } else {
                current_node = current_node->parent;
            }
        } else {
            //down
            while (true) {
                tmp = 0;
                for (auto j : current_node->children) {
                    if (j != nullptr) {
                        current_node = j;
                        break;
                    }
                    tmp++;
                }
                if (tmp != 128) continue;
                else break;
            }

            while (true) {
                tmp = 0;
                for (auto j : current_node->parent->children) {
                    if (j != nullptr) tmp++;
                }
                current_node = current_node->parent;
                for (auto j : current_node->parent->children) {
                    delete j;
                    break;
                }
                if (tmp == 1) {
                    continue;
                } else {
                    break;
                }
            }
        }

    }
}

1 ответ 1

1

Идея состоит в том, чтобы вместо неявного использования стека, как это было бы в рекурсии, использовать его явным образом.

корень кладем в стек

цикл, если стек не пуст
   взять верхушку стека (из стека не удалять)
   если нет потомков 
       удалить верхушку из стека
       удалить вершину из памяти
    иначе
        положить всех потомков в стек и отсоединить их от вершины      
конец цикла
7
  • Не совсем понимаю, что означает отсоединить их от вершины. Насколько я понял, мне необходимо при помощи delete удалить всех потомков в родительском узле, которые содержатся в массиве children. К сожалению не могу использовать стек, попытался хранить узлы в векторе, но получаю ошибку памяти.
    – quasi
    Commented 7 дек. 2022 в 23:09
  • Отсоединить от вершины - это значит, удалить указатели на них из массива children
    – gbg
    Commented 7 дек. 2022 в 23:31
  • Если вы можете использовать вектор, вы можете работать с ним, как со стеком.
    – gbg
    Commented 7 дек. 2022 в 23:31
  • Понял, да мне не хватало этой части с удалением из массива. Но теперь получаю ошибку free(): invalid pointer. Все равно не могу понять в чем проблема
    – quasi
    Commented 7 дек. 2022 в 23:41
  • Я получаю верхушку "стека" при помощи current_node=vec.back(). Потом в случае отсутствия потомков сначала удаляю его из "стека" при помощи vec.pop_back() а затем delete current_node. Такое ощущение что я пытаюсь удалить то, на что у меня уже нет указателя. Далее та часть с потомками. Я сначала добавляю их в вектор а потом удаляю, разве я не получаю таким образом nullptr в векторе?
    – quasi
    Commented 8 дек. 2022 в 0:06

Ваш ответ

Нажимая «Отправить ответ», вы соглашаетесь с условиями пользования и подтверждаете, что прочитали политику конфиденциальности.

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