予約注文トラバーサルは深さ優先の方法ですか？

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

はい、深さ優先です。元のルートの右ノードを見る前に、完全に左のサブツリーを完成させます。しかし、その左の検索の結果を考慮する必要があります。現時点では、右端のノードに目標値がある場合、真が返されます。左側は真を返した場合、権利を実行しないように

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

ほとんどのコンパイラは、この（短絡）を最適化します。そうでない場合は、自分で書くことができます。

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