二叉树前序，中序，后序递归和非递归实现

TreeNode定义

 1 public class TreeNode {
 2     public TreeNode left;
 3     public TreeNode right;
 4     public int val;
 5     
 6     public TreeNode(int val) {
 7         this.val = val;
 8     }
 9     
10     /**
11      * 搞一棵二叉树出来
12      *                     1
13      *                    /  
14      *                   2    3
15      *                   / 
16      *                  4 5  6
17      * @return
18      */
19     public static TreeNode createTree(){
20         TreeNode root = new TreeNode(1);
21         TreeNode node1 = new TreeNode(2);
22         TreeNode node2 = new TreeNode(3);
23         TreeNode node3 = new TreeNode(4);
24         TreeNode node4 = new TreeNode(5);
25         TreeNode node5 = new TreeNode(6);
26         
27         root.left = node1;
28         root.right = node2;
29         
30         node1.right = node3;
31         node2.left = node4;
32         node2.right = node5;
33         
34         return root;
35     }
36 }

---------------------------------------------我是分割线，前序遍历---------------------------------------

 1 /**
 2  * 前序遍历非递归实现
 3  * @author GXF
 4  *
 5  */
 6 public class PreOrderTreeByNoRec {
 7 
 8     public static void main(String[] args) {
 9         PreOrderTreeByNoRec preOrderTreeByNoRec = new PreOrderTreeByNoRec();
10         TreeNode root = TreeNode.createTree();
11         preOrderTreeByNoRec.preOrderByRecursive(root);
12         System.out.println();
13         preOrderTreeByNoRec.preOrderByNoRec(root);
14 
15     }
16     
17     /**
18      * 前序遍历二叉树,非递归实现
19      * @param root
20      */
21     public void preOrderByNoRec(TreeNode root){
22         if(root == null)
23             return;
24         Stack<TreeNode> stack = new Stack<TreeNode>();
25         System.out.print(root.val + " ");
26         stack.push(root);
27         
28         TreeNode curPoint = root.left;
29         
30         while(!stack.isEmpty() || curPoint != null){
31             if(curPoint != null){
32                 System.out.print(curPoint.val + " ");
33                 stack.push(curPoint);
34                 curPoint = curPoint.left;
35             }//if
36             
37             curPoint = stack.pop().right;
38         }
39         
40         System.out.println();
41         
42     }
43     
44     /**
45      * 前序遍历递归实现
46      * @param root
47      */
48     public void preOrderByRecursive(TreeNode root){
49         if(root != null){
50             System.out.print(root.val + " ");
51             preOrderByRecursive(root.left);
52             preOrderByRecursive(root.right);
53         }
54         
55     
56     }
57     
58     
59 
60 }

---------------------------------------------我是分割线，中序遍历---------------------------------------

 1 import java.util.Stack;
 2 
 3 /**
 4  * 中序遍历的非递归实现
 5  * @author GXF
 6  *
 7  */
 8 public class InorderTreeByNoRecursive {
 9 
10     public static void main(String[] args) {
11         InorderTreeByNoRecursive inorderTreeByNoRecursive = new InorderTreeByNoRecursive();
12         TreeNode root = TreeNode.createTree();
13         
14         inorderTreeByNoRecursive.inorderByRecursive(root);
15         System.out.println();
16         inorderTreeByNoRecursive.inorderByNoRecursive(root);
17     }
18     
19     /**
20      * 中序遍历递归实现
21      */
22     public void inorderByRecursive(TreeNode root){
23         if(root != null){
24             inorderByRecursive(root.left);
25             System.out.print(root.val + " ");
26             inorderByRecursive(root.right);
27         }
28     }
29     
30     /**
31      * 中序遍历非递归实现
32      * @param root
33      */
34     public void inorderByNoRecursive(TreeNode root){
35         if(root == null)
36             return;
37         Stack<TreeNode> stack = new Stack<TreeNode>();
38         stack.push(root);
39         TreeNode curPoint = root.left;
40         //开始中序遍历
41         while(curPoint != null || !stack.isEmpty()){
42             while(curPoint != null){
43                 stack.push(curPoint);
44                 curPoint = curPoint.left;
45             }//while
46             
47             //访问根结点
48             curPoint = stack.pop();
49             System.out.print(curPoint.val + " ");
50             curPoint = curPoint.right;
51         }
52     }
53 
54 }

---------------------------------------------我是分割线，后序遍历---------------------------------------

 1 import java.util.HashMap;
 2 import java.util.Map;
 3 import java.util.Stack;
 4 
 5 public class PostorderNoRecurvise {
 6 
 7     public static void main(String[] args) {
 8         TreeNode root = TreeNode.createTree();
 9         
10         PostorderNoRecurvise postorderNoRecurvise = new PostorderNoRecurvise();
11         postorderNoRecurvise.postorderByRecursive(root);
12         System.out.println();
13         postorderNoRecurvise.postorderByNoRecurvise(root);
14     }
15     
16     /**
17      * 递归进行后序遍历
18      * @param root
19      */
20     public void postorderByRecursive(TreeNode root){
21         if(root != null){
22             postorderByRecursive(root.left);
23             postorderByRecursive(root.right);
24             System.out.print(root.val + " ");
25         }
26     }
27     
28     /**
29      * 后序遍历非递归实现
30      * @param root
31      */
32     public void postorderByNoRecurvise(TreeNode root){
33         if(root == null)
34             return;
35         //记录结点是否被访问过
36         Map<TreeNode, Boolean> visited = new HashMap<TreeNode, Boolean>();
37         Stack<TreeNode> stack = new Stack<TreeNode>();
38         stack.push(root);
39         TreeNode curPoint = root.left;
40         while(curPoint != null)
41         {
42             stack.push(curPoint);
43             curPoint = curPoint.left;
44         }
45         while(!stack.isEmpty()){
46             curPoint = stack.peek();
47             if(curPoint.right == null || visited.get(curPoint.right) != null){
48                 curPoint = stack.pop();
49                 System.out.print(curPoint.val + " ");
50                 visited.put(curPoint, true);
51             }
52             else{
53                 curPoint = curPoint.right;
54                 while(curPoint != null){
55                     stack.push(curPoint);
56                     curPoint = curPoint.left;
57                 }
58             }
59         }
60     }
61 
62 }

后序遍历需要额外空间保存已经访问过的节点

---------------------------------------------我是分割线，层序遍历---------------------------------------

 1 import java.util.LinkedList;
 2 import java.util.Queue;
 3 
 4 /**
 5  * 二叉树层序遍历
 6  * @author GXF
 7  *
 8  */
 9 public class LevelTravel {
10 
11     public static void main(String[] args) {
12         TreeNode root = TreeNode.createTree();
13         
14         LevelTravel levelTravel = new LevelTravel();
15         levelTravel.levelTravel(root);
16     }
17     
18     /**
19      * 二叉树层序遍历11
20      * @param root
21      */
22     public void levelTravel(TreeNode root){
23         if(root == null)
24             return;
25         Queue<TreeNode> queue = new LinkedList<TreeNode>();
26         queue.add(root);
27         while(!queue.isEmpty()){
28             root = queue.poll();
29             System.out.print(root.val + " ");
30             if(root.left != null)
31                 queue.add(root.left);
32             if(root.right != null)
33                 queue.add(root.right);
34         }
35     }
36 }