有限 space 个迭代器

Question

我实现了一棵树（不是二叉树，每个节点可以有多个子节点）。对于每个节点，我们可以访问它在树中的级别、它的子节点和它的父节点。

下一阶段是为这棵树实现 2 个迭代器，但要注意的是我不能保存超过恒定数量的信息来帮助完成这些迭代器（即恒定 space 复杂度）。

我的问题是，给定我当前所在的节点 n：

以 BFS 顺序找到要遍历的下一个节点的算法是什么？
以*反向 BFS 顺序查找要遍历的下一个节点的算法是什么？

*注：

反向 BFS 以相反的顺序遍历级别，例如以下树的反向 BFS

      1 
    / | \
   2  3  4
  /  / \  \
 5  6   7  8

将是 5 6 7 8 然后是 2 3 4 然后是 1。

Answer 1

这是算法的草图。非常低效，但满足你只使用 O(1) 额外 space.

的要求

Node* GoRight(Node* c)
如果 c 是根（没有 parent），return NULL
设 p 为 c 的 parent。立即在 c 的右侧找到它的 child r（可能需要对 p 的 child 链接进行线性搜索）。如果找到，return r
如果没有找到（c就是right-mostchild），设置c=p，从头开始重复

由此找到的节点可能比我们开始的节点处于更高级别。

Node* GoDownToLevel(Node* p, int k)
如果p是NULL，returnNULL
如果 p 处于级别 k，return p。
从 p 开始，沿着 left-most child 链接向下，直到达到级别 k 或没有可跟随的链接。设 c 为由此找到的节点。如果 c 处于级别 k，return c。
否则，c是k上一层的叶节点。设置p = GoRight(c)，从头开始重复
Node* NextAtLevel(Node* c, int k)
ReturnGoDownToLevel(GoRight(c), k)
Node* NextInBFSOrder(Node* c)
设 k 为 c 的水平。让r = NextAtLevel(c, k)。如果 r 不是 NULL, return r.
否则，遍历 parent 链一直到根 return GoDownToLevel(root, k+1)。或者，root 可以存储在迭代器中。或者，迭代器可以跟踪它在遍历级别 k 时遇到的第一个 non-leaf 节点的最左边 child，并跳转到 child 一次 NextAtLevel失败；此 child 在级别 k+1 开始迭代。

反向 BFS 的工作方式类似。困难的部分是找到开始遍历的节点。基本上，执行 GoDownToLevel(root, infinity) 同时跟踪遇到的最深层次和在该层次遇到的第一个节点。当然，当 NextAtLevel 失败时，执行 GoDownToLevel(root, k-1) 而不是 GoDownToLevel(root, k+1)。

如果您在构建树时跟踪树的高度 h，那么您可以使用 GoDownToLevel(root, h)

开始遍历

Answer 2

我假设你能弄清楚如何对树进行 pre-order 遍历：先取根，然后转到第一个 child 直到找到没有 [=24] 的节点=]仁。然后去 parent 找到你来自的那个之后的下一个 child。如果它是最后一个 child 用新的 parent 重复。

这样做一次以找出树的最深节点，或者让树存储其最大深度。然后再次停止在该深度的第一个 child。您的迭代器是 child.

的深度和地址

要增加迭代器，请继续在 child 上进行 pre-order 遍历，并跳过 node->depth != depth 所在的所有节点。每次遍历完成递减深度。当深度变为负数时 return end().

注意：在pre-order遍历中你可以跳过children，当node->depth == depth时，直接回到parent。

有限 space 个迭代器

Limited space iterators

c++

algorithm

tree

iterator

space-complexity