c++ - 如何在 C++ 中提取树迭代

Question

我已经多次重复一大块类似的代码。这是伪代码中的样子:

stack.push(root)
while stack size > 0
  node = stack.pop()
  if condition_1
    if node is leaf
      if condition_2
        // do something,
        // for example, push node into a vector and return the vector
    else
      stack.push(children of node)

或者像这样:

stack.push(root)
while stack size > 0
  node = stack.pop()
  if condition_1
    if node is leaf
      if condition_2 // or no condition_2 and return true directly
        return true
    else
      stack.push(children of node)
return false

这两个代码片段的区别在于第一个代码片段遍历所有叶节点，而第二个代码片段具有中断逻辑。通常我做的主要工作是 condition_2 及其范围内的内容。其他行只是在重复自己。

那么有没有办法在 C++ 或任何其他语言中提取这种树迭代循环？

Answer 1

正如我正确理解的那样，您想拥有该算法的通用版本。

我不知道您想要通用化哪些部分，所以这是一个非常简单的解决方案，其中所有内容都是通用的。

template <class NodeType, class TraversalPredicate, class LeafPredicate,
          class TerminalPredicate, class ChildrenGetter>
bool findIf(NodeType *root, TraversalPredicate shouldTraverse,
            LeafPredicate isLeaf, TerminalPredicate shouldFinish,
            ChildrenGetter getChildren) {
  std::stack<NodeType *> stack;
  stack.push(root);

  while (not stack.empty()) {
    auto *node = stack.top();
    stack.pop();
    if (not shouldTraverse(node))
      continue;

    if (isLeaf(node)) {
      if (shouldFinish(node)) {
        return true;
      }
    } else {
      for (auto *child : getChildren(node)) {
        stack.push(child);
      }
    }
  }
  return false;
}

我希望这就是您要找的!