无队列非递归广度优先遍历

Question

在通用树中，由具有指向父级、兄弟级和第一个/最后一个子级的指针的节点表示，如下所示：

class Tnode {

    def data
    Tnode parent = null
    Tnode first_child = null, last_child = null 
    Tnode prev_sibling = null, next_sibling = null 

    Tnode(data=null) {
        this.data = data
    }
}

是否可以在不使用任何其他辅助结构（例如队列）的情况下进行迭代（非递归）广度优先（级别顺序）遍历。

所以基本上：我们可以使用单个节点引用进行回溯，但不能保存节点集合。到底能不能做到是理论上的部分，但更实际的问题是能否在大段不回溯的情况下高效地做到。

Answer 1

是的，可以。但这很可能是一种权衡，会花费您更多时间。

一般来说，实现此目的的一种方法是理解可以“在树中实现无需额外内存的遍历”。使用它，您可以执行迭代深化 DFS，它以 BFS 发现它们的相同顺序发现新节点。 这需要一些记账，记住“你刚刚从哪里来”，并据此决定下一步该做什么。

你的树的伪代码：

special_DFS(root, max_depth):
  if (max_depth == 0):
    yield root
    return
  current = root.first_child
  prev = root
  depth = 1
  while (current != null):
    if (depth == max_depth):
      yield current and his siblings
      prev = current
      current = current.paret
      depth = depth - 1
  else if ((prev == current.parent || prev == current.previous_sibling)
           && current.first_child != null):
    prev = current
    current = current.first_child
    depth = depth + 1
  // at this point, we know prev is a child of current
  else if (current.next_sibling != null):
    prev = current
    current = current.next_sibling
  // exhausted the parent's children
  else:
    prev = current
    current = current.parent
    depth = depth - 1
 

然后，您可以使用以下命令进行级别顺序遍历：

for (int i = 0; i < max_depth; i++):
   special_DFS(root, i)