非递归深度优先搜索算法

Question

我正在寻找一种针对非二叉树的非递归深度优先搜索算法。很感谢任何形式的帮助。

Answer 1

DFS：list nodes_to_visit = {root};while( nodes_to_visit isn't empty ) {  currentnode = nodes_to_visit.take_first();  nodes_to_visit.prepend( currentnode.children );  //do something}BFS：list nodes_to_visit = {root};while( nodes_to_visit isn't empty ) {  currentnode = nodes_to_visit.take_first();  nodes_to_visit.append( currentnode.children );  //do something}两者的对称性很酷。更新：如前所述，take_first()删除并返回列表中的第一个元素。

Answer 2

您将使用一个堆栈来保存尚未访问的节点：stack.push(root)while !stack.isEmpty() do    node = stack.pop()    for each node.childNodes do        stack.push(stack)    endfor    // …endwhile

Answer 3

如果您有指向父节点的指针，则无需额外的内存即可完成操作。def dfs(root):    node = root    while True:        visit(node)        if node.first_child:            node = node.first_child      # walk down        else:            while not node.next_sibling:                if node is root:                    return                node = node.parent       # walk up ...            node = node.next_sibling     # ... and right请注意，如果子节点存储为数组而不是通过同级指针存储，则下一个同级可以找到：def next_sibling(node):    try:        i =    node.parent.child_nodes.index(node)        return node.parent.child_nodes[i+1]    except (IndexError, AttributeError):        return None分享编辑如果您有指向父节点的指针，则无需额外的内存即可完成操作。def dfs(root):    node = root    while True:        visit(node)        if node.first_child:            node = node.first_child      # walk down        else:            while not node.next_sibling:                if node is root:                    return                node = node.parent       # walk up ...            node = node.next_sibling     # ... and right请注意，如果子节点存储为数组而不是通过同级指针存储，则下一个同级可以找到：def next_sibling(node):    try:        i =    node.parent.child_nodes.index(node)        return node.parent.child_nodes[i+1]    except (IndexError, AttributeError):        return None分享编辑