n 個のノードと L 個のリーフ ノードを持つバランス バイナリ ツリーを作成する方法の数を知りたいです。
また、 n は ( 2*L - 1 ) でなければならないことも知っています。
質問する
2526 次
1 に答える
1
平衡二分木は、任意のノードが与えられた場合、そのノードの2つのサブツリーの高さが最大で1つ異なるようなツリーです。したがって、ノードの数は必ずしも2 ^L-1ではありません。ツリーに2^L-1ノードがある場合、それは定義上、完全な二分木です。だからあなたの質問に答えるために..順序が重要な場合..トップノードを選択する方法（またはn個の方法）があります（n個の方法を選択してください）。次に、順序が重要であるため、そのノードの子を選択するための選択肢が（n-1選択2）あります。などなど。したがって、（nは1を選択）*（n-1は2を選択）*（n-3は2を選択）* .... n=1または0になるまでです。
順序が重要でない場合..トップノードは同じです。トップノードにはまだ（1つを選択して）選択肢があります。そのノードの子の1つには、n-1の選択肢があり、それを選択した後、もう1つの子にはn-2の選択肢があります。次に、選択肢がなくなるまで続行します。したがって、この場合、n *（n-1）*（n-2）... = n！方法
----編集---実際に私は間違いを犯しました。合計ノード数は必ずしも2^L-1ではありません。n個のノードがある場合、ツリーの高さはfloor（lg（n））です。リーフノードの数は、ツリー内のノードの総数とは相関関係がありません。
于 2012-11-22T00:37:43.980 に答える