二叉树前序遍历，中序遍历，后序遍历java实现

痛定思痛。 2023-10-17 19:03 49阅读 0赞

首先来看一棵二叉树：

![20160303173659257][]

1、前序遍历：

前序遍历首先访问根结点然后遍历左子树，最后遍历右子树。在遍历左、右子树时，仍然先访问 [根结点][Link 1]，然后遍历左子树，最后遍历右子树。

若 [二叉树][Link 2]为空则结束返回，否则：

（1）访问根结点；

（2）前序遍历左子树；

（3）前序遍历右子树 ；

需要注意的是：遍历左右子树时仍然采用前序遍历方法。可以看出前序遍历后，遍历结果为：631254978

2、中序遍历：

中序遍历首先遍历左子树，然后访问根结点，最后遍历右子树。在遍历左、右子树时，仍然先遍历左子树，再访问根结点，最后遍历右子树。即：

若 [二叉树][Link 2]为空则结束返回， 否则：

（1）中序遍历左子树；

（2）访问根结点；

（3）中序遍历右子树；

注意的是：遍历左右子树时仍然采用中序遍历方法。最上图的二叉树用中序遍历的结果是：123456789

3、后续遍历：

后序遍历首先遍历左子树，然后遍历右子树，最后访问根结点，在遍历左、右子树时，仍然先遍历左子树，然后遍历右子树，最后遍历根结点。即：

若 [二叉树][Link 2]为空则结束返回， 否则：

（1）后序遍历左子树；

（2）后序遍历右子树；

（3）访问根结点；

如图所示的二叉树，用后序遍历的结果是：214538796

三种遍历的递归实现：

**\[java\]** [view plain][] [copy][view plain]

1.  publicclass Node \{ //二叉树节点
2.  
3.  privateint 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. publicint getData()\{ 
14. return data; 
15.  \} 
16. 
17. publicvoid setData(int data)\{ 
18. this.data = data; 
19.  \} 
20. 
21. public Node getLeftNode()\{ 
22. return leftNode; 
23.  \} 
24. 
25. publicvoid setLeftNode(Node leftNode)\{ 
26. this.leftNode = leftNode; 
27.  \} 
28. 
29. public Node getRightNode()\{ 
30. return rightNode; 
31.  \} 
32. 
33. publicvoid setRightNode(Node rightNode)\{ 
34. this.rightNode = rightNode; 
35.  \} 
36. 
37. \}

三种遍历的递归实现：

**\[java\]** [view plain][] [copy][view plain]

1.  publicclass BinaryTree\_DiGui \{ 
2.  
3.  /\*
4.   \* 二叉树先序中序后序排序
5.   \* 方式：递归。
6.   \*/
7.  
8.  //注意必须逆序简历，先建立子节点，再逆序往上建立，
9.  //因为非叶子节点会使用到下面的节点，而初始化是按顺序初始化得，不逆序建立会报错
10. publicstatic 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. publicstaticvoid printNode(Node node)\{ 
25.  System.out.print(node.getData()); 
26.  \} 
27. 
28. 
29. //先序遍历
30. publicstaticvoid 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. publicstaticvoid 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. publicstaticvoid 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. publicstaticvoid main(String\[\] args)\{ 
74. // BinaryTree tree = new BinaryTree();//注释掉本行后类中方法需变为static
75.  Node root = init(); 
76. 
77.  System.out.println("先序遍历"); 
78.  preOrder(root); 
79.  System.out.println(""); 
80. 
81.  System.out.println("中序遍历"); 
82.  inOrder(root); 
83.  System.out.println(""); 
84. 
85.  System.out.println("后序遍历"); 
86.  postOrder(root); 
87.  System.out.println(""); 
88. 
89.  \} 
90. 
91. \}

通过栈实现三种遍历（非递归）：

**\[java\]** [view plain][] [copy][view plain]

1.  publicclass BinaryTree\_Zhan \{ 
2.  
3.  /\*
4.   \* 
5.   \* 二叉树先序中序后序排序
6.   \* 方式：采用非递归方式。
7.   \*/
8.  
9.  //注意必须逆序简历，先建立子节点，再逆序往上建立，
10. //因为非叶子节点会使用到下面的节点，而初始化是按顺序初始化得，不逆序建立会报错
11. publicstatic 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. publicstaticvoid printNode(Node node)\{ 
26.  System.out.print(node.getData()); 
27.  \} 
28. 
29. 
30. publicstaticvoid preOrder\_stack(Node root)\{ //先序遍历
31. 
32.  Stack<Node> stack = new Stack<Node>(); 
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. publicstaticvoid inOrder\_Stack(Node root)\{ //中序遍历
50. 
51.  Stack<Node> stack = new Stack<Node>(); 
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. publicstaticvoid postOrder\_Stack(Node root)\{ //后续遍历
68. 
69.  Stack<Node> stack = new Stack<Node>(); 
70.  Stack<Node> output = new Stack<Node>();//构造一个中间栈来存储逆后续遍历的结果
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. publicstaticvoid main(String\[\] args)\{ 
91. 
92.  Node root = init(); 
93. 
94.  System.out.println("先序遍历"); 
95.  preOrder\_stack(root); 
96.  System.out.println(""); 
97. 
98.  System.out.println("中序遍历"); 
99.  inOrder\_Stack(root); 
100.  System.out.println(""); 
101. 
102.  System.out.println("后序遍历"); 
103.  postOrder\_Stack(root); 
104.  System.out.println(""); 
105.  \} 
106. 
107. \}

[20160303173659257]: https://img-blog.csdn.net/20160303173659257
[Link 1]: http://baike.baidu.com/view/549553.htm
[Link 2]: http://baike.baidu.com/view/88806.htm
[view plain]: https://blog.csdn.net/jssongwei/article/details/50790253#