---

第五章 树与二叉树

小题考频：30
大题考频：8

---

5.3 二叉树的遍历和线索二叉树

难度：☆☆☆☆

知识总览

5.3.1_1 二叉树的先中后序遍历

5.3.1_2 二叉树的层次遍历

5.3.1_3 由遍历序列构造二叉树

5.3.2_1 线索二叉树的概念

5.3.2_2 二叉树的线索化

5.3.2_3 在线索二叉树中找前驱后继

---

5.3.1_1 二叉树的先中后序遍历

什么是遍历

——遍历：按照某种次序把所有结点都访问一遍

线性结构：可以从头往后依次遍历，或者从尾开始往前面依次遍历。

树：层次遍历
——基于树的层次特性确定的次序规则

树：先/中/后序遍历
——根据二叉树的递归特性建立
本小节学习的三种遍历算法

二叉树的遍历

可以根据根、左子树、右子树三个部分被访问的顺序，指定三种遍历规则，分别是先序、中序和后序遍历。
如果子树还有下一级的结点，那么仍按照规则进行。

或者叫先根遍历、中根遍历、后根遍历。

Eg最简单的.

先序遍历：先访问根结点，根左右【ABC】
中序遍历：在中间访问根结点，左根右【BAC】
后序遍历：最后访问根结点，左右根【BCA】

Eg更复杂的.

先序遍历：根左右（ABC），先访问根结点【A】，因为左结点是一个分支结点，B子树也需要递归，所以需要对B子树也进行先序遍历【BDE】，然后对C子树先序遍历【CFG】，所以遍历顺序为：【A BDE CFG】
中序遍历：左根右（BAC），先访问B子树，也进行中序遍历【DBE】，然后访问根结点【A】，然后对C子树中序遍历【FCG】，所以遍历顺序为：【DBE A FCG】
后序遍历：左右根（BCD），先访问B子树，也进行后序遍历【DEB】，然后对C子树【FGC】，最后访问根结点【A】，所以遍历顺序为：【DEB FGC A】

可以把叶子结点D理解为下面还连着两个空子树，所以对这样的一棵子树进行先序遍历、中序遍历、后序遍历得到的都只有D自己。

---

二叉树的遍历（手算练习）

练习1

1. 先序遍历：
   
2. 中序遍历：
   
3. 后序遍历：
   

这种手算确定序列的方法称为分支结点逐层展开法。
如果一个结点是分支结点而不是叶子结点的话，就需要嵌套递归的按照特定的遍历序列把它展开到下一级

练习2

1. 先序遍历：

- + /
- +a* /ef
- + a b- /ef
-+ab-cd/ef

2. 中序遍历：

+ - /
a+* - e/f
a+b*- - e/f
a+b*c-d-e/f

3. 后序遍历：

+ / -
a*+ ef/ -
a b-* + ef/ -
abcd-*+ef/-

可以发现：

对算术表达式“分析树”进行前中后序遍历，可以得到算数表达式的前中后缀表达式。

---

先序遍历（代码）

定义结构体：


先序遍历：

1. 如果二叉树非空，按根左右的顺序，先访问（visit）根结点（可以在visit函数中定义一些操作，比如说打印结点的值等等）；
2. 接下来先序遍历左子树，需要递归的调用先序遍历这个函数，传入左子树的根结点，即当前根的左孩子（lchild）；
3. 遍历完左子树后，先序遍历右子树，传入右孩子结点（rchild）

中序遍历和后序遍历的代码也及其类似：
中序遍历把visit函数放在中间；
后序遍历把vist函数放在最后。

中序遍历：

后序遍历：

---

函数如何执行？

——以先序遍历代码为例：
Step1：调用PreOrder函数，传入的参数T，指向结点A；

由于结点非空，会vist访问这个结点，结点A是第一个被访问的结点

系统会记录下，当前执行到126行代码

Step2：递归左子树，函数会调用自身，传入的参数T，指向当前结点的左孩子（lchild），即结点B

由于结点非空，会vist访问这个结点，结点B是第二个被访问的结点

系统会记录下，当前执行到126行代码

Step3：递归左子树，函数会调用自身，传入的参数T，指向当前结点的左孩子（lchild），即结点D

Step4：接下来访问结点d的左孩子，为空，那么传入的参数T为NULL

因为不满足T != NULL，所以这一层的函数中什么也不做，直接return返回
这层函数执行结束后把信息弹出栈。

Step5：返回上一层的函数，继续处理结点D，之前执行的是126行，接下来执行127行，传入参数T变成了右孩子，即结点G

Step6：访问结点G，接下来访问G的左孩子（#126），为空，返回G结点；访问G的右孩子（#127），为空，返回G结点，且执行结束，返回D结点。

G的左孩子和右孩子都为空，所以#126和#127行函数什么也不会做，执行结束后返回D结点

Step7：D结点也执行结束，返回处理B结点这层函数。

Step？：接下来处理B的右子树（#127）…………

剩下的过程都是类似的，不再赘述。

可以看出这种递归实现遍历的算法，空间复杂度应该是O(h+1)，其中h指的是二叉树的高度，+1是因为最后一层的叶子结点下面有两个空结点，处理空结点的这层函数也需要把信息压到栈顶。
 
舍去常数项：
时间复杂度为：$O(h)$

---

求先序遍历序列

【红色箭头】表示的是第一次路过这个结点；
【绿色箭头】表示的是第二次路过这个结点；
【紫色箭头】表示的是第三次路过这个结点；

从根结点出发，优先选择左边的路走，然后往右走，然后往上走。
先序遍历就是在第一次路过该结点的时候访问该结点【红色箭头】

---

求中序遍历序列

中序遍历就是在第二次路过该结点的时候访问该结点【绿色箭头】

---

求后序遍历序列

后序遍历就是在第三次路过该结点的时候访问该结点【绿色箭头】

以上，即“从你的全世界路过”法确定二叉树序列…

练习

再用这棵二叉树练练手：

补上空结点，然后开始模拟递归函数的执行原理来遍历

• 先序遍历：- + a * b - c d / e f
• 中序遍历：a + b * c - d - e / f
• 后序遍历：a b c d - * + e f / -

---

例：求树的深度（应用）

根据二叉树的递归特性，分为根结点、左子树、右子树。

求一个树的深度，首先求出左子树的深度和右子树的深度，接下来对比左子树的深度和右子树的深度，选取深度更深的一边+1作为树的深度。
树的深度 = Max｛左子树深度，右子树深度｝+ 1

代码中，访问左 - 访问右 - 访问中，可以看做后序遍历的一个变种。

---

5.3.1_2 二叉树的层次遍历

该二叉树层序遍历结果为：A BC DEFG HIJKL

算法思想

1. 初始化一个辅助队列：

2. 根结点入队：

3. 若队列非空，则队头结点出队，访问该结点，并将其左、右孩子插入队尾（如果有的话）：

A出队，访问结点A，并将其左、右孩子B、C插入队尾

4. 重复步骤3直至队列为空：

E结点没有左右孩子，访问完结点E之后没有结点入队

HIJKL结点没有左右孩子，访问完他们之后没有结点入队

---

代码实现

二叉树结点：

首先初始化一个辅助队列：

链式队列结点数据结构定义
【使用链队列】：难以估计访问的树有多少个结点

初始化队列，让元素入队，在第三章中已经讲述过，不再赘述。

对于二叉树结点入队，并不需要在队列中保存一整个结点的真实数据，只需要保存这个结点的一个指针就可以了。

使用while循环：

当队列不空的时候，就会一直循环的让队头元素出队，然后访问此次出队的结点

可以在visit函数中自定义访问一个结点的时候需要进行的一系列操作，比如打印结点的值等

访问当前结点，如果有左孩子，将左孩子入队；如果有右孩子，将右孩子入队
一直循环，直到队列为空

---

5.3.1_3 由遍历序列构造二叉树

不同二叉树的中序遍历序列：

可以发现一个中序遍历序列可能对应多种二叉树形态

不同二叉树的前序遍历序列：

不同二叉树的后序遍历序列：

不同二叉树的层序遍历序列：

同样的，可以发现，如果只有前/中/后/层序遍历序列中的一种，那么其可能对应多种二叉树形态

结论：若只给出一棵二叉树的前/中/后/层序遍历序列中的一种，不能唯一确定一棵二叉树

一定要有中序遍历序列才能推出二叉树

---

前序+中序遍历序列

前序序列中最先出现的结点肯定是根结点，可以确定根结点在中序遍历中的位置
 
中序序列中根结点左边出现的结点一定是左子树中的结点，右边即右子树
 
如此递归地恢复出二叉树

Eg1：前序+中序遍历序列

前序序列中第一个出现A的一定是根结点

通过中序序列可以确定左子树中有三个结点BDC，右子树中有一个结点E
对应的前序序列中根结点后的三个结点DBC为左子树结点

相同的逻辑，前序序列中D是左子树的根结点；

中序序列中左边的B为左孩子，右边的C为右孩子

---

Eg2：前序+中序遍历序列

原理与Eg1.相同

---

后序+中序遍历序列

后序序列中最先出现的结点肯定是根结点，可以确定根结点在中序遍历中的位置
 
中序序列中根结点左边出现的结点一定是左子树中的结点，右边即右子树
 
如此递归地恢复出二叉树

Eg3：后序+中序遍历序列

---

层序+中序遍历序列

层序序列中第一个被访问的结点肯定是根结点，接下来访问的应该是左子树的根结点，下一个是右子树的根结点
 
思路类似，在中序序列找到根结点，划分左子树和右子树，然后找到左子树和右子树的根，进一步对左右子树进行下一层的划分
 
如此递归地恢复出二叉树

Eg4：层序+中序遍历序列

对于左子树来说，A就是根结点，左孩子是E，右孩子是F；对于右子树来说，B就是根结点，下一层左边应该是HC，右边应该是GI

下一层结点为C、G，H为C的左孩子，I为G的右孩子

---

Eg5：层序+中序遍历序列

从中序序列看出，A的左边是没有任何东西的，意味着这棵二叉树的左子树是空的

---

总结

• 最重要的是找到树的根结点，并根据中序序列划分左右子树，再找到左右子树根结点

---

若前序、后序、层序序列两两组合

结论：前序、后序、层序序列的两两组合无法唯一确定一棵二叉树
一定要有中序遍历序列才能推出二叉树

---

5.3.2_1 线索二叉树的概念

之前已经了解过普通的二叉树，可以对它进行中序遍历：

从得到的遍历序列来看，他们之间其实是一种线性的关系；
每一个元素有一个与之对应的前驱，还有一个与之对应的后继
（和线性表一样，第一个元素没有前驱，最后一个元素没有后继）

一个结点只有一个唯一的前驱，并且可能会有多个后继，这是从树本身的逻辑结构出发定义的前驱和后继，与此处不同。

此处讨论的数据元素的前驱和后继是基于遍历序列来定义的前驱和后继。

Q：能否从一个指定结点开始中序遍历？

每当对二叉树进行中序遍历，都需要从根结点出发，必须要知道根结点。

如果在某些场景中，只能知道某个结点的指针，并不知道根结点是哪个。
那么如果只给出G结点的指针，那么能否从G结点出发，对这棵树进行中序遍历呢？
——即遍历G B E A F C这些结点。

做不到！

因为G结点只有指向其孩子的指针，并不可能往回找到其双亲结点，或者找到其后继结点B。

1. 普通的二叉树存在的第一个问题：
   每当对二叉树进行中序遍历，都需要从根结点出发，否则完成不了中序遍历。

在此处回忆线性表，如果这些元素D G B E A F C是一个线性表，知道其中任意一个元素的指针，就可以找到这个元素后面的所有元素。
也就是说：对线性表的遍历，并不是每一次都必须从头开始遍历，可以从任何一个元素开始往后遍历。
但普通的二叉树不可以，每一次遍历都必须从头开始。

2. 普通的二叉树存在的第二个问题：
   如何找到指定结点p在中序遍历序列中的前驱和后继？
   

此处F结点是第6个被访问到的，其中序遍历中的前驱结点应该是A
如果只给出F结点的指针，肯定没办法找到前驱A，因为每一个结点只拥有向下一层的指针，不能往上找

思路：
从根结点出发，重新进行一次中序遍历，指针q记录当前访问的结点，指针pre记录上一个被访问的结点
①当q==p时，pre为前驱
②当pre==p时，q为后继

中序遍历过程中，D结点是第一个被visit的结点，开始时让q指向D，此时没有前驱，所以pre是指向NULL的

进行对比，q和p并没有指向同一个结点，继续往后visit，在下一个结点被visit之前，把pre指针指向当前q所指向的结点：
让q指向下一个被visit的结点：

那么现在pre指针指向的结点就是q指针指向结点的，中序序列中的前驱

通过这个思路，让q指针不断指向后一个被访问的结点，然后pre指针依次后移，最终直到q和p指向同一个结点

那么此时pre所指向的结点，就是p所指向结点的前驱

再后移一次，此时pre和p指向同一个结点

那么此时q所指向的结点，就是p所指向结点的后继

缺点十分明显：找前驱、后继很不方便；操作必须从头开始

如果在某些应用场景中，找前驱、找后继、遍历这些操作十分频繁的话，普通二叉树的设计会体现出缺点。

---

中序线索二叉树

对于一个有n个结点的二叉树，有n+1个空链域！可用来记录前驱、后继的信息。

比如G结点，他的前驱应该是D结点，所以可以让G的左孩子指针指向D，这样就可以通过G结点的左孩子指针来找到G结点的前驱。

后继也是类似的，B是G的后继，让G的右孩子指针指向B，这样就可以通过G结点的右孩子指针来找到G结点的后继。

比如D结点，他是第一个被访问的结点，其没有前驱，那么可以让D的左孩子指针指向NULL，表示其没有前驱。

那么右图所示的二叉树，就是中序线索二叉树。

如果一个结点的左右孩子指针指向的是前驱和后继，而不是左右孩子，那么这种类型的指针称为线索。
指向前驱的是前驱线索，指向后继的是后继线索。

那么思考这个Q：给定结点G的指针，如何找到G的后继？
A：通过后继线索来找到B。

也就意味着从某一个结点出发，继续往后遍历（不断找后继）也是可行的。

又一个Q：那么对于一个右孩子指针指向其右孩子而不是后继，那么这个结点如何找到后继呢？
A：后面会探讨这个问题

本节只需理解线索二叉树，知道建立线索的意义是什么即可

---

线索二叉树的存储结构

线索二叉树中的左右孩子指针可能指向的不是左右孩子，而是前驱和后继。
为了区别这样两种状态，就需要增加两个标志位，分别叫ltag和rtag；

当tag == 0时，表示这个指针指向孩子；
当tag == 1时，表示这个指针指向“线索”。
左孩子指针充当的线索指向的是前驱；右孩子指针充当的线索指向的是后继。

二叉树可以称为二叉链表，那么线索二叉树可以称为线索链表

中序线索二叉树的存储可以这样表示：

原理类似，那么可以引申出先序线索二叉树和后序线索二叉树。

按先序/后序序列来确定各个结点之间的前驱和后继的关系，然后把n+1个空链域变成线索。

先序线索二叉树：

先序线索二叉树的存储：

后序线索二叉树：

后序线索二叉树的存储：

三种线索二叉树的对比：

---

5.3.2_2 二叉树的线索化

——用代码实现二叉树的线索化

用土办法找到中序前驱：

对于给定结点指针p，如何找到这个结点的前驱。
对整棵二叉树重新进行一次中序遍历，用q指针指向当前访问结点，用pre指针指向当前结点的前驱结点。
找中序遍历结点前驱的代码核心就是中序遍历；只要判断当前访问结点q和要找的结点p是否是同一个结点，如果是，pre指针指向的结点即p指针指向结点的前驱结点。
因此引入全局变量final来记录找到的前驱结点，这样就找到了它的中序前驱。

该函数最好换一个名字，比如findpre，可以很好地体现该函数的作用。

那么怎么对二叉树进行线索化呢？
将该结点的左孩子指针连上前驱/右孩子指针连上后继。
可以将上述思想迁移到二叉树的线索化中。

---

中序线索化

和普通二叉树相比，多了两个标志位——左、右线索标志

此处改变了函数名，但实际上该函数的内部就是一个中序遍历

左子树，访问该结点，右子树，中序遍历。

初步建成的二叉树ltag和rtag都设置为0

pre指针用来指向当前访问结点的前驱，第一个结点D没有前驱，让pre指针指向NULL

D结点是没有左孩子的，所以应该把他的左孩子线索化，在visit函数中完成判断：

如果当前结点左孩子为空，那么把其左孩子指针lchild指向他的前驱；
然后修改ltag = 1，因为值=1的时候才表示对应的孩子指针是线索。
然后让pre指针指向当前结点。

接下来访问G结点

同样的逻辑，其左孩子指针为空，让其左指针线索化指向pre，即前驱，
同时将对应的ltag设为1；

接下来访问B结点

B结点的左右孩子指针都是非空的，但是其前驱，也就是pre指针指向的结点，此时指向的结点G右孩子指针是空的，因此要将B结点的前驱pre指针指向的G结点的右孩子指针线索化，指向他的后继，即当前访问的q指针，其指向B结点。
 
让pre的右孩子指针指向q，同时把rtag=1

最终完成线索化：

注意，当visit到第七个，也就是最后一个结点C的时候，最终还需要把pre指针指向当前这个结点C，此时出现了一个问题：
最后一个结点C的右孩子指针是空的，应该将其线索化。
此时设置的pre指针是一个全局变量，所以可以在其他的函数当中对
pre指针当前指向的结点再做处理，让其右孩子指针rchild指向NULL，表示没有后继，并将其rtag设置为1.

中序线索化的完整处理代码：

第一个被visit的结点，其没有前驱，所以pre的值初始化设置为NULL

如果二叉树非空，对其线索化，即调用函数InThread，本质也是一个中序遍历，只不过一边遍历一遍把各个结点进行线索化，具体线索化的逻辑在visit函数中进行。

在遍历处理完所有结点后，还需要处理最后一个结点，如果最后一个结点的右孩子指针是NULL，需要把rtag设置为1

中序线索二叉树：

另一版本中序线索化：

这种代码看不出与中序遍历之间的联系，是因为函数中多了一个参数pre。
此处的局部变量pre与之前方法中定义的全局变量pre的作用相同，用来记录当前被visit的根结点的前驱。
 
pre为以下函数中的局部变量：
并作为参数传入中序线索化的函数中，

Q：为什么pre参数是引用类型？
A：为了保证在中序线索化函数中对pre进行修改可以影响到原始的pre的值。

Q：处理遍历的最后一个结点时，为什么没有判断rchild是否为NULL？
A：中序遍历的最后一个结点右孩子指针必为空。

---

先序线索化

原理相同，本质上就是先序遍历，一边遍历，一边对结点进行线索化。
但是，先序线索化中会出现爱的魔力转圈圈问题：

注意一个问题：假设当前正在visit第三个结点，pre指向第二个结点，那么按照visit函数中的逻辑，应该让第三个结点的左孩子指针线索化，即指向pre，同时让pre指针指向当前访问的这个结点。
但是在代码中，当处理完第三个结点D后，接下来会处理D的左子树，但是，刚才把他的左孩子指针指向了结点B，接下来访问左子树时，会导致q指针再一次指回B。对结点的访问会开始出现无限循环！

如何处理?
当左孩子指针线索化后，还有一个ltag变量，可以通过tag变量来判断左孩子指针指向的是否是真正的左孩子指针。

增加判断条件：ltag = 0，即lchild不是前驱线索时，才对其左指针所指向的子树进行线索化。

⚠️先序线索化中的易错点：
左孩子指针一旦被线索化之后，所指向的结点就是当前访问结点的前驱结点。
如果继续按照前驱线索访问，即又回头去访问其前驱结点，就会导致重复。

先序线索化的完整处理代码：

和中序线索化一样，处理最后一个结点，右孩子指针为NULL时，那么需要把rtag设为1

另一版本中序线索化：

---

后序线索化

也是一样的，区别在于先处理左子树，再处理右子树，最后处理这个根结点。
后序线索化中不会出现先序线索化的“转圈”问题，因为当访问当前结点时，当前结点的左子树和右子树肯定已经处理完了，不会出现“回头访问左子树”的情况。

另一个版本的后序线索化：

记得处理最后一个结点！

---

5.3.2_3 在线索二叉树中找前驱后继

中序线索二叉树找中序后继

怎么找一个指定结点p的中序后继？

① 指定结点p的右孩子指针已经被线索化，其rtag == 1，那么右孩子指针就是指向其中序后继，这种情况下找后继很方便。
② 指定结点p的右孩子指针没有被线索化，其rtag == 0，那么该结点是有右孩子的，即右子树非空。
 
中序遍历的顺序应该是左根右，访问p结点后，需要中序遍历右子树：
按照中序遍历的规则，p的右子树中，第一个被中序遍历的结点就应该是p的后继。
假设p的右孩子为叶子结点，没有下一层，那么该结点就是p的后继；
假设p的右孩子为分支结点，还有下一层，那么右子树中的左下角结点就是p的后继；
假设p的右孩子为分支结点，且左下角结点也为分支结点，那么这个分支结点的左孩子结点，即最左下角的结点就是p的后继

代码实现：

从指定结点出发，如果下一层还有左孩子，那么就一直顺着左分支找到最左下角的结点，即第一个被中序遍历的结点，即当前结点的后继结点。

可以利用找后继对中序线索二叉树进行中序遍历，传入要遍历的树的根结点指针T，首先利用Firstnode函数找到在这棵树中第一个被中序遍历的结点，即从根出发最左下角的这个结点，然后访问该结点，然后用刚才定义的Nextnode函数很方便地找到这个结点的中序后继。
 
用一个for循环，就可以实现对整棵中序线索二叉树进行中序遍历。

该遍历算法不需要递归调用函数，所以空间复杂度为$O(1)$

---

中序线索二叉树找中序前驱

① 指定结点p的左孩子指针已经被线索化，其ltag == 1，那么左孩子指针就是指向其中序前驱。
② 指定结点p的左孩子指针没有被线索化，其ltag == 0，那么该结点是有左孩子的。
类似后继，最右下角的结点就是p的前驱

代码实现：

通过Lastnode函数可以找到中序遍历最后一个被访问到的结点，即最右下角的结点。

在Prenode函数中，如果p的ltag == 0即左指针没有被线索化，那么只需要找到p结点的左子树中最后一个被中序遍历的结点，即左子树中最右下角结点，该结点为p的前驱。
如果p的左指针本来就是线索的话，那么左指针指向的结点就是p的前驱。

可以利用找前驱对中序线索二叉树进行逆向的中序遍历。

---

先序线索二叉树找先序后继

思路相同

① 右指针已经被线索化，直接返回后继线索。
② 右指针没有被线索化，那么肯定有右孩子的。
由于不知道有没有左孩子，先假设！
假设有左右孩子，按照先序遍历顺序为根左右，p结点的后继结点肯定是左子树中第一个被访问的结点，即左子树的根结点，就是他的左孩子。
假设只有右孩子没有左孩子，p结点的后继结点肯定是右子树中第一个被访问的结点，即右子树的根结点，就是他的右孩子。

②中
若p有左孩子，则先序后继为左孩子
若p没有左孩子，则先序后继为右孩子

---

先序线索二叉树找先序前驱

思路类似

探讨左孩子没有被线索化的情况：
ltag == 0时，p结点肯定有左孩子，按照先序遍历中根左右的顺序，p的左子树和右子树中的所有结点都只可能是p的后继，不可能在p的左右子树中找到前驱。
线索二叉树只有指向孩子结点的指针，不可能往回找，除非从头开始遍历。

如何解决只有指向孩子结点的指针不能往回找的问题呢？

使用三叉链表！
给各个结点设置一个指向其父结点的指针。

1. 如果能找到p的父结点，且p是左孩子

按照遍历顺序 - 根左右，那么p结点肯定是在根结点 - 即其父结点之后被访问的一个结点，
那么这个父结点一定是p结点的先序前驱。

2. 如果能找到p的父结点，且p是右孩子，其左兄弟为空

按照遍历顺序 - 根右 ，那么p结点同样是在根结点 - 即其父结点之后被访问的一个结点，
那么这个父结点一定是p结点的先序前驱。

3. 如果能找到p的父结点，且p是右孩子，其左兄弟非空

按照遍历顺序 - 根左右 ，那么p结点的前驱就是在左兄弟子树中最后一个被前序遍历访问到的结点，

4. 如果p是根结点，则p没有先序前驱

以上基于改用三叉链表可以逆向找到p的父结点这个条件来讨论找先序前驱。

---

后序线索二叉树找后序前驱

思路相同

① 右指针已经被线索化，直接返回后继线索。
② 右指针没有被线索化，那么肯定有右孩子的。
由于不知道有没有右孩子，先假设！
假设有左右孩子，按照后序遍历顺序为左右根，p结点的前驱结点就是右子树中最后一个被访问的结点，也就是右孩子。
假设没有右孩子，按照左根顺序，p结点的前驱结点就是左子树中最后一个被访问的结点，也就是“左孩子”。

②中
若p有右孩子，则后序前驱为右孩子
若p没有右孩子，则后序前驱为左孩子

---

后序线索二叉树找后序后继

思路类似

探讨右孩子没有被线索化的情况：
ltag == 0时，p结点肯定有右孩子，按照后序遍历中左右根的顺序，p的左子树和右子树中的所有结点都只可能是p的前驱，不可能在p的左右子树中找到后继。
除非从头开始遍历。

使用三叉链表！
给各个结点设置一个指向其父结点的指针。

1. 如果能找到p的父结点，且p是右孩子

按照遍历顺序 - 左右根，那么无论p结点下面还有没有孩子，p结点一定是该右子树中最后一个被访问的结点，在访问完p结点之后，就会访问p结点的父结点，所以p结点的后序后继为其父结点。

2. 如果能找到p的父结点，且p是左孩子，其右兄弟为空

按照遍历顺序 - 左根 ，在访问完p结点后一定紧接着访问其父结点，
那么这个父结点一定是p结点的先序前驱。

3. 如果能找到p的父结点，且p是右孩子，其左兄弟非空

按照遍历顺序 - 左右根 ，那么p结点的后继就是在右兄弟子树中第一个被后序遍历访问到的结点

4. 如果p是根结点，则p没有后序后继

以上基于改用三叉链表可以逆向找到p的父结点这个条件来讨论找后序后继。

---

知识回顾与重要考点

5.3.1_1 二叉树的先中后序遍历

• 掌握先、中、后序遍历算法
• 掌握求遍历序列的方法

---

5.3.1_2 二叉树的层次遍历

• 二叉树的层次遍历，关键在于设置辅助队列

---

5.3.1_3 由遍历序列构造二叉树

• 最重要的是找到树的根结点，并根据中序序列划分左右子树，再找到左右子树根结点

Q：若前序、后序、层序序列两两组合？

结论：前序、后序、层序序列的两两组合无法唯一确定一棵二叉树

---

5.3.2_1 线索二叉树的概念

• 利用二叉树本身存在的n+1个空链域，将其变成线索并指向前驱、后继
• 再普通二叉树的基础上，增加ltag和rtag两个标志位，当tag值为1，指针指向“线索”，当tag值为0，指针指向孩子。
• 中序前驱/中序后继：按照中序遍历二叉树后，该结点对应的前驱/后继。其他类似。
• 以手算的方式线索化：根据遍历规则确定各个结点被访问的顺序并编号，将n+1个空链域连上前驱、后继。

---

5.3.2_2 二叉树的线索化

• 增加指针pre用来记录当前访问结点的前驱结点，可以把pre设置为全局变量
• 注意处理最后一个结点的rchild、rtag
• 注意先序线索化中，“转圈”问题，只有当ltag == 0时，才能对左子树先序线索化

---

5.3.2_3 在线索二叉树中找前驱后继

• 不需要背，理解过程，学会推算。解无定法，源于观察。
  
• 中序线索二叉树既可以找前驱也可以找后继
• 先序线索二叉树可以找后继，不能找前驱；后续线索二叉树可以找前驱，不能找后继。除非从头遍历或者用三叉链表。