遍历二叉树

就是遍历二叉树，递归非递归
  1 package my_basic.class_4;
  2 
  3 import java.util.Stack;
  4 
  5 public class Code_01_PreInPost {
  6     // 先序 中序 后序遍历二叉树
  7     //递归 和非递归
  8     public static class Node {
  9         int value;
 10         Node parent;
 11         Node left;
 12         Node right;
 13         public Node(int value) {
 14             super();
 15             this.value = value;
 16         }
 17     }
 18 
 19     public static void preOrderRecur(Node head) {
 20         if (head == null) {
 21             return;
 22         }
 23         System.out.print(head.value + " ");
 24         preOrderRecur(head.left);
 25         preOrderRecur(head.right);
 26     }
 27 
 28     public static void inOrderRecur(Node head) {
 29         if (head == null) {
 30             return;
 31         }
 32         inOrderRecur(head.left);
 33         System.out.print(head.value + " ");
 34         inOrderRecur(head.right);
 35     }
 36 
 37     public static void postOrderRecur(Node head) {
 38         if (head == null) {
 39             return;
 40         }
 41         postOrderRecur(head.left);
 42         postOrderRecur(head.right);
 43         System.out.print(head.value + " ");
 44     }
 45     //中左右
 46     public static void preOrderUnRecur(Node head) {
 47         Stack<Node> stack = new Stack<Node>();
 48         stack.add(head);
 49         while (!stack.isEmpty()) {
 50             head = stack.pop();
 51             System.out.print(head.value+" ");
 52             if (head.right!=null) {
 53                 stack.add(head.right);
 54             }
 55             if (head.left!=null) {
 56                 stack.add(head.left);
 57             }
 58         }
 59     }
 60     //左中右
 61     public static void inOrderUnRecur(Node head) {
 62         Stack<Node> stack = new Stack<Node>();
 63         while(!stack.isEmpty() || head!=null) {
 64             if (head != null) {
 65                 stack.add(head);
 66                 head = head.left;
 67             }else {
 68                 head = stack.pop();
 69                 System.out.print(head.value+" ");
 70                 head = head.right;
 71             }
 72         }
 73     }
 74     //左右中  在先序 中左右 的基础上，改成中右左，然后不输出而是放到另一个栈中
 75     public static void postOrderUnRecur(Node head) {
 76         Stack<Node> stack1 = new Stack<Node>();
 77         Stack<Node> stack2 = new Stack<Node>();
 78         stack1.add(head);
 79         while (!stack1.isEmpty()) {
 80             head = stack1.pop();
 81 //            System.out.print(head.value+" ");
 82             stack2.add(head);
 83             if (head.left!=null) {
 84                 stack1.add(head.left);
 85             }
 86             if (head.right!=null) {
 87                 stack1.add(head.right);
 88             }
 89         }
 90         while (!stack2.isEmpty()) {
 91             System.out.print(stack2.pop().value+" ");
 92         }
 93     }
 94 
 95     public static void main(String[] args) {
 96         Node head = new Node(5);
 97         head.left = new Node(3);
 98         head.right = new Node(8);
 99         head.left.left = new Node(2);
100         head.left.right = new Node(4);
101         head.left.left.left = new Node(1);
102         head.right.left = new Node(7);
103         head.right.left.left = new Node(6);
104         head.right.right = new Node(10);
105         head.right.right.left = new Node(9);
106         head.right.right.right = new Node(11);
107 
108         // recursive
109         System.out.println("==============recursive==============");
110         System.out.print("pre-order: ");
111         preOrderRecur(head);
112         System.out.println();
113         System.out.print("in-order: ");
114         inOrderRecur(head);
115         System.out.println();
116         System.out.print("pos-order: ");
117         postOrderRecur(head);
118         System.out.println();
119         System.out.println("==============unrecursive==============");
120         System.out.print("pre-order: ");
121         preOrderUnRecur(head);
122         System.out.println();
123         System.out.print("in-order: ");
124         inOrderUnRecur(head);
125         System.out.println();
126         System.out.print("pos-order: ");
127         postOrderUnRecur(head);
128         
129 
130     }
131 
132 }