二叉树

• 定义：$n$ 个结点的有限集合，或者为空，或者由根节点及两棵互不相交的左、右子树组成。
• 满二叉树：深度为 $k$ 且有 $2^k-1$ 个结点的二叉树。
• 完全二叉树：编号与满二叉树一一对应（只缺最后一层右边）。

关键性质 (必考公式)

1. 第 $i$ 层至多有 $2^{i-1}$ 个结点。
2. 深度为 $k$ 的二叉树至多有 $2^k-1$ 个结点。
3. 叶子与度为2结点关系：$n_0=n_2+1$。
   • 推导：总边数 $B=n-1=n_1+2n_2$，总节点数 $n=n_0+n_1+n_2$，联立可得。
4. 完全二叉树高度：$k=\lfloor {\log }_{2}n\rfloor +1$。
5. 编号性质 (从1开始编号)：
   • 结点 $i$ 的双亲：$\lfloor i/2\rfloor$。
   • 左孩子：$2i$；右孩子：$2i+1$。