1 に答える
1
最初に、同じ数の葉ノードを持つすべての木が同じ数の内部ノードを持つことを示します。Iこれは、内部ノードを持つツリーを持つリーフ ノードの数を確認することで示されます。I内部ノードには、エッジ2*Iがあります。I-1これらのエッジのうち、内部ノードを接続するため、I+1エッジはリーフ ノード用に残されます。したがって、n葉ノードを持つツリーにはn-1内部ノードがあります。
1 つのツリーを別のツリーに変換できることを確認するには、両方のツリーを何らかの「ベース」ツリーに変換するだけで十分です。たとえばA、すべての内部ノード (最後を除く) が左側の葉と右側の内部ノードにあるツリーとします。それはパスのようなものです :-) 任意のツリーをA正しい回転のみに変換するには、必要な順序ノードを簡単に見つけて回転を行うことができます。に変換T1するT2には、 に変換するだけで十分であり、回転のリストを逆にして に変換T1するよりも十分です。AAT2
于 2015-09-19T17:10:49.193 に答える