預先遍歷深度優先方法嗎？

預先遍歷深度優先算法嗎？我在下面的搜索中使用它。我已經包含下面的代碼。預先遍歷深度優先方法嗎？

public bool DFS1(int value, BSTNode root) 
{ // Pre-order search 

    if (root == null) 
     return false; 

    if (root.data == value) 
    { 
     Console.WriteLine("found"); 
     return true; 
    } 

    DFS1(value, root.left); //vist the left node 
    return DFS1(value, root.right); // vist the right node. 
}

來源

2016-09-14 Kiran B.R

你忽略了左遞歸的結果。如果左側成功，則不需要正確的搜索。 – molbdnilo

@ A.Sarid基本問題是重複的。然而OP在雙遞歸中存在問題以解決（恕我直言）保證打開這個問題。 – Prune

是的，它是深度優先：在查看原始根節點的右邊節點之前，您將完全完成左側子樹。但是，您需要考慮該左側搜索的結果。目前，如果最右邊的節點具有目標值，則這將返回true。

return DFS1(value, root.left) or 
     DFS1(value, root.right)

大多數編譯器將優化這個（短路），因此，如果左側返回真的是，權將不會執行。如果沒有，你可以自己寫：

if (DFS1(value, root.left)) 
    return true; 
else 
    return DFS1(value, root.right);

來源

2016-09-14 18:09:20 Prune

@ Prune-良好的捕獲。我不知道如何在遞歸兩次調用之後返回，因爲在結束代碼中「返回false」返回不正確的值。有沒有使用OR條件返回的另一種方法？ –

當然...請參閱編輯。 – Prune

@ Prune-謝謝。這是我想到的。 –

預先遍歷深度優先方法嗎？

回答

相關問題