数を読みました <p>ツリーの高さは2ですが、リーフノードの数は、少なくとも2であり、少なくとも3ではありません。私は間違っていますか？</p>

Question

でIは、高さhのツリー内のリーフノードの数が、少なくともH + 1

しかし、PIC

にここに示されているようであることをリーフノードの

Answer 1

高さhのツリー内の葉の数が少なくともh + 1であるという文は、明らかに偽です。葉ノードが1つしかない長さhのリンクリストを考慮してください。読んだソースが間違っているか、ツリーの構造に関するいくつかの余分な仮定がありました。

EDIT：元の証明では、少なくともh + 1個のNULLポインタがツリーに存在する可能性があります。この声明は、我々が誘導によって見ることができるように、確かに真実です。基底の場合、単一のノードツリーは高さが0で2つのNULLポインタを持ち、したがって、h = 0の保持を保持します。帰納的ステップでは、高さh '< hのすべてのツリーに対して、高さh。そのサブツリーの1つは高さがh-1でなければならず、帰納的仮説ではh NULLポインタが必要です。今度は他のサブツリーを考えてみましょう。他のサブツリーがない場合、ルートは（h + 1）番目のNULLポインタに寄与し、終了します。そうでなければ、k ≥の高さkのサブツリーが存在するので、帰納仮説によって少なくとも1つのNULLポインタがあり（k + 1）≥なので、ツリー自体には少なくともh + 1個のNULLポインタがあり、 。

Answer 2

、あなたは完璧なバイナリツリーの話をしている場合だけ、あなたが作った文が真である：

完璧なバイナリツリーは、すべての葉が 同じ深さである、完全なバイナリ ツリーですまたは同じレベル

Answer 3

私はこれが古いですけど、場合には他の誰が葉を見つけるために、ここに出くわす： （N - 1） - （N/2） ここで、n =ノードの総数。この場合は、（4 - 1） - （4/2）= 3 - 2 = 1