二叉树遍历递归与非递归（java)

</pre><pre name="code" class="html"> import java.util.Stack; public class 二叉树各种遍历 { public static void main(String[] args) { TreeNode one = new TreeNode(1); TreeNode two = new TreeNode(2); TreeNode three = new TreeNode(3); TreeNode four = new TreeNode(4); TreeNode five = new TreeNode(5); TreeNode six = new TreeNode(6); TreeNode seven = new TreeNode(7); TreeNode eight = new TreeNode(8); one.left = two; one.right = three; two.left = four; two.right = five; three.left = six; three.right = seven; four.left = eight; System.out.print("前序 递归："); preOrder(one); System.out.println(); System.out.print("中序 递归："); inOrder(one); System.out.println(); System.out.print("后序 递归："); postOrder(one); System.out.println(); System.out.print("前序非递归："); preOrder1(one); System.out.println(); System.out.print("中序非递归："); inOrder1(one); System.out.println(); System.out.print("后序非递归："); postOrder1(one); } // 前序遍历 public static void preOrder(TreeNode pRoot) { if (pRoot == null) return; System.out.print(pRoot.val + " "); if (pRoot.left != null) preOrder(pRoot.left); if (pRoot.right != null) preOrder(pRoot.right); } // 中序遍历 public static void inOrder(TreeNode pRoot) { if (pRoot == null) return; if (pRoot.left != null) inOrder(pRoot.left); System.out.print(pRoot.val + " "); if (pRoot.right != null) inOrder(pRoot.right); } // 后序遍历 public static void postOrder(TreeNode pRoot) { if (pRoot == null) return; if (pRoot.left != null) postOrder(pRoot.left); if (pRoot.right != null) postOrder(pRoot.right); System.out.print(pRoot.val + " "); } public static void preOrder1(TreeNode pRoot) { if (pRoot == null) return; Stack<TreeNode> stack = new Stack<>(); stack.push(pRoot); while (!stack.isEmpty()) { TreeNode tempNode = stack.pop(); System.out.print(tempNode.val + " "); if (tempNode.right != null) stack.push(tempNode.right); if (tempNode.left != null) stack.push(tempNode.left); } } public static void inOrder1(TreeNode pRoot) { if (pRoot == null) return; Stack<TreeNode> stack = new Stack<>(); TreeNode temp = pRoot; while (!stack.isEmpty() || temp != null) { if (temp != null) { stack.push(temp); temp = temp.left; } else { temp = stack.pop(); System.out.print(temp.val + " "); temp = temp.right; } } } public static void postOrder1(TreeNode pRoot) { if (pRoot == null) return; Stack<TreeNode> stack = new Stack<>(); Stack<TreeNode> output = new Stack<>(); TreeNode temp = pRoot; while (!stack.isEmpty() || temp != null) { if (temp != null) { stack.push(temp); output.push(temp); temp = temp.right; } else { temp = stack.pop(); temp = temp.left; } } while (!output.isEmpty()) { temp = output.pop(); System.out.print(temp.val + " "); } } }