一尘不染

非递归深度优先搜索算法

algorithm

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


阅读 331

收藏
2020-07-28

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

2020-07-28