我正在尋找一種針對非二叉樹的非遞歸深度優先搜索算法。很感謝任何形式的幫助。
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()刪除并返回列表中的第一個元素。
繁華開滿天機
TA貢獻1816條經驗 獲得超4個贊
您將使用一個堆棧來保存尚未訪問的節點：
stack.push(root)
while !stack.isEmpty() do
node = stack.pop()
for each node.childNodes do
stack.push(stack)
endfor
// …
endwhile
皈依舞
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
分享編輯
添加回答
舉報
0/150
提交
取消