資料結構之樹-第一篇
1、此時，将元素30從隊首拿出來，進行通路，之後将30的左孩子29、右孩子42入隊，那麼此時隊首元素就是13了。
1 package com.tree;
2
3
4 import java.util.*;
5
6 /**
7 * 1、二分搜尋樹，二分搜尋樹存儲的内容支援泛型，但是不是支援所有的類型，應該對類型有一個限制，
8 * 這個限制是這個類型必須擁有可比較性，對泛型E進行限制，這個限制就是繼承Comparable<E>接口，
9 * 這個類型E必須具有可比較性。
10 * <p>
11 * <p>
12 * 2、對于前序、中序、後序周遊來說，不管是遞歸寫法還是非遞歸寫法，對于我們這棵二分搜尋樹來說，
13 * 我們都是在周遊的過程中一紮到底，這樣的一種周遊方式，其實還有另外一個名字，叫做，深度優先周遊。
14 * 對于這棵樹來說，都會先來到這棵樹最深的地方，直到不能再深了，才開始傳回回去，
15 * 這種周遊叫做深度優先周遊。和深度優先周遊相對的是另外一種周遊方式，叫做廣度優先周遊，
16 * 廣度優先周遊周遊出來的結果，這個順序其實是整個二分搜尋樹的層序周遊的順序。
17 */
18 public class BinarySearchTree<E extends Comparable<E>> {
19
20 // 二分搜尋樹的節點類，私有内部類。
21 private class Node {
22 private E e;// 存儲元素e;
23 private Node left;// 指向左子樹，指向左孩子。
24 private Node right;// 指向右子樹，指向右孩子。
25
26 /**
27 * 含參構造函數
28 *
29 * @param e
30 */
31 public Node(E e) {
32 this.e = e;// 使用者存儲的元素e。
33 left = null;// 左孩子初始化為空。
34 right = null;// 右孩子初始化為空。
35 }
36 }
37
38 private Node root;// 根節點
39 private int size;// 二分搜尋樹存儲了多少個元素
40
41 /**
42 * 無參構造函數，和預設構造函數做的事情一樣的。
43 */
44 public BinarySearchTree() {
45 // 初始化的時候，二分搜尋樹一個元素都沒有存儲
46 root = null;
47 size = 0;// 大小初始化為0
48 }
49
50 /**
51 * 傳回二分搜尋樹的含有多少個元素
52 *
53 * @return
54 */
55 public int size() {
56 // 二分搜尋樹的大小
57 return size;
58 }
59
60 /**
61 * 判斷二分搜尋樹是否為空。
62 *
63 * @return
64 */
65 public boolean isEmpty() {
66 return size == 0;
67 }
68
69 // /**
70 // * 向二分搜尋樹中添加新的元素e.
71 // * <p>
72 // * 在公開的二分搜尋樹的調用的add方法。在将遞歸調用中， 是将新的元素e作為node子節點插入進去的。
73 // * 這個時候，形成了一個邏輯上的不統一，遞歸函數中，e元素和node.e元素進行了兩輪比較，第一輪比較，
74 // * 在比較完他們的大小的同時，還要看一下node的左右兩邊是不是為空，如果為空直接插入，
75 // * 對于第二輪比較，我們知道我們不能直接作為Node的孩子插入這個元素e，隻要再次遞歸的調用add的函數。
76 // *
77 // * @param e
78 // */
79 // public void add(E e) {
80 // // 判斷，如果根節點是空的時候，直接指向新建立的節點即可
81 // if (root == null) {
82 // // 對根節點進行特殊的處理，如果根為空的時候，就直接建立一個新的節點。
83 // root = new Node(e);
84 // // 維護size
85 // size++;
86 // } else {
87 // // 否則，根節點不是空的時候。從根節點開始添加一個元素。
88 // // 注意，由于需要遞歸的調用，對于每一個節點的左子樹也是一個更小的二分搜尋樹的根節點，
89 // // 對于每一個節點的右子樹也是一個更小的二分搜尋樹的根節點。
90 // // 是以在遞歸的過程中，建立一個新的遞歸的函數。
91 //
92 // // 如果根不為空，嘗試從根節點開始插入元素e。
93 // add(root, e);
94 // }
95 //
96 // }
97 //
98 // /**
99 // * 私有的遞歸添加方法
100 // * <p>
101 // * 整體上是，向以node為根的二分搜尋樹中插入元素E，遞歸算法。
102 // * <p>
103 // * 之是以設定Node，就是因為在插入的過程中，我們要不斷地轉換到新的更小的二分搜尋樹中，
104 // * 去找到這個新的元素e真正應該插入的位置，那麼相應的，我們在遞歸調用的過程中，
105 // * 相當于二分搜尋樹的根在逐漸變化的，是以，我們需要靠這個參數來展現這個變化。
106 // *
107 // * @param node Node結構本身都是對使用者屏蔽的，使用者不需要了解二分搜尋樹中節點的結構。
108 // * @param e
109 // */
110 // private void add(Node node, E e) {
111 // // 精髓，将新的元素e插入給node的左孩子還是node的右孩子。
112 // // 對目前的node來說，如果想插入到左邊，但是左孩子不為空的話，再遞歸的将新的元素e插入到add(node.left, e);node的左子樹。
113 // // 如果想插入到右邊，但是右孩子不為空的話，再遞歸的将新的元素e插入到add(node.right, e);node的右子樹。
114 //
115 //
116 // // 第一部分，遞歸終止的條件。
117 // // 先檢查一下元素e，是不是等于node的元素e。
118 // if (e.equals(node.e)) {
119 // // 如果相等，說明要插入的元素已經存在于二分搜尋樹中了。
120 // return;
121 // // 主要的插入代碼，就是下面的判斷，然後将元素e進行插入到左子樹還是右子樹的操作。
122 // } else if (e.compareTo(node.e) < 0 && node.left == null) {
123 // // 如果待插入元素e小于node的元素e，則把元素e插入到node的左子樹上面。
124 // // 由于元素E滿足Comparable<E>類型的，是以應該是使用compareTo方法比較，不是基礎資料類型，不能使用大于号小于号比較。
125 //
126 // // 如果此時node的左子樹又等于空，直接建立一個Node，将元素存儲到Node裡面即可。
127 // // 此時元素e就變成了node的左孩子了。
128 // node.left = new Node(e);
129 // // 維護size的大小。
130 // size++;
131 // // return表示此次插入操作也完成了。
132 // return;
133 // } else if (e.compareTo(node.e) > 0 && node.right == null) {
134 // // 如果待插入元素e大于node節點的元素e，則把元素e插入到node的右子樹上面。
135 // // 此時，如果node的右孩子又等于空，直接建立一個Node，将元素存儲到Node即可。
136 // // 此時，元素就變成了node的右孩子了。
137 // node.right = new Node(e);
138 // // 維護size的大小。
139 // size++;
140 // // return表示此次插入操作也完成了。
141 // return;
142 // }
143 //
144 //
145 // // 遞歸的第二部分。遞歸調用的邏輯。
146 // if (e.compareTo(node.e) < 0) {
147 // // 如果待插入元素e小于node的元素e，遞歸調用add方法，參數一是向左子樹添加左孩子。
148 // // 向左子樹添加元素e。
149 // add(node.left, e);
150 // } else if (e.compareTo(node.e) > 0) {
151 // // 如果待插入元素e大于node的元素e，遞歸調用add方法，參數一是向右子樹添加右孩子。
152 // // 向右子樹添加元素e。
153 // add(node.right, e);
154 // }
155 // }
156
157
158 /**
159 * 向二分搜尋樹中添加新的元素e。
160 *
161 * @param e
162 */
163 public void add(E e) {
164 // 此時，不需要對root為空進行特殊判斷。
165 // 向root中插入元素e。如果root為空的話，直接傳回一個新的節點，将元素存儲到該新的節點裡面。
166 root = add(root, e);
167 }
168
169 /**
170 * 深入了解遞歸終止條件。
171 * <p>
172 * 傳回插入新節點後二叉搜尋樹的根。
173 * <p>
174 * 向以node為根的二分搜尋樹中插入元素e，遞歸算法。
175 * <p>
176 * <p>
177 * 對于新的add遞歸函數，将向以node為根的二分搜尋樹中插入元素e，并且傳回在做完這個操作以後這個二分搜尋樹的根節點，
178 * 如果我們傳入的這個node為空的話，插入新的元素以後，就産生新的根節點，就是建立了一個Node e,
179 * 否則的話，我們來比較我們待插入的元素e和目前的node e的大小關系，如果小于零的話，向左子樹添加一個左孩子，
180 * 如果大于零的話，向右子樹添加一個右孩子。如果等于零的話，什麼都不操作。
181 * 不管向左子樹添加元素還是向右子樹添加元素，插入完成之後，都将目前node的左孩子和右孩子進行重新指派，
182 * 在重新指派以後，這個node依賴是這個以node為根的二分搜尋樹。相應的根節點将他傳回回去。
183 * <p>
184 * 連結清單的遞歸插入和二分搜尋樹的添加具有高度相似性的，在二分搜尋樹中需要判斷一下，是要插入到左子樹還是右子樹。
185 *
186 * @param node
187 * @param e
188 * @return
189 */
190 private Node add(Node node, E e) {
191 // 空本身也是一種二分搜尋樹，空本身也是一顆二叉樹，換句話說，如果走遞歸函數，走到node為空的時候
192 // 一定要建立一個Node節點。上面的add方法實作，其實還沒有遞歸到底部。
193
194 // 精髓，如果待插入元素e小于node的元素e，此時不管node.left是不是為空，就再遞歸一層，
195 // 如果遞歸的這一層，node等于空的話，也就是，現在要新插入一個元素，插入到哪裡，插入到空這顆
196 // 二叉樹上，那麼，很顯然，這個位置本身就應該是這個節點。
197
198
199 // 如果按照上面的思想，如果此時node等于空的話，此時，肯定要插入一個節點。
200 if (node == null) {
201 // 維護size的大小。
202 size++;
203 // 如果此時，直接建立一個Node的話，沒有和二叉樹挂接起來。
204 // 如何讓此節點挂接到二叉樹上呢，直接将建立的節點return傳回回去即可，傳回給調用的上層。
205 return new Node(e);
206 }
207
208 // 遞歸的第二部分。遞歸調用的邏輯。
209 if (e.compareTo(node.e) < 0) {
210 // 如果待插入元素e小于node的元素e，遞歸調用add方法，參數一是向左子樹添加左孩子。
211 // 向左子樹添加元素e。
212 // 向左子樹添加元素e的時候，為了讓整顆二叉樹發生改變，在node的左子樹中插入元素e，
213 // 插入的結果，有可能是變化的，是以就要讓node的左子樹連接配接住這個變化。
214
215 // 注意，如果此時，node.left是空的話，這次add操作相應的就會傳回一個新的Node節點，
216 // 對于這個新的節點，我們的node.left被指派這個新的節點，相當于我們就改變了整棵二叉樹。
217 node.left = add(node.left, e);
218 } else if (e.compareTo(node.e) > 0) {
219 // 如果待插入元素e大于node的元素e，遞歸調用add方法，參數一是向右子樹添加右孩子。
220 // 向右子樹添加元素e。
221 node.right = add(node.right, e);
222 }
223
224 // 注意，如果如果待插入元素e等于node的元素e，不進行任何操作。
225
226 // 最後将以node為根的二叉樹傳回回去。
227 // 不管在第二部分産生了什麼變化，如果我們的node不為空的話，我們進去了第二部分，
228 // 向以node為根的二分搜尋樹中插入元素e之後，最終，插入了這個節點以後，
229 // 二分搜尋樹的根呢，還是這個node。
230 return node;
231 }
232
233
234 /**
235 * 檢視二分搜尋樹中是否包含元素e
236 *
237 * @param e
238 * @return
239 */
240 public boolean contains(E e) {
241 // 遞歸實作，遞歸的過程中，就要從這個二分搜尋樹的根節點開始，逐漸的轉移在新的二分搜尋樹的子樹中，
242 // 縮小問題規模，縮小查詢的樹的規模，直到發現找到這個元素e或者找不到這個元素e。
243
244 // 整體是看以我們這整棵二分搜尋樹為根的二分搜尋樹中是否包含元素e。
245 return contains(root, e);
246 }
247
248 /**
249 * 看以node為根的二分搜尋樹中是否包含元素e，遞歸算法
250 * <p>
251 * 二分搜尋樹查詢元素，對于查詢元素來說，我們隻要不停的看節點node裡面儲存的元素就好了。
252 * 不牽扯到二分搜尋樹，添加一個元素之後，又如何把它挂接到整個二分搜尋樹中。
253 *
254 * @param node 節點Node
255 * @param e 帶查詢的元素e
256 * @return
257 */
258 private boolean contains(Node node, E e) {
259 // 遞歸的第一部分
260 if (node == null) {
261 // 如果node節點為空，是不包含元素e的，此時直接傳回false
262 return false;
263 }
264
265 // 遞歸的第二部分，開始邏輯判斷
266 if (e.compareTo(node.e) == 0) {
267 // 如果待查詢元素e和node的元素e相等
268 return true;
269 } else if (e.compareTo(node.e) < 0) {
270 // 如果待查詢元素e小于node的元素e，如果此二分搜尋樹中還包含元素e的話，那麼隻可能在node的左子樹
271 return contains(node.left, e);
272 } else {
273 // 如果待查詢元素e大于node的元素e，如果此二分搜尋樹中還包含元素e的話，那麼隻可能在node的右子樹
274 return contains(node.right, e);
275 }
276 }
277
278
279 /**
280 * 二分搜尋樹的前序周遊。二分搜尋樹的周遊操作，就是把所有節點都通路一遍。
281 * 對于二分搜尋樹的周遊操作來說，兩棵子樹都要顧及，差別于添加或者查詢是否包含，
282 * 隻走左子樹或者右子樹。
283 * <p>
284 * <p>
285 * 二分搜尋樹的前序周遊。為什麼這種周遊稱為前序周遊呢，是因為先通路這個節點，
286 * 再通路左右子樹，也就是說，通路這個節點放在了通路左右子樹的前面，是以叫做前序周遊。
287 * 基于此，也就有了二叉樹的中序周遊和後序周遊。
288 */
289 public void preOrder() {
290 // 需要指定遞歸的調用，指定是那一棵二叉樹進行的前序周遊。
291
292 // 使用者的初始的調用，隻需要對root根節點調用遞歸的preOrder就行了。
293 preOrder(root);
294 }
295
296 /**
297 * 前序周遊以node為根的二分搜尋樹，遞歸算法。
298 * <p>
299 * 前序周遊思路。
300 * 首先先周遊這個節點，再周遊這個節點的左子樹，之後周遊這個節點的右子樹。
301 * <p>
302 * 前序周遊是最自然的周遊方式，同時也是最常用的周遊方式。如果沒有特殊情況下，在大多數情況下都是使用前序周遊。
303 *
304 * @param node
305 */
306 private void preOrder(Node node) {
307 // 遞歸的第一部分
308 if (node == null) {
309 // 如果node為空的話，直接傳回
310 return;
311 }
312
313 // 遞歸的第二部分，開始周遊
314 System.out.println(node.e);
315 // 遞歸的調用根節點root的左子樹。
316 preOrder(node.left); // 此處是循環周遊左孩子，直到左孩子為空，直接傳回。
317 // 遞歸的調用根節點root的右子樹。
318 preOrder(node.right); // 執行完上面循環周遊左孩子，執行下面的循環周遊右孩子，直到右孩子是空，直接傳回。
319 // // 此時，完成了二分搜尋樹的前序周遊。
320
321
322 // 更新版遞歸過程
323 // if (node != null) {
324 // // 遞歸的第二部分，開始周遊
325 // System.out.println(node.e);
326 // // 遞歸的調用根節點root的左子樹。
327 // preOrder(node.left);
328 // // 遞歸的調用根節點root的右子樹。
329 // preOrder(node.right);
330 // // 此時，完成了二分搜尋樹的前序周遊。
331 // }
332 }
333
334
335 /**
336 * 二分搜尋樹的的前序周遊的非遞歸方式實作。
337 */
338 public void preOrderNonRecursive() {
339 // 棧的作用是記錄下面要到底要通路那些節點，記錄下一次依次要通路那些節點。
340 // 泛型是Node類型的，存儲的二叉樹節點類型的對象。
341 Stack<Node> stack = new Stack<Node>();
342 // 初始的時候将root根節點push進去
343 stack.push(root);
344
345 // 進行循環操作，隻要stack.isEmpty()為false，說明了棧裡面有元素。
346 // !stack.isEmpty()說明了記錄了下面要通路那個節點。
347 while (!stack.isEmpty()) {
348 // 隻要棧不為空，說明記錄了下面要通路那個節點。
349 // 就要進行通路這個節點。
350
351 // 目前通路的節點。
352 Node current = stack.pop();//将目前的棧頂元素拿出來。
353 // 此時current就是目前要通路的節點。目前要通路的節點直接列印即可。
354 System.out.println(current.e);
355
356
357 // 通路了目前節點之後，就要依次通路目前節點的左子樹，右子樹。
358 // 由于棧是後入先出的，是以先将目前節點的右子樹push進去。
359 // 此時應該判斷目前節點的右子樹是否為空，如果為空，就不要壓入棧了。
360 if (current.right != null) {
361 stack.push(current.right);// 右子樹壓入棧
362 }
363 // 此時應該判斷目前節點的左子樹是否為空，如果為空，就不要壓入棧了。
364 if (current.left != null) {
365 stack.push(current.left);//左子樹壓入棧
366 }
367 }
368
369 }
370
371
372 /**
373 * 二分搜尋樹的中序周遊。
374 * <p>
375 * 二分搜尋樹的的中序周遊，先通路這個節點的左子樹，再通路這個節點，再通路這個節點的右子樹。
376 * 中序周遊的中就展現在通路該節點放在周遊這個節點的左子樹和右子樹的中間。
377 */
378 public void inOrder() {
379 inOrder(root);
380 }
381
382 /**
383 * 中序周遊以node為根的二分搜尋樹，遞歸算法。
384 * <p>
385 * <p>
386 * 二分搜尋樹的中序周遊結果是順序的。有時候，因為這個功能，二分搜尋樹也叫做排序樹。
387 *
388 * @param node
389 */
390 private void inOrder(Node node) {
391 // 遞歸的第一部分，遞歸終止的條件
392 if (node == null) {
393 // 如果node為空的話，直接傳回
394 return;
395 }
396
397 // 遞歸的第二部分，開始周遊
398 // 遞歸的調用根節點root的左子樹。
399 inOrder(node.left); // 此處是循環周遊左孩子，直到左孩子為空，直接傳回。
400 // 此程式就是簡單的列印node節點的元素。就是通路這個節點元素的過程。
401 System.out.println(node.e);
402 // 遞歸的調用根節點root的右子樹。
403 inOrder(node.right); // 執行完上面循環周遊左孩子，執行下面的循環周遊右孩子，直到右孩子是空，直接傳回。
404 // 此時，完成了二分搜尋樹的中序周遊。
405 }
406
407
408 /**
409 * 後續周遊，二分搜尋樹的後序周遊。
410 */
411 public void postOrder() {
412 postOrder(root);
413 }
414
415 /**
416 * 二分搜尋樹的的後序周遊。
417 * <p>
418 * 二分搜尋樹的的後序周遊，先通路這個節點的左子樹，再通路這個節點的右子樹，最後再通路這個節點。
419 * <p>
420 * 後續周遊必須先處理完左子樹，再處理完右子樹，最後處理這個節點。
421 * <p>
422 * 後續周遊的一個應用，為二分搜尋樹釋放記憶體。先釋放左右孩子的記憶體，最後釋放這個節點的記憶體。
423 *
424 * @param node
425 */
426 private void postOrder(Node node) {
427 // 遞歸的第一部分，遞歸終止的條件
428 if (node == null) {
429 // 如果node為空的話，直接傳回
430 return;
431 }
432
433 // 遞歸的第二部分，開始周遊
434 // 遞歸的調用根節點root的左子樹。
435 postOrder(node.left); // 此處是循環周遊左孩子，直到左孩子為空，直接傳回。
436 // 遞歸的調用根節點root的右子樹。
437 postOrder(node.right); // 執行完上面循環周遊左孩子，執行下面的循環周遊右孩子，直到右孩子是空，直接傳回。
438 // 此程式就是簡單的列印node節點的元素。就是通路這個節點元素的過程。
439 System.out.println(node.e);
440 // 此時，完成了二分搜尋樹的後序周遊。
441 }
442
443
444 /**
445 * 二分搜尋樹的層序周遊
446 * <p>
447 * <p>
448 * 相對于深度優先周遊，廣度優先周遊最大的有點，可以更快的找到你想要查詢的那個元素，
449 * 這樣的差別，主要用于搜尋政策上，而不是用于周遊這種操作上，
450 * 因為周遊需要将所有的元素都通路一遍，在這種情況下，深度優先周遊，
451 * 廣度優先周遊是沒有差別的。但是如果想要在一棵樹中找到某個問題的解的話，
452 * 對于深度優先周遊來說，将從根節點一下子通路到樹的最深的地方，
453 * 但是問題的解很可能在樹的上面，是以深度優先周遊先估計左子樹，
454 * 需要很長的時間才能通路到最上面，在這種情況下，廣度優先周遊就很有意義了，
455 * 這種問題的模型，最常用于算法設計中的最短路徑的。
456 */
457 public void levelOrder() {
458 // 由于Queue是接口，這裡使用連結清單的方式實作該Queue。
459 Queue<Node> queue = new LinkedList<Node>();
460 // 将根節點添加到隊列中
461 queue.add(root);
462 // 循環周遊，當隊列不為空的時候，queue.isEmpty()結果為false表示隊列不為空，
463 // 當!queue.isEmpty()表示隊列不為空的時候，繼續循環周遊。
464 while (!queue.isEmpty()) {
465 // 聲明一個目前的節點current，也就是我們隊列中的元素出隊之後的那個元素，
466 // 就是我們目前要通路的這個元素。
467 Node current = queue.remove();
468 // 對于目前要通路的這個元素，可以進行列印輸出
469 System.out.println(current.e);
470
471 // 之後，根據目前通路的元素來看目前的這個節點左右孩子，如果有左孩子或者右孩子進行入隊。
472 if (current.left != null) {
473 queue.add(current.left);
474 }
475 // 如果目前節點有右孩子，就将目前節點的右孩子進行入隊操作。
476 if (current.right != null) {
477 queue.add(current.right);
478 }
479 }
480
481 }
482
483
484 /**
485 * 尋找二分搜尋樹的最小元素。
486 * <p>
487 * <p>
488 * 此時，使用遞歸的算法比寫非遞歸的算法，要麻煩一點，因為這裡相當于我們不停的隻想左走，
489 * 根本不考慮每一個節點的它的右子樹，或者是右孩子，那麼此時呢，我們跟操作一個連結清單是沒有差別的，
490 * 相當于我們在操作對于每一個節點的next就是node.left這樣的一個連結清單，找它的尾節點而已。
491 *
492 * @return
493 */
494 public E minimum() {
495 // 首先，判斷二分搜尋樹中元素個數為零，說明二分搜尋樹中沒有元素，就抛出異常。
496 if (size == 0) {
497 // 首先，判斷二分搜尋樹中元素個數為零，就抛出異常。
498 throw new IllegalArgumentException("BinarySearchTree is Empty.");
499 }
500
501 // 調用遞歸的方式進行查詢最小值
502 Node minimum = minimum(root);
503 // 此時将傳回的最小節點的元素值e傳回即可。
504 return minimum.e;
505 }
506
507 /**
508 * 傳回以node為根的二分搜尋樹的最小值所在的節點。
509 *
510 * @param node
511 */
512 private Node minimum(Node node) {
513 // 遞歸算法，第一個部分，遞歸終止的條件
514 // 如果向左走，走不動了，這個就是最左節點了，即最小值
515 if (node.left == null) {
516 return node;
517 } else {
518 // 遞歸算法，第二部分，即如果節點最左節點不為空
519 // 将這個節點的左孩子作為node傳遞進去，依次檢視最左節點的值。
520 return minimum(node.left);
521 }
522 }
523
524
525 /**
526 * 尋找二分搜尋樹的最大元素。
527 *
528 * @return
529 */
530 public E maximum() {
531 // 首先，判斷二分搜尋樹中元素個數為零，說明二分搜尋樹中沒有元素，就抛出異常。
532 if (size == 0) {
533 // 首先，判斷二分搜尋樹中元素個數為零，就抛出異常。
534 throw new IllegalArgumentException("BinarySearchTree is Empty.");
535 }
536
537 // 調用遞歸的方式進行查詢最大值
538 Node maximum = maximum(root);
539 // 此時将傳回的最大節點的元素值e傳回即可。
540 return maximum.e;
541 }
542
543 /**
544 * 傳回以node為根的二分搜尋樹的最大值所在的節點。
545 *
546 * @param node
547 */
548 private Node maximum(Node node) {
549 // 遞歸算法，第一個部分，遞歸終止的條件
550 // 如果向右走，走不動了，這個就是最右節點了，即最大值
551 if (node.right == null) {
552 return node;
553 } else {
554 // 遞歸算法，第二部分，即如果節點最右節點不為空
555 // 将這個節點的右孩子作為node傳遞進去，依次檢視最右節點的值。
556 return maximum(node.right);
557 }
558 }
559
560
561 /**
562 * 從二分搜尋樹中删除最小值所在節點，傳回最小值。
563 *
564 * @return
565 */
566 public E removeMin() {
567 // 将删除的元素删除掉
568 E ret = minimum();
569
570 // 設計删除最小值的邏輯。最小值所在的節點從二分搜尋樹中删除掉。
571 // 從根節點開始，嘗試從root節點開始，删除最小值所在的節點。
572
573 // 将删除最小值以後的節點傳回給root根節點。
574 // 換句話說，我們從root為根的二分搜尋樹删除掉了最小值，
575 // 之後又傳回了删除掉最小值之後的那棵二分搜尋樹對應的根節點。
576 // 這個根節點就是新的root。
577 root = removeMin(root);
578
579 // 最後，将待删除元素删除掉就行了。
580 return ret;
581 }
582
583 /**
584 * 删除掉以node為根的二分搜尋樹中的最小節點。
585 * 傳回删除節點後新的二分搜尋樹的根。
586 * <p>
587 * <p>
588 * 這個邏輯就是在這種情況下，删除node節點的左子樹對應的最小值，删除掉之後，對于我們目前
589 * 這個以node為根的二分搜尋樹，在做完這些操作之後，它的根節點依然是node，将它傳回回去。
590 *
591 * @param node
592 */
593 private Node removeMin(Node node) {
594 // 遞歸調用，遞歸到底，終止條件。
595 // 就是節點左子樹為空的時候，就是向左走，直到不能再走的時候，就終止條件
596 // 就是目前這個節點不能再向左走了，即目前這個節點就是最小值。
597 // 所在的節點，就是這個待删除的節點。
598 if (node.left == null) {
599 // 我們要删除目前這個節點，但是目前這個節點可能有右子樹的，則右子樹的部分不可以丢失掉。
600 // reightNode儲存目前節點的右子樹。
601 Node reightNode = node.right;
602 // 儲存目前節點的右子樹之後，就将目前節點的右子樹置空就行了。
603 // 将目前節點的右子樹和這個二分搜尋樹脫離關系。
604 node.right = null;
605 // 傳回儲存的右子樹，為什麼傳回這個呢，因為這個函數做的事情就是删除掉以node為根的二分搜尋樹中的最小節點，
606 // 傳回删除節點後新的二分搜尋樹的根，此時，最小節點就是node節點本身，将node删除掉之後，
607 // 新的二分搜尋樹的根就是node.right，就是node的右孩子，它就是node的右子樹對應的那個根節點。
608 // 如果node的右孩子為空，沒有關系，就說明node的右子樹為空，一棵空樹，它的根節點還是空。
609
610 // 維護size的大小。因為删除掉一個元素，是以要維護size的大小。
611 size--;
612 return reightNode;
613 // 這就是删除最小節點這個算法來說，遞歸到底的情況。
614 }
615
616
617 // 如果此時，沒有遞歸到底，就說明還有左孩子。
618 // 就是進行遞歸操作的第二部分就行了。去删除掉這個目前節點node的左子樹所對應的最小值。
619 // Node removeMin = removeMin(node.left);
620 // 删除掉以node為根的二分搜尋樹中的最小節點。
621 // 傳回删除節點後新的二分搜尋樹的根。
622 // 這樣才可以真正改變二分搜尋樹的結構。
623 // node.left = removeMin;
624 node.left = removeMin(node.left);
625
626 // 傳回目前節點
627 return node;
628 }
629
630
631 /**
632 * 從二分搜尋樹中删除最大值所在節點，傳回最大值。
633 * <p>
634 * 删除最大值，類比删除最小值的思路即可。
635 *
636 * @return
637 */
638 public E removeMax() {
639 // 将删除的元素删除掉
640 E ret = maximum();
641
642 root = removeMax(root);
643
644 // 最後，将待删除元素删除掉就行了。
645 return ret;
646 }
647
648
649 /**
650 * 删除掉以node為根的二分搜尋樹中的最大節點。
651 * 傳回删除節點後新的二分搜尋樹的根。
652 *
653 * @param node
654 */
655 private Node removeMax(Node node) {
656 // 當走到該節點最右孩子的時候，即最右孩子是空的時候，就走到了最底。
657 if (node.right == null) {
658 // 儲存目前節點的左子樹。因為對于目前節點，右子樹已經為空了。
659 // 删除掉這個節點之後，這個節點的左子樹的根節點就是新的根節點，
660 Node leftNode = node.left;
661 // 儲存目前節點的左子樹之後，就将目前節點的左子樹置空就行了。
662 // 将目前節點的左子樹和這個二分搜尋樹脫離關系。
663 node.left = null;
664 // 删除節點，維護size的大小
665 size--;
666 // 删除掉這個節點之後，那麼，這個節點的左子樹的根節點，就是新的根節點。
667 return leftNode;
668 }
669
670 // 如果遞歸沒有到到底的話，我們做的事情就是去删除目前這個節點右子樹中的最大值，
671 // 将最終的結果傳回給目前的這個節點的右孩子。然後傳回node節點。
672 node.right = removeMax(node.right);
673
674 // 傳回目前節點
675 return node;
676 }
677
678
679 /**
680 * 從二分搜尋樹中删除元素為e的節點。
681 *
682 * @param e
683 */
684 public void remove(E e) {
685 // 參數一是根節點，參數二是待删除元素
686
687 // 将删除掉元素e之後d得到的新的二分搜尋樹的根節點傳回回來
688 root = remove(root, e);
689 }
690
691 /**
692 * 删除掉以node為根的二分搜尋樹中值為e的節點，遞歸算法。
693 * 傳回删除節點後新的二分搜尋樹的根。
694 * <p>
695 * <p>
696 * 删除左右都有孩子的節點d，找到p = max(d -> node.left)。p是d的前驅。
697 * 此删除方法是找到待删除節點的後繼，也可以找到目前節點的前驅。
698 *
699 * @param node
700 * @param e
701 */
702 private Node remove(Node node, E e) {
703 // 如果node節點為空，直接傳回空即可。
704 // 另外一層含義，在二分搜尋樹中找這個元素為e的節點，根本沒有找到，最後找到node為空的位置了，
705 // 直接傳回空就行了。
706 if (node == null) {
707 return null;
708 }
709
710 // 遞歸函數，開始近邏輯
711 // 如果待删除元素e和目前節點的元素e進行比較，如果待删除元素e小于該節點的元素e
712 if (e.compareTo(node.e) < 0) {
713 // 此時，去該節點的左子樹，去找到待删除元素節點
714 // 遞歸調用，去node的左子樹，去删除這個元素e。
715 // 最後将删除的結果賦給該節點左子樹。
716 node.left = remove(node.left, e);
717 return node;
718 } else if (e.compareTo(node.e) > 0) {
719 // 如果待删除元素e大于該節點的元素e
720 // 去目前節點的右子樹去尋找待删除元素節點
721 // 将删除後的結果傳回給目前節點的右孩子
722 node.right = remove(node.right, e);
723 return node;
724 } else {
725 // 目前節點元素e等于待删除節點元素e，即e == node.e，
726 // 相等的時候，此時就是要删除這個節點的。
727
728 // 如果目前節點node的左子樹為空的時候，待删除節點左子樹為空的情況
729 if (node.left == null) {
730 // 儲存該節點的右子樹
731 Node rightNode = node.right;
732 // 将node和這棵樹斷開關系
733 node.right = null;
734 // 維護size的大小
735 size--;
736 // 傳回原來那個node的右孩子。也就是右子樹的根節點，此時就将node删除掉了
737 return rightNode;
738 }
739
740 // 如果目前節點的右子樹為空，待删除節點右子樹為空的情況。
741 if (node.right == null) {
742 // 儲存該節點的左子樹
743 Node leftNode = node.left;
744 // 将node節點和這棵樹斷開關系
745 node.left = null;
746 // 維護size的大小
747 size--;
748 //傳回原來那個節點node的左孩子，也就是左子樹的根節點，此時就将node删除掉了。
749 return leftNode;
750 }
751
752 // 待删除節點左右子樹均為不為空的情況。
753 // 核心思路，找到比待删除節點大的最小節點，即待删除節點右子樹的最小節點
754 // 用這個節點頂替待删除節點的位置。
755
756 // 找到目前節點node的右子樹中的最小節點，找到比待删除節點大的最小節點。
757 // 此時的successor就是node的後繼。
758 Node successor = minimum(node.right);
759 // 此時将目前節點node的右子樹中的最小節點删除掉，并将二分搜尋樹的根節點傳回。
760 // 将新的二分搜尋樹的根節點指派給後繼節點的右子樹。
761 successor.right = removeMin(node.left);
762
763 // 因為removeMin操作，删除了一個節點，但是此時目前節點的右子樹的最小值還未被删除
764 // 被successor後繼者指向了。是以這裡做一些size加加操作，
765 size++;
766
767 // 将目前節點的左子樹指派給後繼節點的左子樹上。
768 successor.left = node.left;
769 // 将node節點沒有用了，将node節點的左孩子和右孩子置空。讓node節點和二分搜尋樹脫離關系
770 node.left = node.right = null;
771
772 // 由于此時，将目前節點node删除掉了，是以這裡做一些size減減操作。
773 size--;
774
775 // 傳回後繼節點
776 return successor;
777 }
778
779 }
780
781
782 @Override
783 public String toString() {
784 StringBuilder stringBuilder = new StringBuilder();
785 // 使用一種形式展示整個二分搜尋樹，可以先展現根節點，再展現左子樹，再展現右子樹。
786 // 上述這種過程就是一個前序周遊的過程。
787 // 參數一，目前周遊的二分搜尋樹的根節點，初始調用的時候就是root。
788 // 參數二，目前周遊的這棵二分搜尋樹的它的深度是多少，根節點的深度是0。
789 // 參數三，将字元串傳入進去，為了友善生成字元串。
790 generateBSTString(root, 0, stringBuilder);
791
792 return stringBuilder.toString();
793 }
794
795 /**
796 * 生成以node為根節點，深度為depth的描述二叉樹的字元串。
797 *
798 * @param node 節點
799 * @param depth 深度
800 * @param stringBuilder 字元串
801 */
802 private void generateBSTString(Node node, int depth, StringBuilder stringBuilder) {
803 // 遞歸的第一部分
804 if (node == null) {
805 // 顯示的，将在字元串中追加一個空字元串null。
806 // 為了表現出目前的空節點對應的二分搜尋樹的層次，封裝了一個方法。
807 stringBuilder.append(generateDepthString(depth) + "null\n");
808 return;
809 }
810
811
812 // 遞歸的第二部分
813 // 當目前節點不為空的時候，就可以直接通路目前的node節點了。
814 // 将目前節點資訊放入到字元串了
815 stringBuilder.append(generateDepthString(depth) + node.e + "\n");
816
817 // 遞歸進行調用
818 generateBSTString(node.left, depth + 1, stringBuilder);
819 generateBSTString(node.right, depth + 1, stringBuilder);
820 }
821
822 /**
823 * 為了表現出二分搜尋樹的深度
824 *
825 * @param depth
826 * @return
827 */
828 private String generateDepthString(int depth) {
829 StringBuilder stringBuilder = new StringBuilder();
830 for (int i = 0; i < depth; i++) {
831 stringBuilder.append("--");
832 }
833 return stringBuilder.toString();
834 }
835
836
837 public static void main(String[] args) {
838 BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<Integer>();
839 int[] nums = new int[]{1, 5, 3, 6, 8, 4, 2};
840 // for (int i = 0; i < nums.length; i++) {
841 // // 二分搜尋樹的新增
842 // binarySearchTree.add(nums[i]);
843 // }
844 for (int num : nums) {
845 binarySearchTree.add(num);
846 }
847
848
849 // 二分搜尋樹的前序周遊
850 binarySearchTree.preOrder();
851 System.out.println();
852
853
854 // 二分搜尋樹的中序周遊
855 binarySearchTree.inOrder();
856 System.out.println();
857
858 // 二分搜尋樹的後序周遊
859 binarySearchTree.postOrder();
860 System.out.println();
861
862 // 二分搜尋樹的非遞歸的前序周遊。
863 binarySearchTree.preOrderNonRecursive();
864 System.out.println();
865
866 // 二分搜尋樹的非遞歸的層序周遊。
867 binarySearchTree.levelOrder();
868 System.out.println();
869
870 // 二分搜尋樹的遞歸的删除任意元素
871 System.out.println("二分搜尋樹的遞歸的删除任意元素.");
872 binarySearchTree.remove(5);
873 System.out.println(binarySearchTree);
874
875
876 // System.out.println(binarySearchTree.toString());
877 // 5
878 // --3
879 // ----2
880 // ------null
881 // ------null
882 // ----4
883 // ------null
884 // ------null
885 // --6
886 // ----null
887 // ----8
888 // ------null
889 // ------null
890
891
892 // 二分搜尋樹的遞歸的删除最小值
893 // BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<Integer>();
894 // Random random = new Random();
895 // int n = 1000;
896 // for (int i = 0; i < n; i++) {
897 // // 随機添加1000個0-10000之間的數字。有可能重複，總數可能小于1000
898 // binarySearchTree.add(random.nextInt(10000));
899 // }
900 //
901 // ArrayList<Integer> nums = new ArrayList<Integer>();
902 // while (!binarySearchTree.isEmpty()) {
903 // nums.add(binarySearchTree.removeMin());
904 // }
905 // System.out.println(nums);
906 //
907 // // 判斷是否是從小到大排序的
908 // for (int i = 1; i < nums.size(); i++) {
909 // if (nums.get(i - 1) > nums.get(i)) {
910 // throw new IllegalArgumentException("Error.");
911 // }
912 // }
913 // System.out.println("removeMin test completed.");
914
915
916 // 二分搜尋樹的遞歸的删除最大值
917 // BinarySearchTree<Integer> binarySearchTree2 = new BinarySearchTree<Integer>();
918 // Random random2 = new Random();
919 // int n2 = 1000;
920 // for (int i = 0; i < n2; i++) {
921 // // 随機添加1000個0-10000之間的數字。有可能重複，總數可能小于1000
922 // binarySearchTree2.add(random2.nextInt(10000));
923 // }
924 //
925 // ArrayList<Integer> nums2 = new ArrayList<Integer>();
926 // while (!binarySearchTree2.isEmpty()) {
927 // nums2.add(binarySearchTree2.removeMax());
928 // }
929 // System.out.println(nums2);
930 //
931 // // 判斷是否是從小到大排序的
932 // for (int i = 1; i < nums2.size(); i++) {
933 // if (nums2.get(i - 1) < nums2.get(i)) {
934 // throw new IllegalArgumentException("Error.");
935 // }
936 // }
937 // System.out.println("removeMax test completed.");
938
939 }
940
941 }