为了账号安全,请及时绑定邮箱和手机立即绑定

非递归深度优先搜索算法

非递归深度优先搜索算法

精慕HU 2019-11-21 14:15:03
我正在寻找一种针对非二叉树的非递归深度优先搜索算法。很感谢任何形式的帮助。
查看完整描述

3 回答

?
HUH函数

TA贡献1836条经验 获得超4个赞

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()删除并返回列表中的第一个元素。


查看完整回答
反对 回复 2019-11-21
?
繁华开满天机

TA贡献1816条经验 获得超4个赞

您将使用一个堆栈来保存尚未访问的节点:


stack.push(root)

while !stack.isEmpty() do

    node = stack.pop()

    for each node.childNodes do

        stack.push(stack)

    endfor

    // …

endwhile


查看完整回答
反对 回复 2019-11-21
?
皈依舞

TA贡献1851条经验 获得超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

分享编辑


查看完整回答
反对 回复 2019-11-21
  • 3 回答
  • 0 关注
  • 734 浏览

添加回答

举报

0/150
提交
取消
意见反馈 帮助中心 APP下载
官方微信