对于一种数据结构而言遍历是瑺见操作。二叉树是一种基本的数据结构是一种每个节点的儿子数目都不多于2的树。二叉树的节点声明如下：

二叉树的遍历主要有先序遍历中序遍历，后序遍历层序遍历四种方式，下面一一介绍

后序遍历与中序遍历，先序遍历的路径也完全一样主要的不同点是后序遍历访问节点的顺序是先访问左儿子和右儿子，最后访问节点即左儿子-右儿子-根节点。

递归实现思路与中序遍历和先序遍历相似代碼如下:

对于一个节点而言，要实现访问顺序为左儿子-右儿子-根节点可以利用后进先出的栈，在节点不为空的前提下依次将根节点，右兒子左儿子压栈。故我们需要按照根节点-右儿子-左儿子的顺序遍历树而我们已经知道先序遍历的顺序是根节点-左儿子-右儿子，故只需將先序遍历的左右调换并把访问方式打印改为压入另一个栈即可最后一起打印栈中的元素。代码如下：

思路一的优点是由于利用了先序遍历的思想代码较简洁，思路较清晰缺点是需要用一个栈来存储树的所有节点，空间占用较大

要访问一个节点的条件上一个访问的節点是右儿子。我们可以增加一个变量Prev来判断当前节点Curr的上一个节点与它的关系来执行相应的操作

若Prev为空(Curr节点是根节点)或者Prev是Curr的父节点，将Curr节点的左孩子和右孩子分别压入栈；

若Prev是Curr的左儿子则将Curr的右儿子压入栈；

二叉树遍历的核心问题是二维结构的线性化。我们通过节點访问其左右儿子时存在的问题是访问左儿子后，右儿子怎么访问因此我们需要一个存储结构保存暂时不访问的节点。前面三种遍历方式的非递归实现我们是通过堆栈来保存。事实上也可以通过队列来保存

队列实现的基本思路：遍历从根节点开始，首先将根节点入隊然后执行循环：节点出队，访问（访问）根节点将左儿子入队，将右儿子入队直到队列为空停止。

这种遍历方式的结果是将二叉樹从上到下从左至右一层一层的遍历，即层序遍历代码实现如下: