算法：二叉树的先(根)序遍历、中(根)序遍历、后(根)序遍历（递归及压栈出栈实现的非递归方式）的java代码实现

 首先来看一棵二叉树：

1、前(根)序遍历，也叫先序遍历：

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问
根结点，然后遍历左子树，最后遍历右子树。 若
二叉树为空则结束返回，否则： （1）访问根结点； （2）前序遍历左子树； （3）前序遍历右子树 ； 需要注意的是：遍历左右子树时仍然采用前序遍历方法。可以看出前序遍历后，遍历结果为：631254978
2、中(根)序遍历： 中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即： 若
二叉树为空则结束返回，
否则： （1）中序遍历左子树； （2）访问根结点；

（3）中序遍历右子树； 注意的是：遍历左右子树时仍然采用中序遍历方法。最上图的二叉树用中序遍历的结果是：123456789
3、后(根)序遍历： 后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即： 若
二叉树为空则结束返回，
否则： （1）后序遍历左子树； （2）后序遍历右子树； （3）访问根结点； 如图所示的二叉树，用后序遍历的结果是：214538796

三种遍历的递归实现：
[java] 
view plain
 copy

1. public class Node { //二叉树节点  
2.       
3.     private int data;  
4.     private Node leftNode;  
5.     private Node rightNode;  
6.       
7.     public Node(int data, Node leftNode, Node rightNode){  
8.         this.data = data;  
9.         this.leftNode = leftNode;  
10.         this.rightNode = rightNode;  
11.     }  
12.       
13.     public int getData(){  
14.         return data;  
15.     }  
16.       
17.     public void setData(int data){  
18.         this.data = data;  
19.     }  
20.       
21.     public Node getLeftNode(){  
22.         return leftNode;  
23.     }  
24.       
25.     public void setLeftNode(Node leftNode){  
26.         this.leftNode = leftNode;  
27.     }  
28.       
29.     public Node getRightNode(){  
30.         return rightNode;  
31.     }  
32.       
33.     public void setRightNode(Node rightNode){  
34.         this.rightNode = rightNode;  
35.     }  
36.       
37. }  

三种遍历的递归实现：
[java] 
view plain
 copy

1. public class BinaryTree_DiGui {  
2.       
3.     /* 
4.      * 二叉树先序中序后序排序 
5.      * 方式：递归。 
6.      */  
7.       
8.     //注意必须逆序简历，先建立子节点，再逆序往上建立，  
9.     //因为非叶子节点会使用到下面的节点，而初始化是按顺序初始化得，不逆序建立会报错  
10.     public static Node init(){  
11.         Node J = new Node(8, null, null);  
12.         Node H = new Node(4, null, null);  
13.         Node G = new Node(2, null, null);  
14.         Node F = new Node(7, null, J);  
15.         Node E = new Node(5, H, null);  
16.         Node D = new Node(1, null, G);  
17.         Node C = new Node(9, F, null);  
18.         Node B = new Node(3, D, E);  
19.         Node A = new Node(6, B, C);  
20.         return A;  //返回根节点  
21.     }  
22.       
23.     //打印节点数值  
24.     public static void printNode(Node node){  
25.         System.out.print(node.getData());  
26.     }  
27.       
28.       
29.     //先序遍历  
30.     public static void preOrder(Node root){  
31.           
32.         printNode(root);//打印根节点  
33.           
34.         if(root.getLeftNode() != null){ //使用递归遍历左孩子  
35.             preOrder(root.getLeftNode());  
36.         }  
37.         if(root.getRightNode() != null){ //使用递归遍历右孩子  
38.             preOrder(root.getRightNode());  
39.         }  
40.     }  
41.       
42.       
43.     //中序遍历  
44.     public static void inOrder(Node root){  
45.           
46.         if(root.getLeftNode() != null){ //使用递归遍历左孩子  
47.             inOrder(root.getLeftNode());  
48.         }  
49.           
50.         printNode(root);//打印根节点  
51.           
52.         if(root.getRightNode() != null){ //使用递归遍历右孩子  
53.             inOrder(root.getRightNode());  
54.         }  
55.     }  
56.       
57.       
58.     //后续遍历  
59.     public static void postOrder(Node root){  
60.           
61.         if(root.getLeftNode() != null){ //使用递归遍历左孩子  
62.             postOrder(root.getLeftNode());  
63.         }  
64.           
65.         if(root.getRightNode() != null){ //使用递归遍历右孩子  
66.             postOrder(root.getRightNode());  
67.         }  
68.           
69.         printNode(root);//打印根节点  
70.     }  
71.       
72.       
73.     public static void main(String[] args){  
74. //      BinaryTree tree = new BinaryTree();//注释掉本行后类中方法需变为static  
75.         Node root = init();  
76.           
77.         System.out.println(&＃8220;先序遍历&＃8221;);  
78.         preOrder(root);  
79.         System.out.println(&＃8220;&＃8221;);  
80.           
81.         System.out.println(&＃8220;中序遍历&＃8221;);  
82.         inOrder(root);  
83.         System.out.println(&＃8220;&＃8221;);  
84.           
85.         System.out.println(&＃8220;后序遍历&＃8221;);  
86.         postOrder(root);  
87.         System.out.println(&＃8220;&＃8221;);  
88.           
89.     }  
90.       
91. }  

通过栈实现三种遍历（非递归）：
[java] 
view plain
 copy

1. public class BinaryTree_Zhan {  
2.       
3.     /* 
4.      *  
5.      * 二叉树先序中序后序排序 
6.      * 方式：采用非递归方式。 
7.      */  
8.       
9.     //注意必须逆序简历，先建立子节点，再逆序往上建立，  
10.     //因为非叶子节点会使用到下面的节点，而初始化是按顺序初始化得，不逆序建立会报错  
11.     public static Node init(){  
12.         Node J = new Node(8, null, null);  
13.         Node H = new Node(4, null, null);  
14.         Node G = new Node(2, null, null);  
15.         Node F = new Node(7, null, J);  
16.         Node E = new Node(5, H, null);  
17.         Node D = new Node(1, null, G);  
18.         Node C = new Node(9, F, null);  
19.         Node B = new Node(3, D, E);  
20.         Node A = new Node(6, B, C);  
21.         return A;  //返回根节点  
22.     }  
23.       
24.     //打印节点数值  
25.     public static void printNode(Node node){  
26.         System.out.print(node.getData());  
27.     }  
28.       
29.       
30.     public static void preOrder_stack(Node root){ //先序遍历  
31.           
32.         Stack stack = new Stack();  
33.         Node node = root;  
34.           
35.         while(node != null || stack.size()>0){ //将所有左孩子压栈  
36.             if(node != null){ //压栈之前先访问  
37.                 printNode(node);  
38.                 stack.push(node);  
39.                 node = node.getLeftNode();  
40.                   
41.             }else{  
42.                 node = stack.pop();  
43.                 node = node.getRightNode();  
44.             }  
45.         }  
46.     }  
47.       
48.       
49.     public static void inOrder_Stack(Node root){ //中序遍历  
50.           
51.         Stack stack = new Stack();  
52.         Node node = root;  
53.           
54.         while(node != null || stack.size()>0){  
55.             if(node != null){  
56.                 stack.push(node);//直接压栈  
57.                 node = node.getLeftNode();  
58.             }else{  
59.                 node = stack.pop();//出栈并访问  
60.                 printNode(node);  
61.                 node = node.getRightNode();  
62.             }  
63.         }  
64.     }  
65.       
66.       
67.     public static void postOrder_Stack(Node root){ //后续遍历  
68.           
69.         Stack stack = new Stack();  
70.         Stack output = new Stack();//构造一个中间栈来存储逆后续遍历的结果  
71.         Node node = root;  
72.         while(node != null || stack.size()>0){  
73.             if(node != null){  
74.                 output.push(node);  
75.                 stack.push(node);  
76.                 node = node.getRightNode();  
77.             }else{  
78.                 node = stack.pop();  
79.                 node = node.getLeftNode();  
80.             }  
81.         }  
82.           
83.         while(output.size()>0){  
84.             printNode(output.pop());  
85.         }  
86.           
87.     }  
88.       
89.       
90.     public static void main(String[] args){  
91.           
92.         Node root = init();  
93.           
94.         System.out.println(&＃8220;先序遍历&＃8221;);  
95.         preOrder_stack(root);  
96.         System.out.println(&＃8220;&＃8221;);  
97.           
98.         System.out.println(&＃8220;中序遍历&＃8221;);  
99.         inOrder_Stack(root);   
100.         System.out.println(&＃8220;&＃8221;);  
101.           
102.         System.out.println(&＃8220;后序遍历&＃8221;);  
103.         postOrder_Stack(root);  
104.         System.out.println(&＃8220;&＃8221;);  
105.     }  
106.   
107. }