算法：二叉树的遍历

一、3+1种遍历方法

(1)先序法（又称先根法）
先序遍历：根，左子树，右子树
遍历的结果：A，B，C
遍历的足迹：沿途经过各结点的“左部”

(2)中序法（又称中根法）
中序遍历：左子树，根，右子树
遍历的结果：B，A，C
遍历的足迹：沿途经过各结点的“下部”

(3)后序法（又称后根法）
后序遍历：左子树，右子树，根
遍历的结果：B，C，A
遍历的足迹：沿途经过各结点的“右部”

(4)层次法
层次遍历：从根开始，层次自上到下，同层结点自左至右进行。
遍历的结果：A，B，C
遍历的足迹：第一层A，第二层B，C

二、口诀

先序遍历： 先根 再左 再右

中序遍历： 先左 再根 再右

后序遍历： 先左 再右 再根

三、图片展示

先序遍历结果：A B D H I E J C F K G

先序遍历可以想象为，一个小人从一棵二叉树根节点为起点，沿着二叉树外沿，逆时针走一圈回到根节点，路上遇到的元素顺序，就是先序遍历的结果。

中序遍历结果：H D I B E J A F K C G

中序遍历就是从最左边开始，把每个节点垂直投影到同一直线上，然后从左往右读值就可以了。

后序遍历结果：H I D J E B K F G C A

就是围着树的外围绕一圈，如果发现一剪刀就能剪下的葡萄（必须是一颗葡萄）（也就是葡萄要一个一个掉下来，不能一口气掉超过1个这样），就把它剪下来，组成的就是后序遍历了。

层次遍历结果：A B C D E F G H I J K​​​​​​​

层次遍历很好理解，就是从根节点开始，一层一层，从上到下，每层从左到右，依次写值就可以了。