Сегфо на рекурсивном обходе дерева / удалении ветви - PullRequest
Новая
       23

Сегфо на рекурсивном обходе дерева / удалении ветви

0 голосов
/ 28 июня 2018

Я пытаюсь очистить ветки дерева , каждый узел хранит occurrence значение для каждого посещения узла во время построения, «очистка» в этом смысле относится к удалению ветвей после точки, в которой два последующих узла имеют только один occurrence:

Итак, ветвь 5->1->1->1 станет просто 5->1. Я использую рекурсивный обход дерева (который работает при печати всех путей), а затем рекурсивное удаление (который работает при разрушении объекта): 

void tree::cleanBranch(Node *node)
{
    if(!node)
        return;

    int cnt = 0;
    int ind = 0;
    // 4 possible subnodes
    for(int i = 0; i < 4; i++) {
        if(node->subnodes[i]) {
            cnt++;
            ind = i;
        }
        if(cnt > 1)
            break;
    }

    // Only 1 subnode and both current and subnode have occurrence of 1
    if(cnt == 1 && node->occurrences == 1 && 
            node->subnodes[ind]->occurrences == 1) {
        delTree(node->subnodes[ind]);
        return;
    } 

    for(int i = 0; i < 4; i++)
        cleanBranch(node->subnodes[i]);
}

И функция удаления: 

void tree::delTree(Node* node)
{
    if(node) {
        for(int i = 0; i < 4; i++)
            delTree(node->subnodes[i]);
        delete node;
    }
}

Однако он сразу же выходит из строя. Затем я создал простое дерево, 5->1->1, и оно сработало на первом delete, которое было вызвано на третьем узле, но оба cleanBranch() и delTree() проверяют, что перед удалением оно не равно нулю.

Я чувствую, что упускаю что-то очевидное, любая помощь будет признательна.

EDIT

В ответ на Qubit :

Они действительно очень просты, если честно, tree это: 

tree() { root = new Node; }

со ссылкой на участника Node *root.

И Node сам имеет: 

Node(): occurrences(0), subnodes(4)
{
    for(int i = 0; i < 4; i++)
        subnodes[i] = NULL;
}

Где occurrences - это ulong, а subnodes - это vector из Node* s.

В ответ на Эрик Алапаа :

В данный момент я не нахожусь, но я переверну его и сделаю трещину.

1 Ответ

0 голосов
/ 28 июня 2018

Код, представленный, кажется правильным. Может быть что-то не так в том, как вы создаете дерево?

Предполагая, что Node - что-то вроде этого 

struct Node
{
    unsigned long occurrences = 0;
    vector<Node*> subnodes;

    Node(): occurrences(0), subnodes(4)
    {
        for(int i = 0; i < 4; i++)
            subnodes[i] = NULL;
    }
};

и создание дерева что-то вроде этого 

// 5->1->1->1
Node* createTree()
{
    Node* root = new Node;
    root->occurrences = 5;

    Node* cur = root;
    for (int i = 0; i < 3; ++i)
    {
        cur->subnodes[0] = new Node;
        cur->subnodes[0]->occurrences = 1;
        cur = cur->subnodes[0];
    }
    return root;
}

(используя ваш стиль кода) CleanBranch работает нормально. Также добавьте 

node->subnodes[ind] = nullptr;

после 

delTree(node->subnodes[ind]);

в противном случае вы получите GPF, если случайно дважды вызовете cleanBranch для одного и того же дерева.

Кстати, рассмотрите возможность использования unique_ptr вместо Node *.

Обновление: Узел, очевидно, должен иметь такой деструктор 

~Node()
{
    for (int i = 0; i < subnodes.size(); ++i)
    {
        if (subnodes[i])
        {
            delete subnodes[i];
            subnodes[i] = nullptr; // not nesessary with vector but =)
        }
    }
}

чем вы не должны использовать delTree, просто 

delete node->subnodes[ind];
node->subnodes[ind] = nullptr;
...