深度優先搜索代碼片段

Question

我有廣度優先搜索驗證碼：

var queue = new Queue<BinaryNode>(); 
queue.Enqueue(rootNode); 

while(queue.Any()) 
{ 
    var currentNode = queue.Dequeue(); 
    if(currentNode.data == searchedData) 
    { 
    break; 
    } 

    if(currentNode.Left != null) 
    queue.Enqueue(currentNode.Left); 

    if(currentNode.Right != null) 
    queue.Enqueue(currentNode.Right); 
} 

現在我試圖爲深度優先搜索做同樣的，我知道，DFS使用堆棧上而不是排隊，所以我可以得到在編寫DFS方面有一些幫助。

Answer 1

簡單的答案是..只需將隊列更改爲堆棧！ （假設它是一個二叉樹）

如果你想從左至右遍歷的權利，你應該反轉推的順序（像我一樣）：

stack.push(rootNode); 

while(stack.Any()) { 
    var currentNode = stack.pop(); 
    if(currentNode.data == searchedData) 
    break; 

    if(currentNode.Right != null) 
    stack.push(currentNode.Right); 

    if(currentNode.Left != null) 
    stack.push(currentNode.Left); 

} 

所以..這將遍歷樹：

順序

：

A - >乙 - > d - >電子 - 「ç - >的F - 」G

操作的順序將是：

1. 推送的（a）
2. 彈出; a
3. push（c）
4. push（b）
5. pop; b
6. 推送（e）中
7. 推（d）
8. 彈出; d
9. pop; e
10. pop; Ç
11. 推（克）
12. 推（F）
13. 彈出˚F
14. 彈出克

另一種方式

有使用遞歸以類似的方式（它會像使用隱式堆棧）

def dfsSearch(node, searchedData): 
    # Base case 1: end of the tree 
    if node == None: return None 

    # Base case 2: data found 
    if node.data == searchedData: return node 

    # Recursive step1: Traverse left child 
    left = dfsSearch(node.left, searchedData) 
    if left != None: return left 

    # Recursive step2: Traverse right child 
    right = dfsSearch(node.right, searchedData) 
    if right != None: return right 

    return None