二叉树的几个性质
在计算机科学中，二叉树（Binary tree）是每个结点最多只有两个子结点（即不存在分支度大于 2 的结点）的树结构。这两个子结点通常被称作“左子结点”和“右子结点”。
命题 \(A\)：二叉树的第 \(n\) 层至多拥有 \(2^{n}\) 个结点（定义根结点所在层数 \(n_0=0\)）。
令 \(C(n)\) 表示二叉树第 \(n\) 层拥有的结点数，则要证命题 \(A\)，即证 \(\forall n\in Z^+_0\)，\(C(n)\leq2^{n}\) 总成立。
当 \(n=0\) 时，\(C(0)\leq2^{0}=1\)，命题成立。
假设 \(n=m\) 时命题 \(A\) 成立，即 \(\exists m\in Z^+_0\)，\(s.t.\ C(m)\leq2^{m}\)，则当 \(n=m+1\) 时：
由定义“二叉树的每个结点最多只有两个子结点”可知，第 \(m+1\) 层的结点个数最多为 \(2·C(m)\)，即 \(C(m+1)\leq2·C(m)\)，
而 \(C(m)\leq2^{m}\)，故 \(C(m+1)\leq2·C(m)\leq2·2^{m}=2^{m+1}\)，即命题 \(A\) 在第 \(m+1\) 层成立。
由数学归纳法， \(\forall n\in Z^+_0\)，命题 \(A\) 总成立。
命题 \(B\)：深度为 \(k\) 的二叉树最大为 \(2^{k+1}-1\)（定义二叉树的大小为二叉树中结点的总数、根结点所在深度 \(k_0=0\)）。
令 \(S(k)\) 表示深度为 \(k\) 的二叉树的结点总数。
由命题 \(A\)，二叉树的第 \(n\) 层至多拥有 \(2^{n}\) 个结点，故 \(\\S(k)=C(0)+C(1)+\cdots+C(k)\leq2^{0}+2^{1}+\cdots+2^{k}=1×(1-2^{k+1})/(1-2)=2^{k+1}-1\)。
命题 \(C\)：深度为 \(k\) 的满二叉树（完美二叉树）的大小（结点总数）为 \(2^{k+1}-1\)。
对于深度为 \(k\) 的满二叉树，\(C(i)=2^{i}\) 总成立（\(i=\{0,1,2,3,\cdots,k-1,k\}\)），故满二叉树的结点总数 \(\\S(k)=2^{0}+2^{1}+\cdots+2^{k}=1×(1-2^{k+1})/(1-2)=2^{k+1}-1\)[1]。
命题 \(D\)：深度为 \(k\) 的完全二叉树的结点个数大于 \(2^k-1\)，小于等于 \(2^{k+1}-1\)。
完全二叉树从根结点到倒数第二层满足完美二叉树，最后一层可以不完全填充。
由命题 \(C\)，对于深度为 \(k\) 的完全二叉树，其从根结点到倒数第二层部分的节点总数为 \(2^k-1\)，最后一层填满的情况下二叉树的结点总数为 \(2^{k+1}-1\)，故完全二叉树的结点个数大于 \(2^k-1\)，小于等于 \(2^{k+1}-1\)。
命题 \(E\)：结点个数为 \(S\) 的完全二叉树的深度（高度）为 \([lgS]\)。
假设节点总数为 \(S\) 的完全二叉树的高度为 \(h\)，由完全二叉树的定义，对于高度为 \(h\) 的完全二叉树，其节点总数小于等于高为 \(h\) 的满二叉树的节点总数 \(S_p(h)\)，大于等于高为 \(h-1\) 的满二叉树的节点总数 \(S_p(h-1)\) 加 \(1\)，即
\[1+ S_p(h-1) \leq S \leq S_p(h) \]由命题 \(C\)，\(S_p(h-1)=2^{h}-1\)，\(S_p(h)=2^{h+1}-1\)，故
\[1+ 2^{h}-1 \leq S \leq 2^{h+1}-1\\ 2^{h} \leq S \leq 2^{h+1}-1 \] \[2^{h} \leq S < 2^{h+1} \]取对数有
\[h \leq \log S < h+1 \]解得
\[h = \lfloor\log S\rfloor \]命题 \(F\)：从左到右从上到下构造的大小为 \(N\) 的完全二叉树的叶子结点个数为 \(N-[N/2]\)。
令 \(S_y(N)\) 表示大小为 \(N\) 的完全二叉树的叶子结点个数，要证命题 \(F\)，即证 \(S_y(N)=N-[N/2]\)。
大小为 \(2\) 的完全二叉树的叶子结点个数 \(S_y(2)=1\)，\(N-[N/2]=2-[2/2]=1\)，命题成立。另不难知道大小为 \(0\) 或 \(1\) 的完全二叉树满足命题。
假设命题在 \(N=M\) 时成立，即大小为 \(M\) 的完全二叉树的叶子结点个数 \(S_y(N)=M-[M/2]\)，那么当 \(N=M+1\) 时，若：
① \(M\) 为偶数，那么大小为 \(M\) 的完全二叉树的最后一个结点没有兄弟结点，则大小为 \(M+1\) 的完全二叉树的叶子结点个数为大小为 \(M\) 的完全二叉树的叶子结点个数加一，即 \(S_y(M+1)=S_y(M)+1=M-[M/2]+1\)，而 \(M\) 为偶数，故 \([M/2]=[(M+1)/2]\) 进而 \(M-[M/2]+1=M+1-[(M+1)/2]\)，故命题在 \(N=M+1\) 时成立；
② \(M\) 为奇数，那么大小为 \(M\) 的完全二叉树的最后一个结点有兄弟结点，则大小为 \(M+1\) 的完全二叉树的叶子结点个数与大小为 \(M\) 的完全二叉树的叶子结点个数相等，即 \(S_y(M+1)=S_y(M)=M-[M/2]\)，而 \(M\) 为奇数，故 \([(M+1)/2]=[M/2]+1\) 进而 \(M-[M/2]=M+1-[(M+1)/2]\)，故命题在 \(N=M+1\) 时成立。
另：
当 \(N\) 为偶数时，\(N-[N/2]=N-N/2=N/2=[(N+1)/2]\)；
当 \(N\) 为奇数时 \(N-[N/2]=N+1-[(N+1)/2]=N+1-(N+1)/2=(N+1)/2=[(N+1)/2]\)。
故原命题也可写成：大小为 \(N\) 的完全二叉树的叶子结点个数为 \([(N+1)/2]\)。
data structures - What is the depth of a complete binary tree with \(N\) nodes? - Computer Science Stack Exchange
类似也不难得到满多叉树的大小，比如高度为 \(k\) 的满三叉树的大小 \(S_t(k)=3^{0}+3^{1}+\cdots+3^{k}=(3^{k+1}-1)/2\) ??