数据结构：二叉树的遍历

相比线性数据类型，树本身是一种递归结构，因此可以有多种方式遍历。
树之节点的遍历可以分为三个步骤

对当前节点进行操作（访问）
去往左子节点遍历
去往右子节点遍历

二叉树的遍历一般可以分为深度优先遍历和广度优先遍历。

1. 深度优先遍历

深度优先遍历由上述三个步骤的先后顺序不同又可以分为：前序、中序、后序遍历

• 前序遍历：根节点访问——去左子节点——去右子节点
• 中序遍历：去左子节点——根节点访问——去右子节点
• 后序遍历：去左子节点——去右子节点——根节点访问

其实可以看成，是以根节点的位置命名的前、中、后序遍历。

前序遍历

中序遍历

后序遍历

其中黑点代表在此访问该节点

2. 广度优先遍历（按层次遍历）

参考：
https://zh.wikipedia.org/wiki/%E6%A0%91%E7%9A%84%E9%81%8D%E5%8E%86
https://blog.csdn.net/My_Jobs/article/details/43451187_