非递归深度优先搜索算法

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

分享编辑