考研笔记

二叉树的概念、性质与存储

和完全二叉树的八条编号性质，是第 5 章选择题的两大产地。

教材在 后面专门加了注意框：「该性质经常在选择题中涉及，希望读者牢记并灵活应用。」——这是全书为数不多直接说「牢记」的地方。

这一节还有一条容易被跳过但很值钱的线：二叉树与「度为 2 的有序树」不是一回事。这个区分决定了 5.4.2 树与二叉树的转换 为什么必须规定「左孩子右兄弟」而不能随便对应。

机制

定义与 5 种基本形态

二叉树是一种特殊的树形结构，其特点是每个结点至多只有两棵子树（二叉树中不存在度大于 2 的结点），并且二叉树的子树有左右之分，其次序不能任意颠倒。

递归定义：二叉树是 个结点的有限集合——① 或者为空二叉树，即 ；② 或者由一个根结点和两个互不相交的被称为根的左子树和右子树组成，左子树和右子树又分别是一棵二叉树。

5 种基本形态：空二叉树、只有根结点、只有左子树、左右子树都有、只有右子树。

二叉树 ≠ 度为 2 的有序树

#区别
①度为 2 的树至少有 3 个结点，而二叉树可以为空
②度为 2 的有序树的孩子的左右次序是相对于另一个孩子而言的，若某个结点只有一个孩子，则这个孩子无须区分左右次序；而二叉树无论其孩子数是否为 2，均需确定其左右次序，即二叉树的结点次序不是相对于另一结点而言的，而是确定的

边界辨析：

区别 ② 才是本质。 一棵只有一个孩子的树，在「有序树」里那个孩子就是「第一个孩子」，没有左右可言； 在二叉树里它必须明确是左孩子还是右孩子，两种情况是两棵不同的二叉树（教材图 5.15 就是这一对）。 这正是 5.3.1 里「先序 + 后序 无法唯一确定一棵二叉树」的根源。

几种特殊的二叉树

名称定义
满二叉树高度为 且有 个结点，即每层都含有最多的结点
完全二叉树高度为 、有 个结点，当且仅当其每个结点都与高度为 的满二叉树中编号为 的结点一一对应
二叉排序树见 7.3.1
平衡二叉树任意结点左右子树高度差绝对值 ，见 7.3.2
正则二叉树树中每个分支结点都有 2 个孩子，即树中只有度为 0 或 2 的结点

完全二叉树可视为从满二叉树中删去若干最底层、最右边的一些连续叶结点后所得到的二叉树（教材脚注）。

二叉树的性质

1）非空二叉树上的叶结点数等于度为 2 的结点数加 1，即 。

证明：设度为 的结点个数分别为 ，结点总数 。再看分支数，除根结点外其余结点都有一个分支进入，设 为分支总数，则 。这些分支是由度为 1 或 2 的结点射出的，因此又有 。于是得 ，则 。

2）非空二叉树的第 层最多有 个结点（）。

3）高度为 的二叉树至多有 个结点（）。

关联对照：

教材注意框：性质 2 和性质 3 还可以拓展到 叉树—— 叉树的第 层最多有 个结点， 高度为 的 叉树至多有 个结点。 这两条就是 5.1.3 的性质 2 和性质 3。 两节的公式是同一套，不必分开记。

4）完全二叉树按层序编号 后的八条关系：

#结论
①最后一个分支结点的编号为 ；若 则结点 为分支结点，否则为叶结点
②叶结点只可能在最后两层上出现（当减少 2 个或以上叶结点时，次底层将出现叶结点）
③若有度为 1 的结点，则最多只可能有一个，且该结点只有左孩子而无右孩子，其结点编号为
④按层序编号后，一旦出现某结点（如编号 ）为叶结点或只有左孩子，则编号大于 的结点均为叶结点
⑤若 为奇数，则每个分支结点都有左、右孩子；若 为偶数，则编号最大的分支结点（编号为 ）只有左孩子，没有右孩子
⑥当 时，结点 的双亲编号为
⑦若结点 有左、右孩子，则左孩子编号 ，右孩子编号
⑧结点 所在层次（深度）为

5）具有 个结点的完全二叉树的高度为 或 。

边界辨析：

③ 和 ⑤ 是同一件事的两种说法，也是最常被单独考的一条： 完全二叉树里度为 1 的结点最多一个，而且只能是左孩子。 由此推出： 为奇数 ； 为偶数 。 与 联立，就能由 直接算出 ——这是最快的解题路线。

存储结构

1. 顺序存储：用一组连续的存储单元依次自上而下、自左至右存储完全二叉树上的结点元素，即将完全二叉树上编号为 的结点元素存储在一维数组下标为 的分量中。

  • 完全二叉树和满二叉树采用顺序存储比较合适，结点的序号可以唯一地反映结点之间的逻辑关系。
  • 但对于一般的二叉树，为了让数组下标能反映逻辑关系，只能添加一些并不存在的空结点。最坏情况下，一个高度为 且只有 个结点的单支树却需要占据近 个存储单元。
  • 教材注意框：「建议从数组下标 1 开始存储树中的结点，保证数组下标和结点编号一致。」

2. 链式存储（二叉链表）：每个结点含 data、lchild、rchild 三个域。

在含 个结点的二叉链表中，有 个空链域。

推导（教材在 5.3.2 给出）：每个叶结点都有 2 个空指针，每个度为 1 的结点都有 1 个空指针，空指针总数为 ；又 ，所以空指针总数为 。

这 个空链域正是 线索二叉树 的全部原料。

手算模板

由 求完全二叉树的 ：

  1. 奇 ； 偶 。
  2. 代入 与 。
  3. 解得： 奇时 ； 偶时 。

由编号定位：双亲 、左孩子 、右孩子 、层次 。下标从 1 开始时这套公式才成立。

边界

说法判断说明
「二叉树就是度为 2 的有序树」❌二叉树可以为空，且左右次序是绝对的而非相对的
「二叉树中一定存在度为 2 的结点」❌单支树全是度为 1 的结点
「 对任意树成立」❌只对二叉树。一般树要用三式联立
「正则二叉树就是满二叉树」❌正则只要求没有度为 1 的结点，形状可以很不规则
「完全二叉树的叶结点都在最后一层」❌只可能在最后两层
「完全二叉树中度为 1 的结点可以有多个」❌最多一个，且只有左孩子
「结点 的左孩子一定是 」⚠️只在完全二叉树且下标从 1 开始时成立
「一般二叉树适合顺序存储」❌最坏 个结点要 个单元
「 个结点的二叉链表有 个空链域」❌ 个
「高度为 的二叉树至少有 个结点」✅单支树

口径差异：

算竞里线段树、堆用的都是「下标从 1 开始、左儿子 」的写法，这一点两边完全一致，是本节唯一可以直接迁移的经验。 但**「完全二叉树」的定义两边不同**：算竞里常把「除最后一层外都满、最后一层靠左」当作定义（结果一样）， 而 408 的定义是「与同高度满二叉树编号 一一对应」——考的正是用编号做推理（性质 4 的八条）， 不是判断形状。

对照速查

性质结论
叶与度 2
第 层最多
高度 最多
完全二叉树高度 或
二叉链表空链域
最后一个分支结点
的奇偶
奇数0
偶数1
存储方式适合代价
顺序完全 / 满二叉树一般二叉树最坏 个单元
二叉链表一般二叉树 个空链域被浪费

考点

  • （教材明说「牢记并灵活应用」）。
  • 完全二叉树的八条编号性质（2009、2011、2018 命题追踪）。
  • 由 的奇偶判 ，再求 。
  • 二叉树与度为 2 的有序树的两点区别。
  • 正则二叉树的树高与结点数关系（2016 命题追踪）。
  • 一般二叉树顺序存储的空间浪费（2020 命题追踪）。
  • 二叉链表有 个空链域——线索二叉树的入口。

链接

反向链接