我实现了一个树(不是二叉树，每个节点可以有几个子节点)。对于每个节点，我们都可以访问它在树中的级别，它的子节点和父节点。
下一阶段是为这个树实现2个迭代器，但问题是我不能保存超过一个常量的信息来帮助完成这些迭代器(即恒定的空间复杂度)。
我的问题是，给定一个节点n，我目前在:
- 按照BFS顺序找到下一个要遍历的节点的算法是什么?
- 以*反向BFS顺序找到下一个要遍历的节点的算法是什么? *注意:
反向BFS以相反的顺序遍历级别，例如以下树的反向BFS
1
/ |
2 3 4
/ /
5 6 7 8
是5 6 7 8然后是2 3 4然后是1。
这是算法的草图。非常低效，但满足您只使用O(1)个额外空间的要求。
Node* GoRight(Node* c)
如果c是根(没有父)，返回NULL
让p是c的父。立即在c的右侧找到它的子r(可能需要对p的子链接进行线性搜索)。如果找到，返回r
如果没有找到(c是最右边的子节点)，设置c=p，从头开始重复。
这样找到的节点可能处于比我们开始时的节点更高的级别。
-
Node* GoDownToLevel(Node* p, int k)
如果p是NULL，返回NULL
如果p是k，返回p
从p开始，沿着最左边的子链接往下走，直到到达k级或者没有链接可走。设c为这样找到的节点。如果c在k层，则返回c
否则，c是k上一层的叶节点。设置p = GoRight(c)，从头开始。 -
Node* NextAtLevel(Node* c, int k)
返回GoDownToLevel(GoRight(c), k) -
Node* NextInBFSOrder(Node* c)
设k为c的电平。设r = NextAtLevel(c, k)。如果r不是NULL，则返回r
否则，遍历父链直到根链，返回GoDownToLevel(root, k+1)。或者，也可以将root存储在迭代器中。或者，迭代器可以跟踪它在遍历k关卡时遇到的第一个非叶节点的最左边的子节点，并在NextAtLevel失败时跳转到该子节点;这个子进程在k+1级开始迭代。
反向BFS的工作原理类似。困难的部分是找到开始遍历的节点。基本上，在执行GoDownToLevel(root, infinity)的同时跟踪遇到的最深层和在该层遇到的第一个节点。当然，当NextAtLevel失败时，执行GoDownToLevel(root, k-1)而不是GoDownToLevel(root, k+1)。
如果在构建树的时候跟踪树的高度h，那么你可以从GoDownToLevel(root, h)
我假设您可以弄清楚如何对树进行预顺序遍历:首先取根，然后转到第一个子节点，直到您遇到一个没有子节点的节点。然后去找那个家长，在你出生的那个孩子之后找到下一个孩子。如果它是与新父元素的最后一个子重复。
执行一次以找出树的最深节点，或者让树存储其最大深度。然后再做一次，停在具有该深度的第一个子节点。你的迭代器就是那个深度和子节点的地址。
要增加迭代器，继续对子节点进行预序遍历，并跳过所有node->depth != depth。每次遍历完成时，递减深度。当depth变为负值时，返回end().
注意:在预序遍历中，当node->depth == depth时，您可以跳过到子节点，直接返回到父节点。