# 数据结构 第四章 树(速览) > Arietids Learn · 个人课程复习笔记 > 在线阅读：https://learn.arietids.net/courses/data-structures/chapter-04-quick/ ## 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)$)。 ### 小结 - **树**: 第一种非线性结构,元素个数大于零,上下层一对多的层次关系;鉴于物理存储难题,转而讨论二叉树。 - **二叉树**: 元素个数大于等于零,每结点最多两个孩子且明确左右(只有一个儿子也要明确是左是右,而非"第一个孩子");故不能简单说二叉树是一棵有序树,它们是二种不同的数据结构。 - **二叉树的地位**: 现实中直观对应二叉树的数据极少,它更多是虚构出来的工具结构,可解决很多实际问题——树和森林的孩子兄弟表示法、后续的二叉查找树、堆排序等。 - **优先级队列**: 程序设计常用工具;二叉堆是其优秀实现;重要应用——多服务台排队系统的模拟。