二叉树前中后序遍历的实现（递归和非递归版）二叉树前中后序遍历的实现（

各位读者周末愉快呀，今天我想来说说一道很常见的面试题目 —— 关于二叉树前中后序遍历的实现。本文将以递归和非递归方式实现这 3 种遍历方式，代码都比较短，可以放心食用。
先简单说明一下这 3 种遍历方式有什么不同 —— 对于每种遍历，树中每个结点都需要经过 3 次（对于叶结点，其左右子树视为空子树），但前序遍历在第一次遇到结点时就立即访问，中序遍历是在第二次遇到结点时访问，后序遍历则是第三次访问。
所以前中后序遍历访问结点的顺序分别是中左右、左中右、左右中。「中」表示当前结点，「左右」表示当前结点的左右子树。
下面让我们一起来看下代码是怎么实现的吧。
递归版前序遍历

public static void preOrderRecur(Node head) { if (head == null) { return; } System.out.print(head.value + " "); preOrderRecur(head.left); preOrderRecur(head.right); }

中序遍历

public static void inOrderRecur(Node head) { if (head == null) { return; } inOrderRecur(head.left); System.out.print(head.value + " "); inOrderRecur(head.right); }

后序遍历

public static void posOrderRecur(Node head) { if (head == null) { return; } posOrderRecur(head.left); posOrderRecur(head.right); System.out.print(head.value + " "); }

非递归版前序遍历

public static void preOrderUnRecur(Node head) { if (head != null) { Stack stack = new Stack(); stack.add(head); while (!stack.isEmpty()) { head = stack.pop(); System.out.print(head.value + " "); if (head.right != null) { stack.push(head.right); } if (head.left != null) { stack.push(head.left); } } } }

中序遍历

public static void inOrderUnRecur(Node head) { if (head != null) { Stack stack = new Stack(); while (!stack.isEmpty() || head != null) { if (head != null) { stack.push(head); head = head.left; } else { head = stack.pop(); System.out.print(head.value + " "); head = head.right; } } } }

后序遍历

public static void posOrderUnRecur(Node head) { if (head != null) { Stack s1 = new Stack(); Stack s2 = new Stack(); s1.push(head); while (!s1.isEmpty()) { head = s1.pop(); s2.push(head); if (head.left != null) { s1.push(head.left); } if (head.right != null) { s1.push(head.right); } } while (!s2.isEmpty()) { System.out.print(s2.pop().value + " "); } } }

以上就是二叉树的 3 种遍历方式，你学会了吗？
【二叉树前中后序遍历的实现（递归和非递归版）】PS：本文原创发布于微信公众号「不只Java」，后台回复「Java」，送你 13 本 Java 经典电子书。公众号专注分享 Java 干货、读书笔记、成长思考。