21

ツリートラバーサルの時間計算量はどれくらいですか、それは明らかであるに違いないと確信していますが、私の貧しい脳は今それを解決することができません。

4

2 に答える 2

25

実行しているトラバーサルの種類とアルゴリズムによって異なりますが、通常はO（n）になります。ここで、nはツリー内のノードの総数です。深さ優先走査の標準的な再帰的実装は、最も深いレベルの順序で（スタック上の）メモリを消費します。バランスの取れたツリーでは、log（n）になります。

于 2011-02-10T11:20:33.450 に答える
2

n個のノードを持つツリーの場合はnだけではないでしょうか。

あなたはそれぞれの木を訪れます-一度離れてくださいね？だから私はそれが線形だと思います。

于 2011-02-10T11:18:28.210 に答える