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

本文介绍了无队列的非递归广度优先遍历的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

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

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)