预先遍历深度优先方法吗？

预先遍历深度优先算法吗？我在下面的搜索中使用它。我已经包含下面的代码。预先遍历深度优先方法吗？

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-谢谢。这是我想到的。 –

预先遍历深度优先方法吗？

回答

相关问题