在通用树中,由具有指向父节点、兄弟节点和第一个/最后一个子节点的节点表示,如:
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
}
}
是否可以在不使用任何额外的辅助结构(例如队列)的情况下进行迭代(非递归)广度优先(级别顺序)遍历。
所以基本上:我们可以使用单个节点引用进行回溯,但不能保存节点集合。到底能不能做到是理论部分,更实际的问题是能否在大段不回溯的情况下高效完成。
最佳答案
是的,你可以。但这很可能是一种权衡,会花费您更多的时间。
一般来说,一种方法是理解一个可以implement a traversal without extra memory in a tree .使用它,你可以做 Iterative Deepening 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++):
spcial_DFS(root, i)
关于algorithm - 无队列的非递归广度优先遍历,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/34821242/