【题目】
用递归和非递归的方式，分别按照二叉树的先序、中序和后序打印所有的节点，我们约定：先序遍历顺序为根、左、右，中序遍历的顺序为左、根、右，后序遍历顺序为左、右、根。
【解答】
package zcy;import java.sql.Statement;
import java.util.Stack;/*** 二叉树*/
public class P94_BinaryTree {public static void preOrder(Node head) {if (head == null) {return;}System.out.println(head.value);preOrder(head.left);preOrder(head.right);}/*** 用栈的方式实现先序遍历 头左右* 1、申请一个新的栈，记为stack，然后将头节点head压入stack中* 2、从stack中弹出栈顶节点，记为cur，然后打印cur的值，再将cur的右节点压入栈中，然后再将cur的左节点压入栈中* 3、不断重复步骤2，直到stack栈空为止** @param head*/public static void preOrderStack(Node head) {if (head == null) {return;}Stack<Node> s1 = new Stack<Node>();s1.add(head);while (!s1.isEmpty()) {Node cur = s1.pop();System.out.println(cur.value);if (cur.right != null) {s1.add(cur.right);}if (cur.left != null) {s1.add(cur.left);}}}public static void midOrder(Node head) {if (head == null) {return;}System.out.println(head.value);midOrder(head.left);midOrder(head.right);}/*** 用栈的方式实现中序遍历 左头右* 1、申请一个新的栈，记为stack。初始时，令变量 cur = head* 2、先把cur节点压入栈中，对以cur节点为头节点的整颗子树来说，依次把左边界压入栈中，即不停的令cur = cur.left, 然后重复步骤2* 3、不断重复步骤2，直到cur 为空，此时从栈中弹出一个节点，记为node，打印node值，并且让cur = node.right，然后重复步骤2* 4、当stack为空且cur为空时，整个过程停止** @param head*/public static void midOrderStack(Node head) {if (head == null) {return;}Stack<Node> s1 = new Stack<Node>();Node cur = head;while (!s1.isEmpty() || cur != null) {if (cur != null) {s1.add(cur);cur = cur.left;} else {cur = s1.pop();System.out.println(cur.value);cur = cur.right;}}}public static void posOrder(Node head) {if (head == null) {return;}System.out.println(head.value);posOrder(head.left);posOrder(head.right);}/*** 用栈实现后序遍历 左右头* 1、申请两个栈s1、s2，初始化将head 放入s1* 2、从s1中弹出一个节点，记为cur，先将cur 的右节点放入s1，然后将cur的左节点放入s2，并将cur放入s2中，重复步骤2* 3、当s1栈空，结束循环* 4、依次打印s2中的节点值** @param head*/public static void posOrderStack(Node head) {if (head == null) {return;}Stack<Node> s1 = new Stack<Node>();Stack<Node> s2 = new Stack<Node>();s1.add(head);while (!s1.isEmpty()) {Node cur = s1.pop();s2.push(cur);if (cur.right != null) {s1.add(cur.right);}if (cur.left != null) {s1.add(cur.left);}}while (!s2.isEmpty()) {System.out.println(s2.pop().value);}}public static class Node {public int value;public Node left;public Node right;public Node(int value) {this.value = value;}}
}