用java實現的數組創建二叉樹以及遞歸先序遍歷，遞歸中序遍歷，遞歸后序遍歷，非遞歸前序遍歷，非遞歸中序遍歷，非遞歸后序遍歷，深度優先遍歷，廣度優先遍歷8種遍歷方式：
|
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
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
|
package myTest;import java.util.ArrayList;import java.util.LinkedList;import java.util.List;import java.util.Stack;public class myClass { public static void main(String[] args) { // TODO Auto-generated method stub myClass tree = new myClass(); int[] datas = new int[]{1,2,3,4,5,6,7,8,9}; List<Node> nodelist = new LinkedList<>(); tree.creatBinaryTree(datas, nodelist); Node root = nodelist.get(0); System.out.println("遞歸先序遍歷："); tree.preOrderTraversal(root); System.out.println(); System.out.println("非遞歸先序遍歷："); tree.preOrderTraversalbyLoop(root); System.out.println(); System.out.println("遞歸中序遍歷："); tree.inOrderTraversal(root); System.out.println(); System.out.println("非遞歸中序遍歷："); tree.inOrderTraversalbyLoop(root); System.out.println(); System.out.println("遞歸后序遍歷："); tree.postOrderTraversal(root); System.out.println(); System.out.println("非遞歸后序遍歷："); tree.postOrderTraversalbyLoop(root); System.out.println(); System.out.println("廣度優先遍歷："); tree.bfs(root); System.out.println(); System.out.println("深度優先遍歷："); List<List<Integer>> rst = new ArrayList<>(); List<Integer> list = new ArrayList<>(); tree.dfs(root,rst,list); System.out.println(rst); } /** * * @param datas 實現二叉樹各節點值的數組 * @param nodelist 二叉樹list */ private void creatBinaryTree(int[] datas,List<Node> nodelist){ //將數組變成node節點 for(int nodeindex=0;nodeindex<datas.length;nodeindex++){ Node node = new Node(datas[nodeindex]); nodelist.add(node); } //給所有父節點設定子節點 for(int index=0;index<nodelist.size()/2-1;index++){ //編號為n的節點他的左子節點編號為2*n 右子節點編號為2*n+1 但是因為list從0開始編號，所以還要+1 //這里父節點有1（2,3）,2（4,5）,3（6,7）,4（8,9） 但是最后一個父節點有可能沒有右子節點 需要單獨處理 nodelist.get(index).setLeft(nodelist.get(index*2+1)); nodelist.get(index).setRight(nodelist.get(index*2+2)); } //單獨處理最后一個父節點 因為它有可能沒有右子節點 int index = nodelist.size()/2-1; nodelist.get(index).setLeft(nodelist.get(index*2+1)); //先設置左子節點 if(nodelist.size() % 2 == 1){ //如果有奇數個節點，最后一個父節點才有右子節點 nodelist.get(index).setRight(nodelist.get(index*2+2)); } } /** * 遍歷當前節點的值 * @param nodelist * @param node */ public void checkCurrentNode(Node node){ System.out.print(node.getVar()+" "); } /** * 先序遍歷二叉樹 * @param root 二叉樹根節點 */ public void preOrderTraversal(Node node){ if (node == null) //很重要，必須加上 當遇到葉子節點用來停止向下遍歷 return; checkCurrentNode(node); preOrderTraversal(node.getLeft()); preOrderTraversal(node.getRight()); } /** * 中序遍歷二叉樹 * @param root 根節點 */ public void inOrderTraversal(Node node){ if (node == null) //很重要，必須加上 return; inOrderTraversal(node.getLeft()); checkCurrentNode(node); inOrderTraversal(node.getRight()); } /** * 后序遍歷二叉樹 * @param root 根節點 */ public void postOrderTraversal(Node node){ if (node == null) //很重要，必須加上 return; postOrderTraversal(node.getLeft()); postOrderTraversal(node.getRight()); checkCurrentNode(node); } /** * 非遞歸前序遍歷 * @param node */ public void preOrderTraversalbyLoop(Node node){ Stack<Node> stack = new Stack(); Node p = node; while(p!=null || !stack.isEmpty()){ while(p!=null){ //當p不為空時，就讀取p的值，并不斷更新p為其左子節點，即不斷讀取左子節點 checkCurrentNode(p); stack.push(p); //將p入棧 p = p.getLeft(); } if(!stack.isEmpty()){ p = stack.pop(); p = p.getRight(); } } } /** * 非遞歸中序遍歷 * @param node */ public void inOrderTraversalbyLoop(Node node){ Stack<Node> stack = new Stack(); Node p = node; while(p!=null || !stack.isEmpty()){ while(p!=null){ stack.push(p); p = p.getLeft(); } if(!stack.isEmpty()){ p = stack.pop(); checkCurrentNode(p); p = p.getRight(); } } } /** * 非遞歸后序遍歷 * @param node */ public void postOrderTraversalbyLoop(Node node){ Stack<Node> stack = new Stack<>(); Node p = node,prev = node; while(p!=null || !stack.isEmpty()){ while(p!=null){ stack.push(p); p = p.getLeft(); } if(!stack.isEmpty()){ Node temp = stack.peek().getRight(); if(temp == null||temp == prev){ p = stack.pop(); checkCurrentNode(p); prev = p; p = null; }else{ p = temp; } } } } /** * 廣度優先遍歷（從上到下遍歷二叉樹） * @param root */ public void bfs(Node root){ if(root == null) return; LinkedList<Node> queue = new LinkedList<Node>(); queue.offer(root); //首先將根節點存入隊列 //當隊列里有值時，每次取出隊首的node打印，打印之后判斷node是否有子節點，若有，則將子節點加入隊列 while(queue.size() > 0){ Node node = queue.peek(); queue.poll(); //取出隊首元素并打印 System.out.print(node.var+" "); if(node.left != null){ //如果有左子節點，則將其存入隊列 queue.offer(node.left); } if(node.right != null){ //如果有右子節點，則將其存入隊列 queue.offer(node.right); } } } /** * 深度優先遍歷 * @param node * @param rst * @param list */ public void dfs(Node node,List<List<Integer>> rst,List<Integer> list){ if(node == null) return; if(node.left == null && node.right == null){ list.add(node.var); /* 這里將list存入rst中時，不能直接將list存入，而是通過新建一個list來實現， * 因為如果直接用list的話，后面remove的時候也會將其最后一個存的節點刪掉*/ rst.add(new ArrayList<>(list)); list.remove(list.size()-1); } list.add(node.var); dfs(node.left,rst,list); dfs(node.right,rst,list); list.remove(list.size()-1); } /** * 節點類 * var 節點值 * left 節點左子節點 * right 右子節點 */ class Node{ int var; Node left; Node right; public Node(int var){ this.var = var; this.left = null; this.right = null; } public void setLeft(Node left) { this.left = left; } public void setRight(Node right) { this.right = right; } public int getVar() { return var; } public void setVar(int var) { this.var = var; } public Node getLeft() { return left; } public Node getRight() { return right; } }} |
運行結果：
遞歸先序遍歷：
1 2 4 8 9 5 3 6 7
非遞歸先序遍歷：
1 2 4 8 9 5 3 6 7
遞歸中序遍歷：
8 4 9 2 5 1 6 3 7
非遞歸中序遍歷：
8 4 9 2 5 1 6 3 7
遞歸后序遍歷：
8 9 4 5 2 6 7 3 1
非遞歸后序遍歷：
8 9 4 5 2 6 7 3 1
廣度優先遍歷：
1 2 3 4 5 6 7 8 9
深度優先遍歷：
[[1, 2, 4, 8], [1, 2, 4, 9], [1, 2, 5], [1, 3, 6], [1, 3, 7]]
以上這篇java實現二叉樹的創建及5種遍歷方法(總結)就是小編分享給大家的全部內容了，希望能給大家一個參考，也希望大家多多支持服務器之家。
