バイナリツリー

Question

アルゴリズムのジェネリックトラバーサルの時間計算：

Tour (node t) 
if t is a leaf node 
    visit t 
else 
    visit t 
    Tour(t.left) 
    visit t 
    Tour(t.right) 
    visit t 

はO（n）は上記のコードの複雑ですか？ ;ここで、nはノードの数です。

Answer 1

はい、各ノードは一定のアクセス時間で1回訪問されます。私はあなたが他の句でちょうど1 visitを意味することを仮定している、いない3。これは私に多くの意味があります：

Tour (node t) 
    visit t 
    if t is a leaf node 
     return 
    Tour(t.left) 
    Tour(t.right) 

Answer 2

質問：あなたの訪問tの操作は何ですか？

訪問の操作が一定時間操作で、入力サイズnに依存しない場合、このアルゴリズムの全体的な時間の複雑さはO（n）です。