13.3.2 树与二叉树的特性-01

本节重点是二叉树的基本定义、满二叉树、完全二叉树，以及由层次产生的一组常考性质。课程建议：不要把公式当孤立结论，先用满二叉树代入验证。

二叉树的定义

二叉树中每个节点的度最多为 2，可以是 0、1、2，但不能超过 2。更重要的是，左子树和右子树有顺序。

flowchart TD
  A["根"] --> B["左子树"]
  A --> C["右子树"]

即使一个节点只有一个孩子，也要区分它是左孩子还是右孩子，因为遍历和结构判断都会受影响。

满二叉树与完全二叉树

类型	定义	判断关键词
满二叉树	除叶子层外，每个分支节点都有两个孩子，所有层都达到最大节点数	每层都满
完全二叉树	除最后一层外其余层全满，最后一层节点从左到右连续排列	最后一层只缺右侧

满二叉树一定是完全二叉树；完全二叉树不一定是满二叉树。

完全二叉树的直观判断

完全二叉树可以理解为：把满二叉树从上到下、从左到右编号后，保留编号连续的一段。

情况	是否完全二叉树
最后一层缺最右侧 1 个节点	是
最后一层缺最右侧多个节点	是
最后一层中间缺一个，右侧还有节点	否
非最后一层缺节点	否

第 $i$ 层最多节点数

二叉树第 1 层最多 1 个节点，第 2 层最多 2 个，第 3 层最多 4 个。推广到第 $i$ 层：

$$2^{i-1}$$

这来自“每下一层，最多翻倍”。

高度为 $h$ 的二叉树最多节点数

高度为 $h$ 时，最多情况是满二叉树：

$$1+2+4+\cdots +2^{h-1}=2^h-1$$

最少情况是每层只有一个节点的单支树：

$$h$$

所以高度为 $h$ 的二叉树节点数范围是：

$$h\le n\le 2^h-1$$

完全二叉树编号性质

完全二叉树按从上到下、从左到右编号，节点编号为 $i$，总节点数为 $n$：

条件	结论
$i=1$	节点是根，无父节点
$i>1$	父节点编号为 $\lfloor i/2\rfloor$
$2i\le n$	左孩子编号为 $2i$
$2i+1\le n$	右孩子编号为 $2i+1$
$2i>n$	没有左孩子，是叶子节点

这些公式来自满二叉树编号，考试中画 7 个节点的小满二叉树就能快速验证。

本节例题

单选

高度为 $h$ 的二叉树最多有多少个节点？

AhB2^h - 1C2h - 1Dh²

自查清单

1. 能否用“最后一层从左到右连续”判断完全二叉树？
2. 能否推导第 $i$ 层最多 $2^{i-1}$ 个节点？
3. 能否根据编号 $i$ 找父节点、左孩子、右孩子？