5.2.1 二叉树定义与性质

二叉树中每个结点最多有左、右两棵有序子树；即使只有一个孩子，也必须区分左还是右，因此它不同于度不超过 2 的普通树。第 $k$ 层最多 $2^{k-1}$ 个结点，高度 $h$ 最多 $2^h-1$ 个。设叶数 $n_0$、二度结点数 $n_2$，由边数得 $n_0=n_2+1$。

手工推演

若 $n_0=8$，则 $n_2=7$，一度结点数无法由此确定。满二叉树高度 4 有 15 个结点。完全二叉树按层序从左到右填充，编号 $i$ 的左、右孩子分别为 $2i,2i+1$（不超过 $n$），双亲为 $\lfloor i/2\rfloor$。

结构与代码

完全二叉树有 $n$ 个结点时高度为 $\lfloor {\log }_{2}n\rfloor +1$。编号公式依赖根编号为 1；若数组从 0 开始，孩子改为 2*i+1,2*i+2。

错解反馈

把满二叉树和完全二叉树等同；认为只有右孩子也能出现在完全树中；把普通树孩子无序的性质套到二叉树；编号公式混用 0/1 基。

迁移练习

完全二叉树有 100 个结点，叶可能从哪个编号开始？最后一个非叶为 $\lfloor 100/2\rfloor =50$，所以 51 至 100 都是叶。独立验收：能用编号验证孩子与双亲。