本文只要是对使用两种不同的方式（递归遍历、非递归遍历）对二叉树分别进行前序遍历、中序遍历、后序遍历的记录

一、创建二叉树

创建树节点

public class Node {public int value;public Node left;public Node right;public Node(int value) {this.value = value;}
}

初始化二叉树

public class Tree {/***         17*      /     \*     4       3*    / \     / \*   7   9   11  20*  / \   \      / \* 12 13  23    27 35*/public static Node getTree() {Node tree = new Node(17);// 第一层tree.left = new Node(4);tree.right = new Node(3);// 第二层tree.left.left = new Node(7);tree.left.right = new Node(9);tree.right.left = new Node(11);tree.right.right = new Node(20);// 第三层tree.left.left.left = new Node(12);tree.left.left.right = new Node(13);tree.left.right.right = new Node(23);tree.right.right.left = new Node(27);tree.right.right.right = new Node(35);return tree;}
}

二、递归遍历

前序遍历、中序遍历、后序遍历在遍历二叉树的递归代码处理是一样的。区别只在打印数据的时刻，是第一次访问到该节点时打印数据，还是第二次，还是第三次，分别对应调用递归方法前、中、后三个位置

public class 递归遍历 {@Testpublic void preorderTraversal() {Node tree = Tree.getTree();preorder(tree);inorder(tree);postorder(tree);}public static void preorder(Node node) {if (node == null) {return;}System.out.println(node.value);preorder(node.left);preorder(node.right);}public static void inorder(Node node) {if (node == null) {return;}inorder(node.left);System.out.println(node.value);inorder(node.right);}public static void postorder(Node node) {if (node == null) {return;}postorder(node.left);postorder(node.right);System.out.println(node.value);}
}

三、非递归遍历（栈遍历）

利用栈先进后出的特点，对数据进行打印

public class 非递归遍历 {@Testpublic void preorderTraversal() {Node tree = Tree.getTree();preorder(tree);inorder(tree);postorder(tree);}/*** 使用栈：* 存放栈的顺序为 头右左* 由于头先打印了，所以还剩下右左* 又由于是栈，所以真正在打印的时候，是先判定右边（右边先压后打印），再判定左边（左边后压先打印），即完成我们的 先序遍历（头-左-右）*/private static void preorder(Node node) {if (node == null) {return;}Stack<Node> stack = new Stack<>();stack.push(node);while (!stack.isEmpty()) {Node pop = stack.pop();// 先打印头的数据System.out.println(pop.value);if (pop.right != null) {stack.push(pop.right);}if (pop.left != null) {stack.push(pop.left);}}}/*** 中序遍历 左-根-右* 将所有节点划分为一个个小单元————左节点和其父节点（右节点是另一个单元的左节点或者父节点）* 关键逻辑为：* 1.第一个弹出的节点只能是左叶子节点。* 2.在第一步的基础上第二个弹出的只能是左叶子节点回溯的上一个节点，即访问到叶子节点的父节点* 3.然后进行右节点访问，此时的右节点相当于到了另一个单元的跟节点，重复上面步骤即可* 4.从最终的结果来看，访问的顺序就是中序遍历（左-根-右，第一个单元的左-根，右第二单元的左或根）*/private void inorder(Node node) {if (node == null) {return;}Stack<Node> stack = new Stack<>();while (!stack.isEmpty() || node != null) {// 第一次进入的是根节点，后续进入的是树的左节点，将它们压入栈if (node != null) {stack.push(node);node = node.left;} else {// 打印当前节点数据，节点调整为右节点（跳转到了另一个小单元，在新的单元里该右节点以新单元里左节点或者父节点进行压栈）Node pop = stack.pop();System.out.println(pop.value);node = pop.right;}}}/*** 先序遍历（头-左-右）的技术上，我们可以构造出（头-右-左），即push顺序调整* 如果再将（头-右-左）进行翻转，就是后序遍历（左-右-头），将本该打印数据的位置，使用另一个栈进行接受完成数据的反转*/private void postorder(Node node) {if (node == null) {return;}Stack<Node> stack = new Stack<>();// 打印栈Stack<Node> printStack = new Stack<>();stack.push(node);while (!stack.isEmpty()) {Node pop = stack.pop();// 先序遍历此处为打印头，后续修改为将要打印的数据直接压入打印栈printStack.push(pop);if (pop.left != null) {stack.push(pop.left);}if (pop.right != null) {stack.push(pop.right);}}// 打印数据while (!printStack.isEmpty()) {System.out.println(printStack.pop().value);}}
}