Non-recursive breadth-first traversal without a qu

问题:

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.

回答1:

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

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.

Pseudo code for your tree:

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)