时间戳

首页 > 解决方案 > 如何在 C++ 中提取树迭代

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

问题描述

我已经重复了好几次类似的代码。这在伪代码中是这样的：

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++ 或任何其他语言中提取这种树迭代循环？

标签： c++tree

解决方案

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

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

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;
}

我希望这就是你要找的！

推荐阅读