二分木

1：$n$ 個の節点はそれぞれ左右 2 つの枝の場所をもち、場所は全部で $2n$ 個ある。根以外の節点はちょうど 1 つの場所（親の左か右）を埋めるので、埋まった場所は $n-1$ 個で、空の場所は $2n-(n-1)=n+1$ 個である（$n=0$ なら空の木そのものが 1 個の空の部分木である）。
2：内部節点を $i$ 個とする。全二分木では内部節点はちょうど 2 つの子をもち、根以外の節点はちょうど 1 つの親をもつので、$2i=n-1$ である。$n=\ell+i$ と合わせて $\ell=i+1$、$n=2\ell-1$ である。
3：深さ $k$ の節点の位置は長さ $k$ の 0 と 1 の列で、互いに異なるので $2^k$ 個以下である。$k=0,\dots,h$ について足して $n\le2^{h+1}-1$ である。葉については、深さ $d$ の葉の位置 $w$ に、$w$ を先頭にもつ長さ $h$ の列の集合（$2^{h-d}\ge1$ 個）を対応させる。葉の位置は互いに他の先頭部分にならない（先頭部分は祖先の位置である）ので、これらの集合は互いに交わらず、葉は $2^h$ 個以下である。
$n=2^{h+1}-1$ なら、長さ $h$ 以下のすべての列が位置であり、深さ $h$ 未満の節点はすべて 2 つの子をもち、深さ $h$ の節点は葉なので、高さ $h$ の完全二分木である。逆に高さ $h$ の完全二分木では、葉はすべて深さ $h$ にあるので深さ $h$ 未満の節点はすべて内部節点で、全二分木だから 2 つの子をもつ。深さについての帰納法で、各 $k\le h$ について長さ $k$ のすべての列が位置になり、$n=2^{h+1}-1$ である。最後の主張は $n\le2^{h+1}-1$ を書き直したものである。$\square$

1：節点の個数についての帰納法で示す。節点が 1 個なら、根が深さ $0$ の葉なので $S(T)=1$ であり、$T$ は全二分木である。節点が 2 個以上の $T=(v,L,R)$ では、$v$ は葉でなく、$T$ の葉は $L$ の葉と $R$ の葉で、深さは $L,R$ の中での深さより $1$ 大きい。よって
$$ S(T)=\frac12\bigl(S(L)+S(R)\bigr) $$
である。帰納法の仮定と $S(\epsilon)=0$ により $S(L),S(R)\le1$ なので $S(T)\le1$ である。等号は $S(L)=S(R)=1$ のときに限り、それは $L,R$ がともに空でなく（$S(\epsilon)=0$ だから）全二分木であることと同値で、さらにそれは $T$ が全二分木であることと同値である（$T$ の根が子を 2 個もち、ほかの節点の子の個数は $L$ か $R$ の中で決まる）。
2：番号を付け替えて $d_1\le d_2\le\dots\le d_\ell$ としてよい。$a_i:=2^{d_i}\sum_{j< i}2^{-d_j}$ とおく。$j< i$ なら $d_j\le d_i$ なので $2^{d_i-d_j}$ は整数で、$a_i$ は $0$ 以上の整数である。また $\sum_{j< i}2^{-d_j}\le1-2^{-d_i}$ なので $a_i\le2^{d_i}-1$ である。そこで $a_i$ を $d_i$ 桁の 2 進法で（先頭に $0$ を補って）書いた列を $c_i$ とする（$d_i=0$ なら $\ell=1$ で $c_1$ は空の列）。
$i< j$ のとき $c_i$ は $c_j$ の先頭部分でないことを示す。$c_j$ の先頭の $d_i$ 文字が表す整数は $\lfloor a_j2^{d_i-d_j}\rfloor=\bigl\lfloor2^{d_i}\sum_{k< j}2^{-d_k}\bigr\rfloor$ である。ここで $\sum_{k< j}2^{-d_k}\ge\sum_{k< i}2^{-d_k}+2^{-d_i}$ なので、この整数は $a_i+1$ 以上で、$a_i$ と異なる。とくに $c_1,\dots,c_\ell$ は互いに異なる。
$c_1,\dots,c_\ell$ とそれらの先頭部分の全体を $P$ とすると、$P$ は先頭部分をとる操作で閉じた有限集合なので、ある二分木の位置の全体である。$c_i$ はほかの $c_j$ の先頭部分でないので、その真の延長は $P$ に属さず、$c_i$ は葉の位置である。$c_i$ でない $P$ の元は、ある $c_j$ の真の先頭部分なので子をもち、葉でない。よって葉はちょうど $c_1,\dots,c_\ell$ の位置にあり、深さは $d_1,\dots,d_\ell$ である。$\square$

thm-btr-kraft の 1 と、相加平均と相乗平均 の不等式により
$$ \frac1\ell\ \ge\ \frac1\ell\sum_{i=1}^\ell2^{-d_i}\ \ge\ \Bigl(\prod_{i=1}^\ell2^{-d_i}\Bigr)^{1/\ell}=2^{-\frac1\ell\sum_id_i} $$
であり、両辺の $\log_2$ をとって $-\log_2\ell\ge-\frac1\ell\sum_id_i$ を得る。平均は最大値以下なので、後半も従う。$\square$

相異なる 2 つの順は正しい答えが異なるので、正しい手順では異なる葉に着く。よって着く葉は $n!$ 個あり、それぞれの順で使う比較の回数はその葉の深さである。それら $n!$ 個の葉の深さを $e_1,\dots,e_{n!}$ とする。thm-btr-kraft の 1 により、比較の木のすべての葉について $2^{-(\text{深さ})}$ を足しても $1$ 以下なので、$\sum_k2^{-e_k}\le1$ である。cor-btr-average-depth の証明と同じ計算により、$e_k$ の平均と最大値はどちらも $\log_2n!$ 以上である。$\square$

節点の個数 $n$ についての帰納法で示す。列の長さは節点の個数なので、$T,T'$ の節点の個数は等しい。$n=0$ ならどちらも空の木である。$n\ge1$ とし、$T=(v,L,R)$、$T'=(v',L',R')$ とする。前順の最初の名前は根の名前なので、$v$ と $v'$ の名前は等しい。それを $x$ とする。名前は互いに異なるので、$x$ は中順の列にちょうど 1 回現れ、その位置を $k+1$ 番目とする。$\mathrm{in}(T)=\mathrm{in}(L),x,\mathrm{in}(R)$ で $x$ は $\mathrm{in}(L)$ に現れないので、$L$ の節点は $k$ 個で、$\mathrm{in}(L)$ は中順の最初の $k$ 個、$\mathrm{in}(R)$ は $k+2$ 番目以降である。同じことが $T'$ についても成り立つので $\mathrm{in}(L)=\mathrm{in}(L')$、$\mathrm{in}(R)=\mathrm{in}(R')$ である。前順では、$\mathrm{pre}(L)$ は 2 番目から $k+1$ 番目、$\mathrm{pre}(R)$ はそれ以降なので、$\mathrm{pre}(L)=\mathrm{pre}(L')$、$\mathrm{pre}(R)=\mathrm{pre}(R')$ である。$L,L'$ と $R,R'$ の節点はそれぞれ $n$ 個未満で名前は互いに異なるので、帰納法の仮定により $L$ と $L'$、$R$ と $R'$ は同じである。よって $T$ と $T'$ は同じである。$\square$

節点の個数 $n$ についての帰納法で示す。$n=1$ なら根だけの木で、名前も前順で決まる。$n\ge2$ なら $T=(v,L,R)$ の根は葉でなく、全二分木なので $L,R$ はともに空でない全二分木である（$T'=(v',L',R')$ も同じ）。根の名前は前順の最初で決まる。前順の 2 番目の名前 $y$ は $L$ の根の名前である。後順は $\mathrm{post}(L),\mathrm{post}(R),x$ の形で、$L$ の根の名前 $y$ は $\mathrm{post}(L)$ の最後にある。名前は互いに異なるので、$y$ が後順の $k$ 番目にあれば $L$ の節点は $k$ 個である。これは $T'$ でも同じなので、前順と後順をそれぞれ左部分木の分と右部分木の分に切り分けられ、$\mathrm{pre}(L)=\mathrm{pre}(L')$、$\mathrm{post}(L)=\mathrm{post}(L')$、$R,R'$ についても同様である。帰納法の仮定により $L=L'$、$R=R'$ であり、$T=T'$ である。$\square$