算法：二叉树的遍历

一、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???????

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