本文實例講述了java實現二叉樹的深度優先遍歷和廣度優先遍歷算法。分享給大家供大家參考，具體如下：
1. 分析
二叉樹的深度優先遍歷的非遞歸的通用做法是采用棧，廣度優先遍歷的非遞歸的通用做法是采用隊列。
深度優先遍歷：對每一個可能的分支路徑深入到不能再深入為止，而且每個結點只能訪問一次。要特別注意的是，二叉樹的深度優先遍歷比較特殊，可以細分為先序遍歷、中序遍歷、后序遍歷。具體說明如下：
先序遍歷：對任一子樹，先訪問根，然后遍歷其左子樹，最后遍歷其右子樹。
中序遍歷：對任一子樹，先遍歷其左子樹，然后訪問根，最后遍歷其右子樹。
后序遍歷：對任一子樹，先遍歷其左子樹，然后遍歷其右子樹，最后訪問根。
廣度優先遍歷：又叫層次遍歷，從上往下對每一層依次訪問，在每一層中，從左往右（也可以從右往左）訪問結點，訪問完一層就進入下一層，直到沒有結點可以訪問為止。
2. 舉例說明
對下圖所示的二叉排序樹進行遍歷，要求使用先序遍歷（遞歸、非遞歸）、中序遍歷（遞歸、非遞歸）、后序遍歷（遞歸、非遞歸）和廣度優先遍歷。
① 參考代碼
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
|
package binarytreetraversetest;import java.util.linkedlist;import java.util.queue;/** * 二叉樹的深度優先遍歷和廣度優先遍歷 * @author fantasy * @version 1.0 2016/10/05 - 2016/10/07 */public class binarytreetraversetest { public static void main(string[] args) { binarysorttree<integer> tree = new binarysorttree<integer>(); tree.insertnode(35); tree.insertnode(20); tree.insertnode(15); tree.insertnode(16); tree.insertnode(29); tree.insertnode(28); tree.insertnode(30); tree.insertnode(40); tree.insertnode(50); tree.insertnode(45); tree.insertnode(55); system.out.print("先序遍歷（遞歸）："); tree.preordertraverse(tree.getroot()); system.out.println(); system.out.print("中序遍歷（遞歸）："); tree.inordertraverse(tree.getroot()); system.out.println(); system.out.print("后序遍歷（遞歸）："); tree.postordertraverse(tree.getroot()); system.out.println(); system.out.print("先序遍歷（非遞歸）："); tree.preordertraversenorecursion(tree.getroot()); system.out.println(); system.out.print("中序遍歷（非遞歸）："); tree.inordertraversenorecursion(tree.getroot()); system.out.println(); system.out.print("后序遍歷（非遞歸）："); tree.postordertraversenorecursion(tree.getroot()); system.out.println(); system.out.print("廣度優先遍歷："); tree.breadthfirsttraverse(tree.getroot()); }}/** * 結點 */class node<e extends comparable<e>> { e value; node<e> left; node<e> right; node(e value) { this.value = value; left = null; right = null; }}/** * 使用一個先序序列構建一棵二叉排序樹（又稱二叉查找樹） */class binarysorttree<e extends comparable<e>> { private node<e> root; binarysorttree() { root = null; } public void insertnode(e value) { if (root == null) { root = new node<e>(value); return; } node<e> currentnode = root; while (true) { if (value.compareto(currentnode.value) > 0) { if (currentnode.right == null) { currentnode.right = new node<e>(value); break; } currentnode = currentnode.right; } else { if (currentnode.left == null) { currentnode.left = new node<e>(value); break; } currentnode = currentnode.left; } } } public node<e> getroot(){ return root; } /** * 先序遍歷二叉樹（遞歸） * @param node */ public void preordertraverse(node<e> node) { system.out.print(node.value + " "); if (node.left != null) preordertraverse(node.left); if (node.right != null) preordertraverse(node.right); } /** * 中序遍歷二叉樹（遞歸） * @param node */ public void inordertraverse(node<e> node) { if (node.left != null) inordertraverse(node.left); system.out.print(node.value + " "); if (node.right != null) inordertraverse(node.right); } /** * 后序遍歷二叉樹（遞歸） * @param node */ public void postordertraverse(node<e> node) { if (node.left != null) postordertraverse(node.left); if (node.right != null) postordertraverse(node.right); system.out.print(node.value + " "); } /** * 先序遍歷二叉樹（非遞歸） * @param root */ public void preordertraversenorecursion(node<e> root) { linkedlist<node<e>> stack = new linkedlist<node<e>>(); node<e> currentnode = null; stack.push(root); while (!stack.isempty()) { currentnode = stack.pop(); system.out.print(currentnode.value + " "); if (currentnode.right != null) stack.push(currentnode.right); if (currentnode.left != null) stack.push(currentnode.left); } } /** * 中序遍歷二叉樹（非遞歸） * @param root */ public void inordertraversenorecursion(node<e> root) { linkedlist<node<e>> stack = new linkedlist<node<e>>(); node<e> currentnode = root; while (currentnode != null || !stack.isempty()) { // 一直循環到二叉排序樹最左端的葉子結點（currentnode是null） while (currentnode != null) { stack.push(currentnode); currentnode = currentnode.left; } currentnode = stack.pop(); system.out.print(currentnode.value + " "); currentnode = currentnode.right; } } /** * 后序遍歷二叉樹（非遞歸） * @param root */ public void postordertraversenorecursion(node<e> root) { linkedlist<node<e>> stack = new linkedlist<node<e>>(); node<e> currentnode = root; node<e> rightnode = null; while (currentnode != null || !stack.isempty()) { // 一直循環到二叉排序樹最左端的葉子結點（currentnode是null） while (currentnode != null) { stack.push(currentnode); currentnode = currentnode.left; } currentnode = stack.pop(); // 當前結點沒有右結點或上一個結點（已經輸出的結點）是當前結點的右結點，則輸出當前結點 while (currentnode.right == null || currentnode.right == rightnode) { system.out.print(currentnode.value + " "); rightnode = currentnode; if (stack.isempty()) { return; //root以輸出，則遍歷結束 } currentnode = stack.pop(); } stack.push(currentnode); //還有右結點沒有遍歷 currentnode = currentnode.right; } } /** * 廣度優先遍歷二叉樹，又稱層次遍歷二叉樹 * @param node */ public void breadthfirsttraverse(node<e> root) { queue<node<e>> queue = new linkedlist<node<e>>(); node<e> currentnode = null; queue.offer(root); while (!queue.isempty()) { currentnode = queue.poll(); system.out.print(currentnode.value + " "); if (currentnode.left != null) queue.offer(currentnode.left); if (currentnode.right != null) queue.offer(currentnode.right); } }} |
② 輸出結果
先序遍歷（遞歸）：35 20 15 16 29 28 30 40 50 45 55
中序遍歷（遞歸）：15 16 20 28 29 30 35 40 45 50 55
后序遍歷（遞歸）：16 15 28 30 29 20 45 55 50 40 35
先序遍歷（非遞歸）：35 20 15 16 29 28 30 40 50 45 55
中序遍歷（非遞歸）：15 16 20 28 29 30 35 40 45 50 55
后序遍歷（非遞歸）：16 15 28 30 29 20 45 55 50 40 35
廣度優先遍歷：35 20 40 15 29 50 16 28 30 45 55
希望本文所述對大家java程序設計有所幫助。
原文鏈接：https://blog.csdn.net/fantasy_lin_/article/details/52751559
