algorithm - 前序遍历是深度优先的方法吗？

Question

前序遍历是深度优先算法吗？我在下面的搜索中使用它。我在下面包含了代码。

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.
}

Answer 1

是的，它是深度优先的:在查看原始根的右节点之前，您将完全完成左子树。但是，您需要考虑左侧搜索的结果。目前，这将返回 true 当且仅当最右边的节点具有目标值。

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

大多数编译器会对此进行优化(短路)，因此如果左侧返回true，右侧将不会执行。如果没有，你可以自己写:

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