掌握二叉树的性质、顺序与链式存储、遍历和重建方法,并理解线索二叉树、二叉搜索树、平衡树与堆的结构特征。
# 一、二叉树的定义与性质
二叉树是由一个根结点和两棵互不相交的二叉树组成的有序树,分别称为左子树和右子树。左右子树不能互换;每个结点至多有两个孩子,且 “没有左孩子、有右孩子” 与 “有左孩子、没有右孩子” 是不同结构。
若根位于第 层,则第 层最多有 个结点;高度为 的二叉树最多有
个结点。这里高度按层数计,根在第 层。
满二叉树的每一层都填满,高度为 时结点数是 。完全二叉树除最后一层外均填满,最后一层结点从左向右连续排列。若完全二叉树有 个结点、高度为 (按层计),则
设 分别为度数为 的结点数。二叉树边数既等于 ,也等于 ,故
有些资料把 “每个内部结点有两个孩子” 的树称为严格或正则二叉树,把每层填满的树称为完美二叉树。本文使用数据结构课程常用的 “满二叉树” 表示各层均满;碰到不同资料时应依定义作答。
# 二、二叉树的存储结构
# 1. 顺序存储
完全二叉树适合用数组按层序存储。采用从 开始的数组下标时,结点 的关系为
若使用从 开始的下标,则左右孩子分别为 、,双亲为 。一般形状的二叉树使用顺序存储可能在缺失孩子处留下许多空位;完全二叉树或堆则不会产生大量空洞。
# 2. 链式存储
链式存储为每个结点保存数据、左孩子指针和右孩子指针,适用于任意形状的二叉树。
1 | typedef struct BiTNode { |
# 三、二叉树遍历
遍历是按某种次序访问每个结点且恰好一次。先序、中序、后序的区别只在访问根结点的时机。
| 遍历 | 访问顺序 |
|---|---|
| 先序 | 根、左子树、右子树 |
| 中序 | 左子树、根、右子树 |
| 后序 | 左子树、右子树、根 |
| 层序 | 按层从左到右,使用队列 |
1 | void PreOrder(BiTNode *root) { |
三种深度优先递归遍历都访问 个结点,时间复杂度为 ;递归栈空间为 ,其中 为树高。退化成单支树时 。层序遍历使用队列,最坏需要 辅助空间。
先序序列可用于复制或输出树形结构;中序序列在二叉搜索树中为递增序列;后序序列适合先处理子结点再处理父结点,例如释放整棵树或计算表达式。
# 四、由遍历序列构造二叉树
若结点值互不相同,先序序列与中序序列能唯一确定一棵二叉树:
- 先序序列首元素是根。
- 在中序序列中找到根,左侧元素构成左子树,右侧元素构成右子树。
- 按左子树结点数,将先序序列余下部分拆成左、右子树的先序序列,再递归构造。
中序加后序也能唯一确定二叉树,区别是后序末元素为根。先序加后序一般不能唯一确定,因为单孩子结点无法判断孩子位于左边还是右边;若额外保证每个内部结点都有两个孩子,则可唯一重建。
以下图例使用先序序列 A B D C E 和中序序列 B D A C E 。先序首项 A 是根;在中序序列中, A 左侧的 B D 与右侧的 C E 分别属于左右子树,再按子树结点数递归切分先序序列。
# 五、线索二叉树
链式二叉树有 个结点时共有 个左右指针域,其中只有 个指向非空孩子,另有 个空链域。线索二叉树利用空链域存放遍历序列中的前驱或后继信息。
若以中序遍历建立线索,结点的空左指针可指向其中序前驱,空右指针可指向其中序后继。结点还需用标志位区分该指针是孩子链接还是线索。线索化不改变遍历次序,可在不递归、不使用栈的情况下寻找中序前驱或后继。
# 六、二叉搜索树与平衡树
二叉搜索树(BST)满足:左子树所有关键字小于根,右子树所有关键字大于根,且左右子树也分别为二叉搜索树。中序遍历因此得到递增序列。查找、插入、删除的代价与树高 成正比:接近平衡时为 ,按有序关键字依次插入时会退化到 。
AVL 树通过限制每个结点左右子树高度差来保持平衡。定义平衡因子为左子树高度减右子树高度,AVL 要求其属于 。插入后失衡时,根据失衡结点和较高子树的方向,使用 LL、RR 单旋或 LR、RL 双旋恢复平衡,查找、插入和删除均为 。
红黑树以结点颜色和路径黑高约束控制树高,平衡条件比 AVL 宽松,插入和删除通常调整次数更少;其高度仍为 。考题若要求具体旋转过程,应按题目给定的插入或删除规则逐步模拟。
# 七、堆与二叉树应用
堆是满足堆序性质的完全二叉树。大根堆的每个结点都不小于其孩子,小根堆则不大于其孩子。堆适合用数组顺序存储,可在 时间读取堆顶,并在 时间插入或删除堆顶。堆排序和树搜索的细节分别在排序、查找笔记中展开。
# 八、考场检查清单
- 左右子树是有序的;只有一个孩子时,孩子位于左或右会形成不同二叉树。
- 完全二叉树的数组下标公式依赖从 还是从 开始。
- 二叉树的叶子数满足 。
- 先序加中序、后序加中序在结点值互异时可唯一确定;先序加后序一般不行。
- BST 操作取决于树高,只有保持平衡才能保证对数级代价。
