1 package tree;
2
3 import java.util.Stack;
4
5 public class VisitTree {
6
7 public static void main(String[] args) {
8 // TODO Auto-generated method stub
9 TreeNode t = new TreeNode(5);
10 t.left = new TreeNode(3);
11 t.right = new TreeNode(7);
12 t.left.left = new TreeNode(1);
13 t.left.right = new TreeNode(4);
14 t.right.left = new TreeNode(6);
15 t.right.right = new TreeNode(8);
16
17 // TreeNode t = null;
18
19 preOrderR(t);
20 System.out.println();
21 inOrderR(t);
22 System.out.println();
23 posOrderR(t);
24 System.out.println();
25 preOrder(t);
26 System.out.println();
27 inOrder(t);
28 System.out.println();
29 posOrder(t);
30 }
31
32
33 public static void posOrder(TreeNode root) {
34 if(root == null) return;
35 Stack<TreeNode> s = new Stack<>();
36 s.push(root);
37 TreeNode cur, pre = null;
38
39 while(!s.isEmpty()){
40 cur = s.peek();
41 if(cur.left == null && cur.right == null || (pre != null && (pre == cur.left || pre == cur.right))) {
42 System.out.print(cur.val + " ");
43 pre = s.pop();
44 }else {
45 if(cur.right != null) s.push(cur.right);
46 if(cur.left != null) s.push(cur.left);
47 }
48 }
49
50 }
51
52 public static void inOrder(TreeNode root) {
53 Stack<TreeNode> s = new Stack<>();
54 TreeNode node = root;
55
56 while(node != null || !s.isEmpty()) {
57 if(node != null) {
58 s.push(node);
59 node = node.left;
60 }else {
61 node = s.pop();
62 System.out.print(node.val + " ");
63 node = node.right;
64 }
65 }
66 }
67
68 public static void preOrder(TreeNode root) {
69 Stack<TreeNode> s = new Stack<>();
70 TreeNode node = root;
71
72 while(node != null || !s.isEmpty()) {
73 if(node != null) {
74 System.out.print(node.val + " ");
75 s.push(node);
76 node = node.left;
77 }else {
78 node = s.pop();
79 node = node.right;
80 }
81 }
82 }
83
84
85
86 public static void preOrderR(TreeNode root) {
87 if(root == null) return ;
88 System.out.print(root.val + " ");
89 preOrderR(root.left);
90 preOrderR(root.right);
91 }
92
93 public static void inOrderR(TreeNode root) {
94 if(root == null) return ;
95
96 inOrderR(root.left);
97 System.out.print(root.val + " ");
98 inOrderR(root.right);
99 }
100
101 public static void posOrderR(TreeNode root) {
102 if(root == null) return ;
103
104 posOrderR(root.left);
105
106 posOrderR(root.right);
107 System.out.print(root.val + " ");
108 }
109
110 }
