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

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

是否可能在不使用任何额外的辅助结构（如队列）的情况下进行迭代（非递归）广度优先（层次遍历）遍历。

基本上：我们可以使用单个节点引用进行回溯，但不能保留节点集合。能否完成是理论问题，但更实际的问题是在大段上是否可以高效地完成而不需要回溯。

- Basel Shishani

---

对于BFS，你无论如何都需要一个队列。你可以自己发明一些东西，它就是一个队列。 - SashaMN

@TimothyShields 你为什么这么有信心？假设一个人拥有父级链接（他确实有），那就完全有可能。 - amit

@amit 好的。如果要在O（|E| + |V|）时间内执行BFS，则无法在没有队列的情况下完成。 - SashaMN

(1) 这个问题并没有要求O（|E|+|V|）的时间复杂度。 (2) 因为这是一棵树，所以|E|=|V|-1，因此O（|E|+|V|）= O（|V|）。（仅供参考） - amit

在我看来，实现“不使用额外内存的迭代遍历树”通常需要比“使用额外内存的递归遍历树”更多的内存 :). 如果你使用“递归”，通常只需要一个大小等于树深度的堆栈数据结构（无需使用C调用堆栈），但是要进行相同的“迭代”，通常需要为树的每个节点分配额外的内存（可能比递归多指数级的内存）。例如，递归搜索不需要保留对父节点的指针。 - Alexey

Answer 1

是的，你可以。但这很可能会有所牺牲，并且需要更多时间。

一般来说，实现它的方法之一是理解在树中可以不使用额外内存实现遍历。利用这个方法，你可以做迭代加深深度优先搜索（Iterative Deepening DFS），它以与广度优先搜索相同的顺序发现新节点。

这需要一些记账，以及记住“你刚才来自哪里”，并基于此决定下一步要做什么。

你树的伪代码：

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++):
   spcial_DFS(root, i)

- amit

---

你对权衡的解释很清晰 - 谢谢你花时间写代码。 - Basel Shishani