递归树上的段错误 Traversal/Branch 删除

Question

我正在尝试清理树的分支，每个节点存储一个 occurrence 构造过程中每次访问该节点的值，"cleaning"在这个意义上是指在两个后续节点都只有一个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() 都检查它不为空删除前。

我觉得我遗漏了一些明显的东西，我们将不胜感激。

编辑

回应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 是 Node* 的 vector。

回应 Erik Alapää：

我现在不在，但我会把它换过来试一试。

Answer 1

提供的代码似乎是正确的。您创建树的方式可能有问题吗？

假设 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]);

否则，如果您不小心在同一棵树上两次调用 cleanBranch，您将获得 GPF。

顺便说一句，考虑使用 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;

递归树上的段错误 Traversal/Branch 删除

Segfault on Recursive Tree Traversal/Branch Deletion

c++

tree

recursion

segmentation-fault

delete-operator