募集：イン注文バイナリツリーの出力方法

Question

の再発式を、私はこのJavaメソッド

void printInorder(Node<T> v) { 
    if(v != null) { 
     printInorder(v.getLeft()); 
     System.out.println(v.getData()); 
     printInorder(v.getRight()); 
    } 
} 

いくつかの基準の漸化式を探しジャムのビットにいるよ：

• その完全なバイナリツリー（すべての内側の結び目は、2人の子供を持っている、すべての葉が同じ深さを持っている）
• ツリーにn個のノットとOの複雑さ（N）

木のdepth hに関連する漸化式はn knotsであり、追加ボーナスとして、O（n）に至る明示的公式を外挿する必要があります。

は今、これは私が得たものである：

d = depth of the tree 
c = constant runtime for execution of the method itself 
d = 1: T(n) = c 
d = 3: T(n) = T(d=1) + T(d=2) + T(d=3) + c 

、私は自分のために物事を明確にする例D = 3を使用し、私はこれをさらに分解する困難を抱えています。私の前提は正しい？

---

編集：ツリーの深さのすべてのレベルが正確に2 ^（H-1）ノードが含まれているので、物事

[x] = { x in real numbers : max([x]) <= x }, [x] rounded down to next full number 
d = 1: T(d) = 1 
d > 1: T(d) = 2^(h-1) * T(n/(2^(h-1))) 

1: T(h) = T(i = 0) + T(i = 1) + ... T(i = h-1) 
2: T(h) <= (2^(0-1) + n/(2^(0-1))) + (2^(1-1) + n/(2^(1-1))) + ... + (2^(h-2) + n/(2^(h-2))) 
3: T(h) = n + n + ... + n 
4: T(h) = (h-1)n 
5: T(h) = O(n) 

で 次に試み、ライン4中のH因子があるため、無視することができますnは最終的な結果とより関連しています。

Answer 1

T（N）= T（N/2）+ T（N/2）+ 1

• レベル0は1つの動作を有しています。

• レベル1には2つの操作があります。

• レベル2には4つの操作があります。

• レベルkには2^k回の演算があります。

• ツリーの深さはlgnです。

1 + 2 + ... + 2^LGN =
2^0 + 2^1 + 2^2 + ... + 2^LGN =
（2 ^（LGN + 1 ）-1）/（2-1）= 2 * 2 lgn =
2nとなる。

Answer 2

ここ平滑ルールを使用して別のアプローチは、（Levitin、デザインアルゴリズムの&解析、第2版。、481から82）このような漸化式ではなく、指数として表現されることを可能にする、です。

どちらのアプローチ - 前方または後方に代入 - この問題に適しています。私は多くの場合、消化しやすいように後方への置換を見つける。