在DFS遍历期间调用每个节点上的自定义函数

Question

我想知道什么是编写DFS遍历的最优雅的方式，它可以适应于解决不同的问题（在C中）。

我想把一个函数指针和一个void*传递给我的函数，让用户传递一个回调函数，这个回调函数将在每个节点上使用。

这就是我所拥有的：

typedef std::shared_ptr<struct Node> NodePtr;
typedef std::vector<NodePtr> NodeVector;

struct Node {
    int id{0};
    NodeVector children;
};

bool NodeIsInVector(NodePtr node, NodeVector node_vector);

void DFS(NodePtr node, void (*callback)(NodePtr, void * userdata)=nullptr, void * userdata=nullptr);

bool NodeIsInVector(NodePtr node, NodeVector node_vector){
    auto result = std::find(node_vector.begin(), node_vector.end(), node);
    return result != node_vector.end();
}

void DFS(NodePtr node, void (*callback)(NodePtr, void * userdata), void * userdata){
    static NodeVector visited;

    if (!NodeIsInVector(node, visited)) {
        visited.push_back(node);
        if (callback){
            callback(node, userdata);
        }
    }

    for (auto&& n : node->children){
        if (!NodeIsInVector(n, visited)){
            DFS(n, callback, userdata);
        }
    }
}

在这里，回调只计算节点、增量和整数。假设root是一个节点指针，并且定义了一个树。树有7个节点，因此在遍历之后，count的值应该是7。

int count = 0;
DFS(root, [](NodePtr node, void * count){ ++*(int*)count; }, (void*) &count);
std::cout << "DFS count: there are " << count << " nodes.\n";

但是输出是：DFS计数：有0个节点。调用回调（通过输出到stdout进行验证）。问题是userdata变量不会更新。

我的问题是：

• 这是实现我想要的有效方法吗？有更好的方法吗？
• 我犯的错误是什么？

Answer 1

如果我错了，请纠正我的错误，但我怀疑问题是由于DFS中定义的static变量造成的。

在我的问题中，我没有提到DFS是使用不同的回调调用的，在使用回调调用之前，回调不会增加计数变量。我认为这与我的问题无关。

在函数中声明静态变量是否会导致在第二次调用期间不替换回调函数？

以下版本按预期工作。我还用一个反映注释中提出的一些建议的std::function替换了函数指针，但更重要的是，我创建了一个包装器，声明访问了NodeVector，这让我没有任何静态 声明。

void DFS(NodePtr &node, std::function<void(NodePtr)> callback){
    NodeVector visited;
    _DFS(node, callback, visited);
}

void _DFS(NodePtr &node, std::function<void(NodePtr)> callback, NodeVector& visited){
    if (!NodeIsInVector(node, visited)) {
        visited.push_back(node);
        callback(node);
    } else {
        for(auto item : visited){
            std::cout<<item->id << " ";
        }
        std::cout << "\n";
    }
    for (auto&& n : node->children){
        if (!NodeIsInVector(n, visited)){
            _DFS(n, callback, visited);
        }
    }
}

和驱动程序代码：

int count = 0;
DFS(root, [&count](NodePtr node) mutable { ++count; });
std::cout << "DFS count: there are " << count << " nodes.\n";

生产：

DFS计数：共有7个节点

注意，相同的函数，但访问了一个静态NodeVector 而不是包装器策略无法按预期工作。我仍然不是100%清楚为什么。

Answer 2

我认为代码的问题在于，如果在调用回调之前节点没有子节点，则返回。这将导致只有父节点调用回调。

我会完全取消孩子们的空头支票。如果节点没有子节点，则不会执行for循环。

void DFS(NodePtr node, void (*callback)(NodePtr, void * userdata), void * userdata){
    static NodeVector visited;

    if (!NodeIsInVector(node, visited)) {
        visited.push_back(node);
        if (callback){
            callback(node, userdata);
        }
    }

    for (auto&& n : node->children){
        if (!NodeIsInVector(n, visited)){
            DFS(n, callback, userdata);
        }
    }
}