选择题考点总结·第五章：树与二叉树

知识点 4：

???? 完全二叉树的定义：

一棵高度为 h，有2^h - 1个结点的二叉树，当且仅当其每一个结点都与高度为 h 的满二叉树中编号为 1到n的结点一一对应时，称为完全二叉树。

???? 完全二叉树中叶子结点的出现规律：

在完全二叉树中，叶结点数比非叶结点数多一或二者相等。

由以下结论引申而来：

已知 在一棵二叉树中，如果叶子结点数为n₀，度为2的结点数为n₂，则有 : n₀ = n₂ + 1。（见【 2011 . 6 】)

而完全二叉树的叶子结点只可能在层次最大的两层上出现。如图：

情况一 ：没有度为1的结点，即叶结点数比非叶结点数多一。

情况二 ：有度为1的结点，即叶结点数和非叶结点数相等。

可引申出以下结论：

完全二叉树中最后一个分支结点的序号为⌊ n/2 ⌋（向下取整）。