数据结构 第四章 树(速览)

数据结构目录阅读详版下载 Markdown

1. 树

定义与术语

• 树(递归定义): 有限个 $(n>0)$ 元素的集合: ① 有一个结点称为根;② 其余结点分为若干个互不相交的非空子集,每个子集又是一棵树(根的子树);③ 子树的根是树根结点的孩子。注意前提是 $n>0$。
• 直观特征/前驱后继: 上层元素是直接前驱且唯一,下层元素是直接后继且可有多个;父结点即孩子的直接前驱,孩子即父的直接后继。
• 术语: 子树之根为该结点的孩子,反之为父结点;根到某结点路径上所有结点(含根)为其祖先,反之为子孙;同一父结点的结点互为兄弟;父结点的父结点为祖父结点。
• 度 = 结点拥有的孩子个数;度为 0 的是叶子(终端)结点,度不为 0 的是非叶子(非终端/中间)结点;树的度 = 各结点度的最大值。
• 层次与高度: 根的层次规定为 1,其余结点层次 = 父层次 + 1;树的高度 = 所有结点层次数的最大值;提醒——高度是从顶到底数的。
• 有序树: 任一结点的孩子都规定了顺序;未规定则为无序树。森林: 两棵及以上的树。

抽象数据类型与物理结构

• ADT: 有限 $(n>0)$ 个相同类型元素组成;9 个操作——Constructor、Deconstructor、GetRoot、FirstChild、NextChild、Search、InsertChild、DeleteChild、Traverse(访问每一结点且每结点只访问一次)。
• 顺序结构存树不经济: 各结点孩子个数不一样,难以确定设几个字段存孩子地址(多则浪费、少则不够);父结点下标数组法(每结点存父下标,根记 -1)省空间,但找孩子要遍历整个数组,$O(N)$。
• 链式结构同样存在孩子指针个数不好预估的问题;结论: 没有合适的物理存储做基础,树的基本操作就无从谈起。

2. 二叉树

定义与特殊二叉树

• 二叉树: 有限个($n \geq 0$)结点的集合,或者为空,或者由根结点与左右两个互不相交的子树组成,每个子树又是一棵二叉树(递归定义)。
• 二叉树和树是两种完全不同的结构,二叉树不是一棵特殊的树: ① 二叉树结点个数可以为 0(允许空二叉树),树必须至少为 1;② 二叉树即便只有一个孩子也必须指明是左子还是右子,有序树的孩子只排序、无左右之分——根带一个左孩子与带一个右孩子是两棵不同的二叉树,对树而言却等价。
• 满二叉树: $k$ 层且每层结点数都达最大值 $2^{k-1}$。完全二叉树: 前 $k-1$ 层全满,第 $k$ 层缺结点只能自右向左缺(逐层从上到下、从左到右遍历不跳过任何结点)。

性质 1–5

• 性质 1: 非空二叉树第 $i$ 层最多 $2^{i-1}$ 个结点($i \geq 1$);数学归纳法证。
• 性质 2: 高度为 $k$ 的二叉树最多 $2^k - 1$ 个结点($N=\sum_{i=1}^{k} 2^{i-1}$,等比数列求和)。
• 性质 3: 非空二叉树 $n_0 = n_2 + 1$。证法: 自下向上数边(除根每结点恰一条向上边)得 $n_0+n_1+n_2-1$,自上向下数边得 $n_1 + 2n_2$,两式相等。
• 性质 4: $n$ 个结点的完全二叉树高度 $k = \lfloor \log_2 n \rfloor + 1$(由 $2^{k-1} \leq n < 2^k$ 取对数)。
• 性质 5: 完全二叉树按层自上而下、每层自左而右从 1 编号,编号 $i$($1 \leq i \leq n$): ① $i=1$ 为根;② $i>1$ 时父编号为 $\lfloor i/2 \rfloor$;③ $2i > n$ 则无左子,否则左子编号 $2i$;④ $2i+1 > n$ 则无右子,否则右子编号 $2i+1$。结点是否存在的判定: 编号大于 $n$ 即不存在。

存储

• 顺序存储 Naive 法(每结点存 Value / Parent / Left / Right 下标)缺点: ① 信息冗余(父子互存);② 大量无效值 -1(叶子、根)。
• 利用性质 5 的顺序存储: 只用一个一维数组,根放下标 1(下标 0 不用),下标 $i$ 的左子放 $2i$、右子放 $2i+1$;孩子下标除 2 取下整即父下标(Notes 助记"我是二分之你");非完全二叉树在数组中留空洞。优点: 需存信息更少;缺点: 退化成一条链时空间最坏 $O(2^n)$(课件该条版面标签误写为"优点")。
• 链式存储两种形式: 标准形式 Left | Data | Right;广义标准形式再加 Parent 指针。通常用标准形式——求父结点概率不大,且可通过遍历检查谁的孩子是 x 来求 x 的父;标准形式最直观,特点"最小化、完备"(Notes)。
• Notes 提示: 算法 + 数据结构 = 程序。

四种遍历

• 遍历: 对每个元素访问且只访问一次;以任一结点为根的子树仍是二叉树,定义天然递归。遍历要解决: 访问根后先遍历左子还是右子?到子结点后如何返回父结点(链式结点通常不存父信息)?
• 前序"根左右"、中序"左根右"、后序"左右根";层次遍历: 从第一层起自上而下逐层、同层自左向右;四者对空二叉树遍历操作均为空。
• 一般有序树没有中序遍历(根有多个孩子,无法定义)。
• 递归实现: 把定义直接翻译成语句即可,直观简单;中序递归实现应递归调用 _in_order 处理左右子树。

非递归遍历(机制与复杂度)

• 总思路: 用**栈保存"调用信息"**模拟递归。
• 前序非递归: 根进栈;循环至栈空——出栈、访问,先压右子、后压左子(栈先进后出,左子后压先弹,保证"根左右")。每结点由唯一父结点带入栈、只进栈一次,出栈即访问,循环 $n$ 次,时间 $O(n)$。
• 中序非递归: 每结点需访问两次(第一次经它去访问左子树,第二次访问本身及右子),故引入 flag 记录第几次被访问: 弹出 flag=0 → 标志改 1 重新压栈,有左子则压左子;弹出 flag=1 → 访问,有右子则压右子。边界约定: 标志数组初始值为 0。每结点经历两次循环,共 $2n$ 次,$O(n)$。
• 后序非递归: 每结点需访问三次,flag 有三种状态——0 首次进栈、1 已考虑过左子、2 已考虑过右子;弹出 0 → 改 1 重压并压左子,弹出 1 → 改 2 重压并压右子,弹出 2 → 直接访问。循环 $3n$ 次,$O(n)$。
• 代码边界: 课件文字算法对空树约定为遍历操作为空,但非递归前/中/后序代码片段均直接把根指针入栈;直接复用时需先判空或保证根非空。
• 层次遍历: 把辅助工具由栈换为队列——根进队;循环至队空: 队首出队、访问,有左子左子进队、有右子右子进队;"先左后右"靠队列先进先出保证。结点访问完后续不再需要,故与前序非递归一样不需 flag。每结点进队、出队各一次,$O(n)$。

构造与基本操作

• 层次构造: 反用层次遍历——队首出队,依次取序列元素作其左、右孩子并进队,直到队空;完全二叉树可直接以层次遍历结果为输入;一般二叉树先用空值 NULL_VALUE 占位补全成完全二叉树,以含占位的层次序列为输入;NULL_VALUE 只占序列位置、不建结点也不进队。易错点: 输入可能没有末尾的 NULL_VALUE,取 v[i+1] 前须判断 i+1 < v.size() 防越界。
• size: 空树返回 0,否则 1 + 左右子树结点数;height: 空树返回 0,否则 1 + 左右子树高度的最大值;delTree: 递归先删左、再删右、最后删当前结点,删完 root 置空。root 是私有成员,带参递归函数设为私有,公有无参函数调用之以方便外部调用。

3. 遍历序列确定二叉树

• 完全二叉树: 已知层次遍历能唯一确定;满二叉树: 已知前/中/后序之一能唯一确定;一般二叉树: 单一前/中/后序不能唯一确定(反例: 前序 ABC 既可对应 A 根、B 左 C 右,也可对应 A—B—C 单支链)。

序列组合	能否唯一确定一棵二叉树
前序 + 中序	能
后序 + 中序	能
前序 + 后序	不能(反例: B 为 A 的左或右孩子,前序均 AB、后序均 BA)

• 原因: 前序中根在最前、后序中根在最后,二者提供的信息一致,都能与中序提供的信息互补;而前序与后序提供的信息是重叠的而非互补的,一方得不到的信息另一方也无从获知。
• 前序+中序构造算法: 先检查输入合法(非空、等长、元素相同且无重复);用前序首元素 pre[pre_l] 定根 → 在中序中线性找到根的位置 $pos$,其左为左子树、右为右子树,由此得到两序列中左右子树的下标范围,递归构造;递归终止条件为下标范围为空(返回 nullptr);左子树结点个数 = $pos$ − 中序左端点。后序+中序同理,只是在后序序列末尾找根。

4. 最优二叉树

• 路径长度: 两结点间路径上的分支总数。加权路径长度 $WPL=\sum_{k=1}^{n} w_k L_k$($n$ 为叶子个数、$w_k$ 为第 $k$ 个叶子的权值、$L_k$ 为根到该叶子的路径长度);同一组带权叶子,二叉树形态不同则 WPL 不同。
• 最优二叉树: 使 WPL 达到最小的二叉树;构造采用贪心策略——权值越大,越靠近根。
• 哈夫曼算法步骤(输入带权结点集合 $U$): ① 若 $U$ 中只有一个结点,结束;② 取两个权值最小的结点 $x,y$,构造新结点 $z$(权值 = 两者之和),在 $U$ 中删去 $x,y$、加入 $z$,转 ①。哈夫曼树是一棵最优二叉树。
• 构造示例结论: 对 $U=\{A{:}3, B{:}8, C{:}10, D{:}12, E{:}50, F{:}4\}$,依次合并 $(A,F){\to}7$、$(7,B){\to}15$、$(C,D){\to}22$、$(15,22){\to}37$、$(37,E){\to}87$,根权 87;权值最大的 E 离根最近(路径长 1),最小的 A、F 最远(路径长 4)且互为兄弟。
• 最优性: 定理 4-1——最优二叉树中两个最小权 $w_1,w_2$ 的叶子是兄弟,且以它们为儿子的中间结点路径长度最长;定理 4-2——把该中间结点改为带权 $w_1+w_2$ 的叶子,新树仍是最优二叉树。
• 实现与复杂度: 链接存储,HuffmanNode 四字段 data / weight / left / right(孩子初始化为空指针);所有结点放入 vector,反复取出两最小合并、新结点放回,最后一个结点即根。创建 $n$ 叶 $O(n)$;$n-1$ 次合并、每次找两最小 $O(n)$,总时间 $O(n^2)$;学堆后找最小可降为 $O(\log n)$,总体降到 $O(n\log n)$。
• 前缀编码: 字符编码可不等长,但任何一个字符的编码不得是另一个编码的前缀;易错点——否则会造成解码的多义性。哈夫曼编码是一种前缀编码。
• 求编码方法: 从根开始遍历,向左加 0、向右加 1,直到叶子结点。上例编码: E=1、C=010、D=011、B=001、F=0001、A=0000;平均码长 $\frac{168}{87}$ 位/字符,不到 2 位,远优于等长编码的 3 位($3n$ 位)。
• 求编码复杂度: 哈夫曼树共 $2n-1$ 个结点(构建中添加 $n-1$ 个中间结点),每结点只遍历一次,$O(n)$。

5. 树和森林

• 两种常用存储: 双亲表示法(顺序存储)、孩子兄弟法(二叉树存储);常用孩子兄弟法,可复用二叉树的基本操作。
• 孩子兄弟表示法: 结点存 data、firstchild(指向最大孩子,又称左分支/左子)、nextsibling(指向最大弟弟,又称右分支/右子)。
• 树 → 二叉树: 树的根即二叉树的根;每结点保留其到最大孩子的分支,其余孩子删除到父的分支、逐个降级,链到最小哥哥结点的右分支上。
• 森林 → 二叉树: ① 每棵树各自转为二叉树;② 各树的根视作兄弟;③ 第一棵二叉树的根作为整体的根,其余根由其最小哥哥用 nextsibling 连接(即各树根一个接一个链在最小哥哥的右分支上)。
• 二叉树 → 树/森林(三者一一对应): 二叉树的根即第一棵树的根;断开每个结点 nextsibling 发出的分支,右分支结点上移至连续右分支最上层——上层结点有父则作该父的次子,无父则作一棵新树的根。
• 树的遍历只有前序、后序、层次三种;根有多个孩子,无法定义中序遍历。
• 结论: 树的先根(前序)遍历 = 对应二叉树的先序遍历;树的后根(后序)遍历 = 对应二叉树的中序遍历;森林同理——森林的先序遍历 = 对应二叉树的先序遍历,森林的中序遍历(即前页所称森林的"后序遍历")= 对应二叉树的中序遍历。
• 应用(遍历是基础): 求树高——用对应二叉树前序遍历,左子层次 = 父层次 + 1、右子层次与父相同;求森林中树的棵数——在二叉树中顺着根一路右子计数。
• 思考题结论: 已知一棵结点标识可区分(无重复)的树的前序和后序遍历,可以唯一确定这棵树——树前序 = 对应二叉树前序、树后序 = 对应二叉树中序,前序+中序唯一确定二叉树,该二叉树又唯一对应一棵树。

6. 优先级队列

• 优先级队列: 结点关系由优先级决定而非入队先后,优先级高的先出队;接口与普通队列相同。
• 用普通队列的两种简单实现: ① 入队时按优先级找位置插入,出队不变——入队 $O(N)$、出队 $O(1)$;② 入队仍放队尾,出队时查找优先级最高者——入队 $O(1)$、出队 $O(N)$。

二叉堆

• 堆的定义: 一棵完全二叉树,且每个有孩子的结点 $i$ 对所有存在的孩子满足 $k_i \le k_{2i}$、$k_i \le k_{2i+1}$(最小堆)或 $k_i \ge k_{2i}$、$k_i \ge k_{2i+1}$(最大堆),不存在的孩子不参与比较,下标为层次遍历次序。两特性: 结构性(完全二叉树)+ 有序性(最小堆父小于子 / 最大堆父大于子)。
• 注意: 课件写"以下讨论以最大化堆为例",但后续插入/删除讲解实际均以最小堆为例;课件代码注释与命名(maxValue、"maximum element")为最大堆口径,按最小堆语义应理解为 minValue/"minimum element",根处返回的是最小元素。
• 存储: 完全二叉树故可顺序存储,下标 0 不用、根在下标 1;最小堆的最小元素就是根。数值越小优先级越高时,用最小堆存优先级队列;获取队头即返回下标 1 的元素。
• push(插入): 新元素必须放在最大序号元素之后(否则违反结构性);若违反有序性,让其向父结点移动直到满足有序性或到根——向上过滤(percolate up)。最坏 $O(\log N)$(完全二叉树高度);平均比较 2.6 次、上移 1.6 层,平均 $O(1)$。
• pop(删除): 删根后根处留空洞,按结构性最后一个结点应删掉,将其值填入空洞并向下过滤——与两孩子比较,取三者中最小者交换,直到无孩子(叶子)或当前值比两孩子都小。最坏 $O(\log N)$;最后结点值一般较大、向下过滤很少提前结束,平均也是对数时间。空队 pop 抛出异常;删除后堆非空才执行向下过滤。
• 建堆: 看成 $N$ 次连续插入需 $O(N\log N)$;关键观察——只需最终状态满足有序性、中间过程无所谓,故可降到 $O(N)$。做法: 按逆向层次次序对结点调用 heapify_down(处理结点 i 时其子孙均已处理过);易错点——叶结点不需调用(调用也不会有变化),从编号最大的非叶结点开始。代码从 data.size()/2 递减到根($N$ 为奇数时该起点实为第一个叶结点,空操作、结果仍正确)。
• 建堆 $O(N)$ 的依据: 高度为 $h$ 的结点(叶为 0)在 heapify_down 中最多交换 $h$ 次,建堆时间 = 所有结点高度之和;定理: 高度 $h$、$N = 2^{h+1} - 1$ 个结点的满二叉树,结点高度和为 $N - h - 1$(错位相减法证: $2s-s=(2^{h+1}-1)-(h+1)$)。

小结

• 树: 第一种非线性结构,元素个数大于零,上下层一对多的层次关系;鉴于物理存储难题,转而讨论二叉树。
• 二叉树: 元素个数大于等于零,每结点最多两个孩子且明确左右(只有一个儿子也要明确是左是右,而非"第一个孩子");故不能简单说二叉树是一棵有序树,它们是二种不同的数据结构。
• 二叉树的地位: 现实中直观对应二叉树的数据极少,它更多是虚构出来的工具结构,可解决很多实际问题——树和森林的孩子兄弟表示法、后续的二叉查找树、堆排序等。
• 优先级队列: 程序设计常用工具;二叉堆是其优秀实现;重要应用——多服务台排队系统的模拟。