无队列的非递归广度优先遍历 [英] Non-recursive breadth-first traversal without a queue

问题描述

在由节点表示的通用树中，该节点具有指向父代，兄弟姐妹和第一个/最后一个孩子的指针，如:

In a generic tree represented by nodes having pointers to parent, siblings, and firs/last children, as in:

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

是否可以进行迭代(非递归)广度优先(级别顺序)遍历而无需使用任何其他辅助结构(例如队列).

Is it possible to do an iterative (non-recursive) breadth-first (level-order) traversal without using any additional helper structures such as a queue.

所以基本上:我们可以使用单节点引用进行回溯，但不能保存节点集合.从理论上讲，是否可以完全做到这一点，但更实际的问题是，是否可以高效地完成这一过程而无需在大片段上进行回溯.

So basically: we can use single node references for backtracking, but not hold collections of nodes. Whether it can be done at all is the theoretical part, but the more practical issue is whether it can be done efficiently without backtracking on large segments.

推荐答案

是的，可以.但这很可能是一个折衷方案，并且会花费您更多的时间.

Yes, you can. But it will most likely be a tradeoff and cost you more time.

通常来说，一种方法是了解一种方法，可以在没有树的额外内存的情况下实现遍历.使用它，您可以执行迭代加深DFS ，该发现以相同顺序发现新节点BFS会发现它们的.

Generally speaking, one approach to do it is to understand one can implement a traversal without extra memory in a tree. Using that, you can do Iterative Deepening DFS, which discovers new node in the same order BFS would have discovered them.

这需要进行一些记账，并记住您刚来自哪里"，并据此决定下一步要做的事情.

This requires some book-keeping, and remembering "where you just came from", and deciding what to do next based on that.

树的伪代码:

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

然后，您可以使用以下命令进行关卡遍历:

And then, you can have your level order traversal with:

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

这篇关于无队列的非递归广度优先遍历的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！