目录 前言 层序遍历 前中后序遍历(递归) 前序递归中序递归后序递归 非递归前序 法一(技巧)法二(传统) 非递归中序 非递归后序※ 法1(传统方法)法2(双栈)： 总结
前言 前面介绍了二叉排序树的构造和基本方法的实现。但是排序遍历也是比较重要的一环。所以笔者将前中后序.和层序遍历梳理一遍。了解树的遍历，需要具有的只是储备有队列，递归，和栈。这里笔者都有进行过详细介绍，可以关注笔者数据结构与算法专栏。持续分享，共同学习。 层序遍历
层序遍历。听名字也知道是按层遍历。我们知道一个节点有左右节点。而每一层一层的遍历都和左右节点有着很大的关系。也就是我们选用的数据结构不能一股脑的往一个方向钻，而左右应该均衡考虑。这样我们就选用队列来实现。
实现的代码也很容易理解：
public void cengxu(node t) {//层序遍历Queue<node> q1 = new ArrayDeque<node>();if (t == null)return;if (t != null) {q1.add(t);}while (!q1.isEmpty()) {node t1 = q1.poll();if (t1.left != null)q1.add(t1.left);if (t1.right != null)q1.add(t1.right);System.out.print(t1.value + " ");}System.out.println();} 前中后序遍历(递归)其实这种就是一个类似dfs的思想。用递归实现。前面有很详细的介绍递归算法。我们采用的三序遍历是采用同一个递归。并且大家也都直到递归是一个有来有回的过程。三序遍历只是利用了递归中的来回过程中不同片段截取输出，而达到前(中、后序遍历的结果)。
前序递归前序的规则就是根结点 ---> 左子树 ---> 右子树.我们在调用递归前进行节点操作。对于前序，就是先访问(输出)该节点。而递归左，递归右侧，会优先递归左侧。直到没有左节点。才会停止。访问次序大致为：
有了前序的经验，我们就很好利用递归实现中序遍历。中序遍历的规则是：左子树---> 根结点 ---> 右子树。所以我们访问节点的顺序需要变。
我们直到递归是来回的过程，对于恰好有两个子节点(子节点无节点)的节点来说。只需要访问一次左节点，访问根，访问右节点。即可。而如果两侧有节点来说。每个节点都要满足中序遍历的规则。我们从根先访问左节点。到了左节点这儿左节点又变成一颗子树，也要满足中序遍历要求。所以就要先访问左节点的左节点(如果存在)。那么如果你这样想，规则虽然懂了。但是也太复杂了。那么我们借助递归。因为它的子问题和根节点的问题一致，只是范围减小了。所以我们使用递归思想来解决。那么递归的逻辑为：考虑特殊情况(特殊就直接访问)不进行递归否则递归的访问左子树(让左子树执行相同函数，特殊就停止递归输出，不特殊就一直找下去直到最左侧节点。)——>输出该节点—>递归的访问右子树.代码为：
public void zhongxu(node t)// 中序遍历 中序遍历：左子树---> 根结点 ---> 右子树{if (t != null) {zhongxu(t.left);System.out.print(t.value + " ");// 访问完左节点访问当前节点zhongxu(t.right);}} 后序递归同理，有了前面的分析，后续就是左子树 ---> 右子树 ---> 根结点
public void houxu(node t)// 后序遍历 后序遍历：左子树 ---> 右子树 ---> 根结点{if (t != null) {houxu(t.left);houxu(t.right);System.out.print(t.value + " "); // 访问玩左右访问当前节点}} 非递归前序 法一(技巧) 非递归的前序。我们利用栈的性质替代递归，因为递归有时候在效率方面不是令人满意的。利用栈，我们直到栈的顺序为现金先出。那么顺序如何添加？递归是左递归，右递归。但是利用栈要相反，因为如果左进栈、右进栈会出现以下后果：
所以，我们要利用递归的思路，需要先放右节点进栈，再放左节点进栈，这个下次·再取节点取到左节点·，这个节点再右节点进栈，左节点进栈。然后循环一直到最后会一直优先取到左节点。达到和递归顺序相仿效果。
每pop完添加右左节点直接输出(访问)即可完成前序非递归遍历。 public void qianxu3(node t)// 非递归前序 栈 先左后右 t一般为root{Stack<node> q1 = new Stack<node>();if (t == null)return;if (t != null) {q1.push(t);}while (!q1.empty()) {node t1 = q1.pop();if (t1.right != null) {q1.push(t1.right);}if (t1.left != null) {q1.push(t1.left);}System.out.print(t1.value + " ");}} 法二(传统)
方法二和非递归中序遍历的方法类似，只不过需要修改输出时间，在进栈时候输入访问节点即可。具体参考中序遍历分析。
public void qianxu2(node t) {Stack<node> q1 = new Stack();while(!q1.isEmpty()||t!=null){if (t!=null) {System.out.print(t.value+" ");q1.push(t);t=t.left;}else {t=q1.pop();t=t.right;}}} 非递归中序非递归中序和前序有所区别。
我们直到中序排列的顺序是：左节点，根节点，右节点。那么我们在经过根节点的前面节点 不能释放， 因为后面还需要用到它。所以要用栈先储存。
它的规则大致为：
可行性分析：中序是左—中—右的顺序。访问完左侧。当抛出当前点的时候说明左侧已经访问完(或者自己就是左侧)，那么需要首先访问当前点的右侧。那么这个右节点把它当成根节点重复相同操作（因为右节点要满足先左再右的顺序）。这样其实就是模拟了一个递归的过程，需要自己思考。
实现代码1：
实现代码2：(个人首次写的)
public void zhongxu3(node t)// 先储藏所有左侧点，抛出一个点，访问该点右节点，对右节点在储存所有子左节点{Stack<node> q1 = new Stack();if (t == null)return;if (t != null) {q1.push(t);}node t1 = q1.peek();// 不能抛出，要先存最左侧while (t1.left != null) {t1 = t1.left;q1.push(t1);}while (!q1.isEmpty()) {node t2 = q1.pop();System.out.print(t2.value + " ");if (t2.right != null) {t2 = t2.right;q1.push(t2);while (t2.left != null) {t2 = t2.left;q1.push(t2);}}}} 非递归后序※非递归后序遍历有两种方法
一种方法是利用和前面中序、前序第二种方法类似的方法进入压栈出栈，但是要借助额外的标记次数，一个节点访问第二次才能输出。(这个访问第一次是入栈，第二次是子树解决完毕自己即将出栈（先不出栈）)。
在前面的前序和中序先到最左侧压入栈的时候，两种顺序依次是
前序: 中入栈——>左入栈——>左出栈——>中出栈——>右入栈——>右孩子入出——>右出栈 在入栈时候操作即可前序中序: 中入栈——>左入栈——>左出栈——>中出栈——>右入栈 ——>右孩子入出——>右出栈 按照出栈顺序即可完成中序而在后序遍历中：它有这样的规则：
入栈，第一次访问即将出栈。第二次访问，如果有右孩子，先不出栈把右孩子压入栈第一次访问，如果没右孩子。访问从栈中弹出。循环重复，直到栈为空
实现代码为(用map记录节点出现次数)：
另一种方法是借助双栈进行处理。我们曾在前序方法一借助一个栈右压，左压。持续让达到一个前序遍历的效果。但是这个方法很难实现后续。
分析相同方法，如果我们先压左，再压右，那么我们获得的顺序将是和前序完全相反的顺序（顺序为：中间，右侧，左侧。倒过来刚好是左侧、右侧、中间的后续）对称看起来的前序。即用另一个栈将序列进行反转顺序！如果再这个过程，我们利用另一个栈进行储存，将它的首次入栈用一个栈存入，相当于起到一个反转的作用。
实现代码为： public void houxu3(node t)// q1和q2 q1要先右后左，先遍历右侧，q1先装右侧就把右侧放到前面，左侧放在上面（栈顶）{Stack<node> q1 = new Stack();Stack<node> q2 = new Stack();if (t == null)return;if (t != null) {q1.push(t);}while (!q1.isEmpty()) {node t1 = q1.pop();q2.push(t1);if (t1.left != null) {q1.push(t1.left);}if (t1.right != null) {q1.push(t1.right);}}while (!q2.isEmpty()) {node t1 = q2.pop();System.out.print(t1.value + " ");}} 总结
测试结果：
这部分内容比较多，也可能比较杂，希望大家好好吸收，也可能笔者写的大意或者错误。还请大佬指正。！