二叉树三种遍历（递归与非递归）C++实现

众所周知，二叉树的遍历有三种：前序遍历、中序遍历和后序遍历。三者不同之处是访问节点的先后次序（注意该先后次序是指节点、节点左子树、节点右子树，这三部分的顺序而非每一个节点的顺序，这三部分内部的遍历顺序与外部保持一致）。三种遍历的实现依靠递归或者非递归两种。

所以，前中后三种遍历是指节点相对于其左孩子和右孩子的位置。

如下图一个满的完全二叉树

遍历时，遇空则返回上一级，使用下图更直接些。

因为4/5/6/7四个节点的左右孩子为空，所以到达空节点后会返回节点，拿节点4为例：

4的树遍历完后返回到2的位置，开始进行2的右孩子的遍历。其他节点同理。 遍历的实际过程为：124442555213666377731 神奇的事情发生了！

观察代码你会发现，三种遍历方法的不同之处就是打印操作出现的时间！ 4. 先序遍历（中左右）：打印放前 → \rightarrow →递归左子树 → \rightarrow →递归右子树 5. 中序遍历（左中右）：递归左子树 → \rightarrow →打印放中 → \rightarrow →递归右子树 6. 后序遍历（左右中）：递归左子树 → \rightarrow →递归右子树 → \rightarrow →打印放后 所以，递归对于二叉树是好用的，他可以实访问一个节点三次。

用非递归实现二叉树时，要借用堆（stack）这个数据结构。因为递归的实质就是系统压栈出栈的过程，不使用递归则要申请一个额外的空间使用栈来实现二叉树的遍历（用队列好像也可以）。强烈建议自己动手画一遍过程！！！

使用一个栈stack。 先将头结点压入，再在栈不为空的前提下循环： 1.弹出栈顶元素 2.判断该节点右孩子不为空，压入该右孩子 3.判断该节点左孩子不为空，压入该左孩子（此时该值为栈顶元素），循环1的操作 故，第一步把头结点弹出，然后先压右再压左，弹出的顺序便是先弹左再弹右，符合中左右的顺序。

使用一个栈。 在该节点不为空或栈不为空的前提下循环： 1.节点不为空，将该节点与其左边界（左孩子的左孩子的左…）全部顺次压入栈中，直至为空。 2.节点为空，则将栈顶元素（左边界值）弹出（此时栈顶是其父节点），移至右孩子，判空后执行响应操作。

使用两个栈。（也可以使用一个栈） 一个栈temp用来临时存放，另一个栈用来弹出遍历结果。 先将头结点压入temp中： 1.栈temp不空，则把栈顶元素弹出当做当前节点，并压入另一个栈中，若该节点左右节点为空，则一直进行栈顶元素的弹出和压入,否则先压其左孩子再压其右孩子，直至栈空为止。 2.当要弹出遍历结果的栈不空时，一次弹出栈顶元素即为遍历结果。 一开始就把头结点压入了栈中，在temp中先压左再压右的目的就是弹出给stackpull中是以先右后左的顺序。这样就做到了弹出时按照左右中的顺序。