有限的空间迭代器

Question

我已经实现了一棵树（不是二进制树，每个节点都有几个子节点）。对于每个节点，我们都可以在树，孩子和父节点中访问其水平。

下一阶段是为这棵树实现2个迭代器，但捕获是我不能节省超过恒定数量的信息来帮助完成这些迭代器（即恒定的空间复杂性）。

我的问题是我目前处于的一个节点n：

1. 在BFS顺序中找到下一个遍历的节点是什么算法？
2. 在 *反向BFS顺序中找到下一个遍历的节点是什么算法？

*注意：

反向BFS正在以相反顺序横穿水平，例如以下树的反向BF

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

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

Answer 1

这是算法的草图。效率低下，但满足您仅使用O（1）额外空间的要求。

1. node* goright（node* c）
   如果c是root（没有父母），请返回null
   令p为c的父母。立即在c的右边找到其子女r（可能需要对p的子女链接进行线性搜索）。如果找到，返回r
   如果找不到（c是最正确的孩子），set c = p，从一开始就重复。

因此，发现的节点可能比我们开始的节点更高。

2. 节点* godowntolevel（node* p，int k）
   如果p是null，返回null
   如果p在级别k，返回p。
   从p开始，请按照左侧的儿童链接向下链接，直到达到级别k或无需链接。令c为因此找到的节点。如果c在级别k，返回c。
   否则，c是k上方的级别节点。 SET P = Goright（C），从开始时重复。

3. node* nextAtlevel（node* c，int k）
   返回godowntolevel（goright（c），k）

4. node* nextinbfsorder（node* c）

   令k为c的级别。令r = nextAtlevel（c，k）。如果r不是null，返回r。
   否则，将父链一直穿过根，返回godowntolevel（root，k+1）。另外，root可以存储在迭代器中。另外，迭代器可以跟踪它在遍历级别k时遇到的第一个非叶节点的最左边的孩子，然后跳到该孩子，一旦NextAtlevel失败；这个孩子在级别开始迭代k+1。

   


---

反向BF会类似地工作。困难的部分是找到启动遍历的节点。基本上，执行godowntolevel（root，infinity），同时跟踪遇到的最深层次，并在该级别遇到的第一个节点。当然，do godowntolevel（root，k-1）而不是godownTolevel（root，k+1） nextAtlevel失败。

如果您在建造树时跟踪h，则可以使用godowntolevel（root，h）启动遍历

Answer 2

我假设您可以弄清楚如何进行树的预订遍历：先扎根，然后再去第一个孩子，直到您没有孩子碰到节点。然后去找父母，然后在您来自一个孩子之后找到下一个孩子。如果这是最后一个孩子与新父母重复。

一次这样做以找出树的最深节点，或者使树存储的最大深度。然后，再做一个深度的第一个孩子。您的迭代器是那个深度和孩子的地址。

要增加迭代器，请继续对孩子进行预订遍历，然后跳过所有节点，其中node-＆gt; depth！= depth。每次遍历饰面都会减小深度。当深度变为负返回end（）时。

注意：在预订遍历中，您可以在node-＆gt; depth == depth 时跳到孩子身上，直接回到父母身上。