4

次のテキストは、アルゴリズムブックの抜粋です。

リンクリストで一般的な長方形のボックスを使用して二分木を描画することもできますが、実際にはグラフであるため、ツリーは通常、線で結ばれた円として描画されます。また、ツリーを参照するときにNULLリンクを明示的に描画しません。これは、Nノードを持つすべてのバイナリツリーがN +1NULLリンクを必要とするためです。

私の質問は、N個のノードを持つすべての二分木がN +1個のヌルリンクを必要とすることを著者が何を意味するのかということです。著者はどのようにしてN+1番号を付けましたか？

4

3 に答える 3

7

1ノードのツリーがある場合、2つのヌルリンクがあります（ルートの左右）。左または右にノードを追加すると、1つのnullが入力され、さらに2つ追加されます。これは無限に続くため、追加されたノードごとに1つの余分なヌルリーフが追加されます。

于 2011-08-29T13:21:53.580 に答える
4

これは数学的帰納法で証明できます。

規範事例

1つのノードに2つのNULLリンクがあります-プロパティを満たします。

帰納的ステップ

ここで、n-1ノードのすべてのツリーにn個のNULLリンクがあると仮定します。次に、n個のノードを持つすべてのツリーにn +1個のNULLリンクがあることを示したいと思います。

n個のノードを持つ任意のツリーを取得し、葉の1つを選択します。この葉を取り除きます。これで、仮定に従って、n個のNULLリンクを持つツリーができました。リーフを再度追加すると、1つのNULLリンクが失われますが、2つ増加します。したがって、n個のノードを持つツリーにn --1 + 2 = n +1NULLリンクがあります。

于 2011-08-29T13:23:54.650 に答える
1

観察：各エッジはリンクとして機能します。NノードのN-1エッジ。

完全にリンク：2N。

ヌルリンク：2N-（N-1）= N+1。

于 2013-07-23T17:20:10.337 に答える