数据结构之树-超详细二叉树的遍历(一)-学习笔记-54

引入

这节课是二叉树的考试重点,通过什么样的方式遍历二叉树,这里需要把内容搞清楚,不要混淆。

二叉树遍历

二叉树遍历(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

这个不用讲了,最简单了!

总结

  • 前序:根左右
  • 中序:左根有
  • 后续:左右根

就是根在不同的位置,进行不同的遍历。
遍历的不同方式决定你如何使用树中的各个结点,我们下节课再见。

尾巴

这是我的个人学习笔记,主要是应付考研复习使用,充斥着一些吐槽和个人观点,并不严谨,欢迎大家参考、指正。


-------------The End-------------
欢迎请我喝咖啡哦~!