引入
这节课是二叉树的考试重点,通过什么样的方式遍历二叉树,这里需要把内容搞清楚,不要混淆。
二叉树遍历
二叉树遍历(traversing binary tree),指的是
- 从根结点出发,按
照某种次序
依次访问
二叉树中的所有结点- 使得每个结点都被访问一次,且
仅有一次
。
二叉树跟线性结构的不同
线性结构的便利,最多是
- 顺序
- 循环
- 双向
- 都是简单的遍历方式
树就不一样了
- 树的结点之间不存在唯一的前驱和后继这样的关系
- 一个结点后面会跟着左子树和右子树两个结点,不是唯一的
- 所以下一个结点的选择是不同的
二叉树的遍历方式
如果都是从左到右的话,遍历方式分为 4 种
- 前序遍历
- 中序遍历
- 后序遍历
- 层序遍历
前序遍历
如果二叉树为空,则返回,否则
- 先访问根节点
- 然后前序遍历左子树
- 接着前序遍历右子树
遍历的技巧
- 每个结点都看成一个根
- 按照根、左子树、右子树顺序输出
- 然后返回上一层
- 再进行根、左子树、右子树的顺序输出
上面的答案是
ABDHIEJCFKG
超详细解题思路
- A 是 ABC 的根,输出 A,走向左子树 B
- B 是 BDE 的根,输出 B,走向左子树 D
- D 是 DHI 的跟,输出 D,走向左子树 H
- H 本身就是根,没有左右子树
- DHI 的根和左子树输出完了,接着输出右子树 I
- I 本身就是根,没有左右子树
- DHI 的根和左右子树都输出完了,接着输出 BDE
- BDE 的根 B 输出了、D 左子树也输出了,所以输出右子树 E
- E 是 EJ 的根,输出 E,走向左子树,结果没有,走向右子树 J
- J 本身就是根,没有左右子树
- BDE 全部输出完了,ABC 已经输出了根 A,左子树 B,开始输出右子树 C
- C 是 CFG 的根,输出 C,走向左子树 F
- F 是 FK 的根,输出 F,走向左子树,结果没有,走向右子树 K
- K 本身就是跟,没有左右子树
- FK 都输出完了,CFG 的 C 根已经输出了,F 左子树也输出了,开始输出 G
- G 本身就是根,没有左右子树
- 全部输出完毕
- 答案是 ABDHIEJCFKG
中序遍历
如果二叉树为空,则返回,否则
- 从根结点开始,并不是输出根节点,而是从根结点开始,根据一下规则
- 先中序遍历左子树
- 接着访问根节点
- 最后中序遍历右子树
遍历的技巧
- 每个结点都看成一个根
- 先放问左子树,如果坐子树还有左子树
- 那就把它当成根,继续向下
- 按照左子树、根、右子树顺序遍历
上面的答案是
HDIBEJAFKCG
超详细解答
- B 是 ABC 的左子树, 访问 B
- D 是 BDE 的左子树,访问 D
- H 是 DHI 的左子树,本身就是根,直接输出 H,然后访问根 D
- D 是 DHI 的根,已经输出了左子树 H,接着输出根 D,然后访问右子树 I
- I 是 DHI 的右子树,本身就是根,直接输出 I,然后 BDE 的左子树和根都输出了
- E 是 BDE 的右子树,E 是 EJ 的根,EJ 没有左子树,输出 EJ 的根 E
- J 是 EJ 的右子树,左子树没有,根已经输出了,输出右子树 J
- A 是 ABC 的根,左子树 B 已经全部输出,接着输出根 A,访问右子树 C
- F 是 CFG 的左子树,F 是 FK 的根
- F 是 FK 的跟,FK 没有左子树,输出根 F
- K 是 FK 的右子树,FK 没有左子树,根已经输出,输出右子树 K
- C 是 CFG 的根,左子树 F 已经全部输出,输出根 C
- G 是 CFG 的右子树,本身就是根,没有左右子树,直接输出
- 全部输出完毕
- 答案是 HDIBEJAFKCG
1秒解题小技巧
想想一根垂直的线在树的左侧
从左向右扫描,扫到谁就输出谁
后序遍历
如果二叉树为空,则返回,否则
- 从左到右,先叶子后结点
- 遍历左右子树
- 最后访问根节点
上面的答案是
HIDJEBKFGCA
超详细解答
- 先找到最左侧的叶子 H 输出
- H 是 DHI 的左子树,接着输出右子树 I
- D 是 DHI 的根,左子树、右子树都输出了,接着输出根 D
- D 是 BDE 的左子树,接着找到 E,E 是结点,向下找
- J 是 EJ 的根,EJ 没有左子树,所以输出右子树 J
- E 是 EJ 的根,EJ 没有左子树,右子树 J 已经输出,现在输出根 E
- B 是 BED 的根,D左子树 和 E右子树都已经输出,现在输出根 B
- C 是 ABC 的右子树,右子树 C 是 CFG 的根,左子树是 F
- F 是 FK 的根,FK 没有左子树,输出右子树 K
- F 是 FK 的跟,FK 没有左子树,右子树 K 已经 输出,现在输出根 F
- F 是 CFG 的左子树,开始输出右子树 G
- G 本身就是根,没有左右子树,直接输出 G
- C 是 CFG 的根,左子树 F 已经输出,G 右子树也已经输出,现在输出 C
- A 是 ABC 的根,左子树 B 和右子树 C 都已经输出,现在开始输出根 A
- 全部输出完毕
- 答案是 HIDJEBKFGCA
层序便利
如果二叉树为空,则返回,否则
- 从第一层,也就是树的根节点开始
- 从上到下,从左到右
- 按照顺序对结点进行访问
上面的答案是
ABCDEFGHIJK
这个不用讲了,最简单了!
总结
- 前序:根左右
- 中序:左根有
- 后续:左右根
就是根在不同的位置,进行不同的遍历。
遍历的不同方式决定你如何使用树中的各个结点,我们下节课再见。
尾巴
这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。