一、基本認識
1、資料結構與演算法的關系？
（1）資料結構（data structure）：
資料結構指的是 資料與資料 之間的結構關系，比如：陣列、佇列、哈希、樹 等結構，
（2）演算法：
演算法指的是 解決問題的步驟，
（3）兩者關系：
程式 = 資料結構 + 演算法，
解決問題可以有很多種方式，不同的演算法實作 會得到不同的結果，正確的資料結構 是 好演算法的基礎（演算法好壞取決于 如何利用合適的資料結構去 處理資料、解決問題），
（4）資料結構動態演示地址：
https://www.cs.usfca.edu/~galles/visualization/Algorithms.html
2、資料結構分類？
（1）分類：
資料結構 可以分為 兩種：線性資料結構、非線性資料結構，
（2）線性資料結構：
線性資料結構指的是 資料元素之間存在一對一的線性關系，比如：一維陣列、鏈表、佇列、堆疊，
其又可以分為：
順序存盤結構：指的是 使用一組地址連續的存盤單元 存盤資料元素 的結構，其每個元素節點僅用于 保存資料元素，比如：一維陣列，
鏈式存盤結構：指的是 可使用一組地址不連續的存盤單元 存盤資料元素 的結構，其每個元素節點 保存資料元素 以及 相鄰資料元素的地址 資訊，比如：鏈表，
（3）非線性資料結構：
非線性資料結構指的是 資料元素之間存在 一對多、多對多 的關系，比如：二維陣列、多維陣列、樹、圖 等，
3、時間復雜度、空間復雜度
（1）分析多個演算法執行時間：
事前估算時間：程式運行前，通過分析某個演算法的時間復雜度來判斷演算法解決問題是否合適，
事后統計時間：程式運行后，通過計算程式運行時間來判斷（容易被計算機硬體、軟體等影響），
注：
一般分析演算法都是采用 事前估算時間，即估算分析 演算法的 時間復雜度，
（2）時間頻度、時間復雜度：
時間頻度（ T(n) ）：
一個演算法中 陳述句執行的次數 稱為 陳述句頻度 或者 時間頻度，記為 T(n)，
通常 一個演算法花費的時間 與 演算法中 陳述句的執行次數 成正比，即 某演算法陳述句執行次數多，其花費時間就長，
時間復雜度（ O(f(n)) ）：
存在某個輔助函式 f(n)，當 n 接近無窮大時，若 T(n) / f(n) 的極限值為不等于零的常數，則稱 f(n) 為 T(n) 的同數量級函式，記為 T(n) = O(f(n))，稱 O(f(n)) 為演算法的漸進時間復雜度，簡稱 時間復雜度，
（3）通過 時間頻度（ T(n) ）推算 時間復雜度 （ O(f(n)) ）：
對于一個 T(n) 運算式，比如： T(n) = an^2 + bn + c，其推算為 O(n) 需要遵循以下規則：
rule1：使用常數 1 替代運算式中的常數，若運算式存在高階項，則忽略常數項，
即：若 T(n) = 8，則其時間復雜度為 O(1)，若 T(n) = n^2 + 8，則其時間復雜度為 O(n^2)，
rule2：只保留最高階項，忽略所有低次項，
即：T(n) = 3n^2 + n^4 + 3n，其時間復雜度為 O(n^4)，
rule3：去除最高階項的系數，
即：T(n) = 3n^2 + 4n^3，其時間復雜度為 O(n^3)，
注：
T(n) 運算式不同，但是其對應的時間復雜度可能相同，
比如：T(n) = n^2 + n 與 T(n) = 3n^2 + 1 的時間復雜度均為 O(n^2)，
（4）常見時間復雜度
【常見時間復雜度（由小到大排序如下）：】 O(1) < O(logn) < O(n) < O(nlogn) < O(n^2) < O(n^3) < O(n^k) < O(2^n) 注： 時間復雜度越大，演算法執行效率越低， 【常數階 O(1) ：】 演算法復雜度 與 問題規模無關， 比如： int a = 1; int b = 2; int c = a + b; 分析： 代碼中不存在回圈、遞回等結構，其時間復雜度即為 O(1)， 【對數階 O(logn) ：】 演算法復雜度 與 問題規模成對數關系， 比如： int i = 1; while(i < n) { i*=2; // 不斷乘 2 } 分析： 上述代碼中存在回圈，設回圈執行次數為 x，則回圈退出條件為 2^x >= n， 從而推算出 x = logn，此時 log 以 2 為底，即時間復雜度為 O(logn)， 【線性階 O(n) ：】 演算法復雜度 與 問題規模成線性關系， 比如： for(int i = 0; i < n; i++) { System.out.println(i); } 分析： 代碼中存在回圈，且回圈次數為 n，即時間頻度為 T(n)，從而時間復雜度為 O(n)， 【線性對數階 O(nlogn) ：】 演算法復雜度 與 問題規模成線性對數關系（回圈嵌套）， 比如： for(int j = 0; j < n; j++) { int i = 1; while(i < n) { i*=2; // 不斷乘 2 } } 分析： 代碼中回圈嵌套，完成 for 回圈需要執行 n 次，每次均執行 while 回圈 logn 次， 即總時間頻度為 T(nlogn)， 從而時間復雜度為 O(nlogn)， 【平方階 O(n^2) ：】 演算法復雜度 與 問題規模成平方關系（回圈嵌套）， 比如： for(int i = 0; i < n; i++) { for(int j = 0; j < n; j++) { System.out.println(i + j); } } 分析： 代碼中回圈嵌套，總時間頻度為 T(n*n)，即時間復雜度為 O(n^2) 【立方階 O(n^3) 、k 次方階 O(n^k) ：】 類似于平方階 O(n^2)，只是回圈嵌套的層數更多了， O(n^3) 表示三層回圈，O(n^K) 表示四層回圈， 【指數階 O(2^n) ：】 演算法復雜度 與 問題規模成指數關系（回圈嵌套）， 這個演算法的執行效率非常糟糕，一般都不考慮， 比如： int n = 3; for (int i = 0; i < Math.pow(2, n); i++) { System.out.println(i); } 分析： 上面回圈，總時間頻度為 T(2^n)，即時間復雜度為 O(2^n)，
（5）空間復雜度
空間復雜度 指的是演算法所需耗費的存盤空間，與時間復雜度類似，但其關注的是演算法執行所需占用的臨時空間（非陳述句執行次數），
一般演算法分析更看重 時間復雜度，即保證程式執行速度快，比如：快取 就是空間換時間，
二、基本資料結構以及代碼實作
1、稀疏陣列（Sparse Array）
（1）什么是稀疏陣列？
當陣列中 值為 0 的元素 大于 非 0 元素 且 非 0 元素 分布無規律時，可以使用 稀疏陣列 來表示該陣列，其將一個大陣列整理、壓縮成一個小陣列，用于節約磁盤空間，
注：
不一定必須為 值為 0 的元素，一般 同一元素在陣列中過多時即可，
使用 稀疏陣列 的目的是為了 壓縮陣列結構、節約磁盤空間（比如：一個二維陣列 a[10][10] 可以存盤 100 個元素，但是其只存盤了 3 個元素后，那么將會有 97 個空間被閑置，此時可以將 二維陣列 轉為 稀疏陣列 存盤，其最終轉換成 b[4][3] 陣列進行保存，即從 a[10][10] 的陣列 壓縮到 b[4][3]，從而減少空間浪費），
【舉例：】 定義二維陣列 a[4][5]，并存盤 3 個值如下： 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 1 0 0 此時，陣列中元素為 0 的個數大于 非 0 元素個數，所以可以作為 稀疏陣列 處理， 換種方式，比如 將 0 替換成 5 如下，也可以視為 稀疏陣列 處理， 5 5 5 5 5 5 1 5 2 5 5 5 5 5 5 5 5 1 5 5
（2）二維陣列轉為稀疏陣列：
【如何處理：】 Step1：先記錄陣列 有幾行幾列，有多少個不同的值， Step2：將不同的值 的元素 的 行、列、值 記錄在一個 小規模的 陣列中，從而將 大陣列 縮減成 小陣列， 【舉例：】 原二維陣列如下： 0 0 0 0 0 0 1 0 2 0 0 0 0 0 0 0 0 1 0 0 經過處理后變為 稀疏陣列 如下： 行 列 值 4 5 3 // 首先記錄原二維陣列 有 幾行、幾列、幾個不同值 1 1 1 // 表示原二維陣列中 a[1][1] = 1 1 3 2 // 表示原二維陣列中 a[1][3] = 2 3 2 1 // 表示原二維陣列中 a[3][2] = 1 可以看到，原二維陣列 a[4][5] 轉為 稀疏陣列 b[4][3]，空間得到利用、壓縮，
（3）二維陣列、稀疏陣列 互相轉換實作
【二維陣列 轉 稀疏陣列：】 Step1：遍歷原始二維陣列，得到 有效資料 個數 num， Step2：根據有效資料個數創建 稀疏陣列 a[num + 1][3]， Step3：將原二維陣列中有效資料存盤到 稀疏陣列中， 注： 稀疏陣列有 三列：分別為：行、 列、 值， 稀疏陣列 第一行 存盤的為 原二維陣列的行、列 以及 有效資料個數，其余行存盤 有效資料所在的 行、列、值， 所以陣列定義為 [num + 1][3] 【稀疏陣列 轉 二維陣列：】 Step1：讀取 稀疏陣列 第一行資料并創建 二維陣列 b[行][列]， Step2：讀取其余行，并賦值到新的二維陣列中， 【代碼實作：】 package com.lyh.array; import java.util.HashMap; import java.util.Map; public class SparseArray { public static void main(String[] args) { // 創建原始 二維陣列，定義為 4 行 10 列，并存盤 兩個 元素， int[][] arrays = new int[4][10]; arrays[1][5] = 8; arrays[2][3] = 7; // 遍歷輸出原始 二維陣列 System.out.println("原始二維陣列如下："); showArray(arrays); // 二維陣列 轉 稀疏陣列 System.out.println("\n二維陣列 轉 稀疏陣列如下："); int[][] sparseArray = arrayToSparseArray(arrays); showArray(sparseArray); // 稀疏陣列 再次 轉為 二維陣列 System.out.println("\n稀疏陣列 轉 二維陣列如下："); int[][] sparseToArray = sparseToArray(sparseArray); showArray(sparseToArray); } /** * 二維陣列 轉 稀疏陣列 * @param arrays 二維陣列 * @return 稀疏陣列 */ public static int[][] arrayToSparseArray(int[][] arrays) { // count 用于記錄有效資料個數 int count = 0; // HashMap 用于保存有效資料（把 行,列 用逗號分隔拼接作為 key，值作為 value） Map<String, Integer> map = new HashMap<>(); // 遍歷得到有效資料、以及總個數 for (int i = 0; i < arrays.length; i++) { for (int j = 0; j < arrays[i].length; j++) { if (arrays[i][j] != 0) { count++; map.put(i + "," + j, arrays[i][j]); } } } // 根據有效資料總個數定義 稀疏陣列，并賦值 int[][] result = new int[count + 1][3]; result[0][0] = arrays.length; result[0][1] = arrays[0].length; result[0][2] = count; // 把有效資料從 HashMap 中取出 并放到 稀疏陣列中 for(Map.Entry<String, Integer> entry : map.entrySet()) { String[] temp = entry.getKey().split(","); result[count][0] = Integer.valueOf(temp[0]); result[count][1] = Integer.valueOf(temp[1]); result[count][2] = entry.getValue(); --count; } return result; } /** * 遍歷輸出 二維陣列 * @param arrays 二維陣列 */ public static void showArray(int[][] arrays) { for (int[] a : arrays) { for (int data : a) { System.out.print(data + " "); } System.out.println(); } } /** * 稀疏陣列 轉 二維陣列 * @param arrays 稀疏陣列 * @return 二維陣列 */ public static int[][] sparseToArray(int[][] arrays) { int[][] result = new int[arrays[0][0]][arrays[0][1]]; for (int i = 1; i < arrays.length; i++) { result[arrays[i][0]][arrays[i][1]] = arrays[i][2]; } return result; } } 【輸出結果：】 原始二維陣列如下： 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 二維陣列 轉 稀疏陣列如下： 4 10 2 1 5 8 2 3 7 稀疏陣列 轉 二維陣列如下： 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 0 0 7 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
2、佇列（Queue）、環形佇列
（1）什么是佇列？
佇列指的是一種 受限的、線性的資料結構，其僅允許在 一端進行插入操作（隊尾插入，rear），且在另一端進行 洗掉操作（隊首洗掉，front），
佇列可以使用 陣列 或者 鏈表 實作（一般采用陣列實作，僅在首尾增刪，效率比鏈表高），
其遵循 先進先出（First In First Out，FIFO） 原則，即先存入 佇列的值 先取出，
【使用 陣列實作 佇列：】 需要注意三個值： maxSize： 表示佇列最大容量， front： 表示佇列頭元素下標（指向佇列頭部的第一個元素的前一個位置），初始值為 -1. rear： 表示佇列尾元素下標（指向佇列尾部的最后一個元素），初始值為 -1， 臨界條件： front == rear 時，表示佇列為 空， rear == maxSize - 1 時，表示佇列已滿， rear - front， 表示佇列的存盤元素的個數， 資料進入佇列時： front 不動，rear++， 資料出佇列時： rear 不動，front++，
如下圖：
紅色表示入隊操作，rear 加 1，
黃色表示出隊操作，front 加 1，
每次入隊，向當前實際陣列尾部添加元素，每次出隊，從當前實際陣列頭部取出元素，符合 先進先出原則，
可以很明顯的看到，如果按照這種方式實作佇列，黃色區域的空間將不會被再次使用，即此時的佇列是一次性的，
那么如何重復利用 黃色區域的空間？可以采用 環形佇列實作（看成一個環來實作），
環形佇列在 上面佇列的基礎上稍作修改，當成環處理（資料首尾相連，可以通過 % 進行取模運算實作），核心是考慮 佇列 什么時候為空，什么時候為滿，
一般采用 犧牲一個 陣列空間 作為判斷當前佇列是否已滿的條件，
【使用 陣列 實作環形佇列：（此處僅供參考）】 需要注意三個值： maxSize： 表示佇列最大容量， front： 表示佇列頭元素下標（指向佇列頭部的第一個元素），初始值為 0， rear： 表示佇列尾元素下標（指向佇列尾部的最后一個元素的后一個位置），初始值為 0， 臨界條件： front == rear 時，表示佇列為 空， (rear + 1) % maxSize == front 時，表示佇列已滿， (rear - front + maxSize) % maxSize， 表示佇列的存盤元素的個數， 資料進入佇列時： front 不動，rear = (rear + 1) % maxSize， 資料出佇列時： rear 不動，front = (front + 1) % maxSize，
（2）使用陣列實作佇列
【代碼實作：】 package com.lyh.queue; public class ArrayQueue<E> { private int maxSize; // 佇列最大容量 private int front; // 佇列首元素 private int rear; // 佇列尾元素 private Object[] queue; // 存盤佇列 /** * 構造初始佇列 * @param maxSize 佇列最大容量 */ public ArrayQueue(int maxSize) { this.maxSize = maxSize; queue = new Object[maxSize]; front = -1; rear = -1; } /** * 添加資料進入佇列 * @param e 待入資料 */ public void addQueue(E e) { if (isFull()) { System.out.println("佇列已滿"); return; } // 佇列未滿時，添加資料，rear 向后移動一位 queue[++rear] = e; } /** * 從佇列中取出資料 * @return 待取資料 */ public E getQueue() { if (isEmpty()) { System.out.println("佇列已空"); return null; } // 佇列不空時，取出資料，front 向后移動一位 return (E)queue[++front]; } /** * 輸出當前佇列所有元素 */ public void showQueue() { if (isEmpty()) { System.out.println("佇列已空"); return; } System.out.print("當前佇列存盤元素總個數為：" + getSize() + " 當前佇列為："); for(int i = front + 1; i <= rear; i++) { System.out.print(queue[i] + " "); } System.out.println(); } /** * 獲取當前佇列實際大小 * @return 佇列實際存盤資料數量 */ public int getSize() { return rear - front; } /** * 判斷佇列是否為空 * @return true 為空 */ public boolean isEmpty() { return front == rear; } /** * 判斷佇列是否已滿 * @return true 已滿 */ public boolean isFull() { return rear == maxSize - 1; } public static void main(String[] args) { // 創建佇列 ArrayQueue<Integer> arrayQueue = new ArrayQueue<>(6); // 添加資料 arrayQueue.addQueue(10); arrayQueue.addQueue(8); arrayQueue.addQueue(9); arrayQueue.showQueue(); // 取資料 System.out.println(arrayQueue.getQueue()); System.out.println(arrayQueue.getQueue()); arrayQueue.showQueue(); } } 【輸出結果：】 當前佇列存盤元素總個數為：3 當前佇列為：10 8 9 10 8 當前佇列存盤元素總個數為：1 當前佇列為：9
（3）使用陣列實作環形佇列
【代碼實作：】 package com.lyh.queue; public class ArrayCircleQueue<E> { private int maxSize; // 佇列最大容量 private int front; // 佇列首元素 private int rear; // 佇列尾元素 private Object[] queue; // 存盤佇列 /** * 構造初始佇列 * @param maxSize 佇列最大容量 */ public ArrayCircleQueue(int maxSize) { this.maxSize = maxSize; queue = new Object[maxSize]; front = 0; rear = 0; } /** * 添加資料進入佇列 * @param e 待入資料 */ public void addQueue(E e) { if (isFull()) { System.out.println("佇列已滿"); return; } // 佇列未滿時，添加資料，rear 向后移動一位 queue[rear] = e; rear = (rear + 1) % maxSize; } /** * 從佇列中取出資料 * @return 待取資料 */ public E getQueue() { if (isEmpty()) { System.out.println("佇列已空"); return null; } // 佇列不空時，取出資料，front 向后移動一位 E result = (E)queue[front]; front = (front + 1) % maxSize; return result; } /** * 輸出當前佇列所有元素 */ public void showQueue() { if (isEmpty()) { System.out.println("佇列已空"); return; } System.out.print("當前佇列存盤元素總個數為：" + getSize() + " 當前佇列為："); for(int i = front; i < front + getSize(); i++) { System.out.print(queue[i] + " "); } System.out.println(); } /** * 獲取當前佇列實際大小 * @return 佇列實際存盤資料數量 */ public int getSize() { return (rear - front + maxSize) % maxSize; } /** * 判斷佇列是否為空 * @return true 為空 */ public boolean isEmpty() { return front == rear; } /** * 判斷佇列是否已滿 * @return true 已滿 */ public boolean isFull() { return (rear + 1) % maxSize == front; } public static void main(String[] args) { // 創建佇列 ArrayCircleQueue<Integer> arrayQueue = new ArrayCircleQueue<>(3); // 添加資料 arrayQueue.addQueue(10); arrayQueue.addQueue(8); arrayQueue.addQueue(9); arrayQueue.showQueue(); // 取資料 System.out.println(arrayQueue.getQueue()); System.out.println(arrayQueue.getQueue()); arrayQueue.showQueue(); } } 【輸出結果：】 佇列已滿 當前佇列存盤元素總個數為：2 當前佇列為：10 8 10 8 佇列已空
3、鏈表（Linked list）-- 單鏈表 以及 常見筆試題
（1）什么是鏈表？
鏈表指的是 物理上非連續、非順序，但是 邏輯上 有序 的 線性的資料結構，
鏈表 由 一系列節點 組成，節點之間通過指標相連，每個節點只有一個前驅節點、只有一個后續節點，節點包含兩部分：存盤資料元素的資料域 （data）、存盤下一個節點的指標域 （next)，
可以使用 陣列、指標 實作，比如：Java 中 ArrayList 以及 LinkedList，
（2）單鏈表實作？
單鏈表 指的是 單向鏈表，首節點沒有前驅節點，尾節點沒有后續節點，只能沿著一個方向進行 遍歷、獲取資料的操作（即某個節點無法獲取上一個節點的資料），
可參考：https://www.cnblogs.com/l-y-h/p/11385295.html
注：
頭節點（非必須）：僅用于作為鏈表起點，放在鏈表第一個節點前，無實際意義，
首節點：指鏈表第一個節點，即頭節點后面的第一個節點，
頭節點是非必須的，使用頭節點是方便操作鏈表而設立的，如下代碼實作采用 頭節點 方式實作，
【模擬 指標形式 實作 單鏈表：】 模擬節點： 節點包括 資料域（保存資料） 以及 指標域（指向下一個節點）， class Node<E> { E data; // 資料域，存盤節點資料 Node next; // 指標域，指向下一個節點 public Node(E data) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } public Node(E data, Node<E> next) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; this.next = next; } } 【增刪節點：】 直接添加節點 A 到鏈表末尾： 先得遍歷得到最后一個節點 B 所在位置，條件為： B.next == null， 然后將最后一個節點 B 的 next 指向該節點， 即 B.next = A， 向指定位置插入節點： 比如： A->B 中插入 C， 即 A->C->B，此時，先讓 C 指向 B，再讓 A 指向 C， 即 C.next = A.next; // 此時 A.next = B A.next = C; 直接洗掉鏈表末尾節點： 先遍歷到倒數第二個節點 C 位置，條件為：C.next.next == null; 然后將其指向的下一個節點置為 null 即可，即 C.next = null， 洗掉指定位置的節點： 比如： A->C->B 中洗掉 C，此時，直接讓 A 指向 B， 即： A.next = C.next;
【代碼實作：】 package com.lyh.com.lyh.linkedlist; public class SingleLinkedList<E> { private int size; // 用于保存鏈表實際長度 private Node<E> header; // 用于保存鏈表頭節點，僅用作 起點，不存盤資料， public SingleLinkedList(Node<E> header) { this.header = header; } /** * 在鏈表末尾添加節點 * @param data 節點資料 */ public void addLastNode(E data) { Node<E> newNode = new Node<>(data); // 根據資料創建一個 新節點 Node<E> temp = header; // 使用臨時變數保存頭節點，用于輔助遍歷鏈表 // 遍歷鏈表 while(temp.next != null) { temp = temp.next; } // 在鏈表末尾添加節點，鏈表長度加 1 temp.next = newNode; size++; } /** * 在鏈表末尾添加節點 * @param newNode 節點 */ public void addLastNode(Node<E> newNode) { Node<E> temp = header; // 使用臨時變數保存頭節點，用于輔助遍歷鏈表 // 遍歷鏈表 while(temp.next != null) { temp = temp.next; } // 在鏈表末尾添加節點，鏈表長度加 1 temp.next = newNode; size++; } /** * 在鏈表指定位置 插入節點 * @param node 待插入節點 * @param index 指定位置（1 ~ n， 1 表示第一個節點位置） */ public void insert(Node<E> node, int index) { Node<E> temp = header; // 使用臨時變數保存頭節點，用于輔助遍歷鏈表 // 節點越界則拋出例外 if (index < 1 || index > size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } // 若節點為鏈表末尾，則呼叫 末尾添加 節點的方法 if (index == size) { addLastNode(node); return; } // 若節點不是鏈表末尾，則遍歷找到插入位置 while(index != 1) { temp = temp.next; index--; } // A -> B 變為 A -> C -> B， 即 A.next = B 變為 C.next = A.next, A.next = C，即 A 指向 C，C 指向 B， node.next = temp.next; temp.next = node; size++; } /** * 回傳鏈表長度 * @return 鏈表長度 */ public int size() { return size; } /** * 輸出鏈表 */ public void showList() { Node<E> temp = header.next; // 使用臨時變數保存第一個節點，用于輔助遍歷鏈表 if (size == 0) { System.out.println("當前鏈表為空"); return; } // 鏈表不為空時遍歷鏈表 System.out.print("當前鏈表長度為： " + size + " 當前鏈表為： "); while(temp != null) { System.out.print(temp + " ===> "); temp = temp.next; } System.out.println(); } /** * 洗掉最后一個節點 */ public void deleteLastNode() { Node<E> temp = header; // 使用臨時變數保存頭節點，用于遍歷鏈表 if (size == 0) { System.out.println("當前鏈表為空，無需洗掉"); return; } while(temp.next.next != null) { temp = temp.next; } temp.next = null; size--; } /** * 洗掉指定位置的元素 * @param index 指定位置（1 ~ n， 1 表示第一個節點位置） */ public void delete(int index) { Node<E> temp = header; // 使用臨時變數保存頭節點，用于輔助遍歷鏈表 // 節點越界則拋出例外 if (index < 1 || index > size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } // 若節點為鏈表末尾，則呼叫 末尾洗掉 節點的方法 if (index == size) { deleteLastNode(); return; } // 遍歷鏈表，找到洗掉位置 while(index != 1) { index--; temp = temp.next; } // A -> C -> B 變為 A -> B，即 A.next = C, C.next = B 變為 A.next = C.next，即 A 直接指向 B temp.next = temp.next.next; size--; } public static void main(String[] args) { // 創建一個單鏈表 SingleLinkedList<String> singleLinkedList = new SingleLinkedList(new Node("Header")); // 輸出，此時鏈表為空 singleLinkedList.showList(); System.out.println("======================================="); // 給鏈表添加資料 singleLinkedList.addLastNode("Java"); singleLinkedList.addLastNode(new Node<>("JavaScript")); singleLinkedList.insert(new Node<>("Phthon"), 1); singleLinkedList.insert(new Node<>("C"), 3); // 輸出鏈表 singleLinkedList.showList(); System.out.println("======================================="); // 洗掉鏈表資料 singleLinkedList.deleteLastNode(); singleLinkedList.delete(2); // 輸出鏈表 singleLinkedList.showList(); System.out.println("======================================="); } } class Node<E> { E data; // 資料域，存盤節點資料 Node<E> next; // 指標域，指向下一個節點 public Node(E data) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } public Node(E data, Node<E> next) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; this.next = next; } @Override public String toString() { return "Node{ data = "https://www.cnblogs.com/l-y-h/archive/2020/09/29/+ data +" }"; } } 【輸出結果：】 當前鏈表為空 ======================================= 當前鏈表長度為： 4 當前鏈表為： Node{ data = https://www.cnblogs.com/l-y-h/archive/2020/09/29/Phthon } ===> Node{ data = Java } ===> Node{ data = JavaScript } ===> Node{ data = C } ===> ======================================= 當前鏈表長度為： 2 當前鏈表為： Node{ data = https://www.cnblogs.com/l-y-h/archive/2020/09/29/Phthon } ===> Node{ data = JavaScript } ===> =======================================
（3）常見的單鏈表筆試題
【筆試題一：】 找到當前鏈表中倒數 第 K 個節點， 【筆試題一解決思路：】 思路一： 鏈表長度 size 可知時，則可以遍歷 size - k 個節點，從而找到倒數第 K 個節點， 當然 size 可以通過遍歷一遍鏈表得到，這會消耗時間， 思路二： 鏈表長度 size 未知時，可使用 快慢指標 解決， 使用兩個指標 A、B 同時遍歷，且指標 B 始終比指標 A 快 K 個節點， 當 指標 B 遍歷到鏈表末尾時，此時 指標 A 指向的下一個節點即為倒數第 K 個節點， 【核心代碼如下：】 /** * 獲取倒數第 K 個節點， * 方式一： * size 可知，遍歷 size - k 個節點即可 * @param k K 值，（1 ~ n，1 表示倒數第一個節點） * @return 倒數第 K 個節點 */ public Node<E> getLastKNode(int k) { Node<E> temp = header.next; // 使用臨時變數存盤第一個節點，用于輔助鏈表遍歷 // 判斷節點是否越界 if (k < 1 || k > size) { throw new IndexOutOfBoundsException("Index: " + k + ", Size: " + size); } // 遍歷 size - k 個節點，即可找到倒數第 K 個節點 for (int i = 0; i < size - k; i++) { temp = temp.next; } return temp; } /** * 獲取倒數第 K 個節點， * 方式二： * size 未知時，使用快慢節點， * 節點 A 比節點 B 始終快 k 個節點，A,B 同時向后遍歷，當 A 遍歷完成后，B 遍歷的位置下一個位置即為倒數第 K 個節點， * @param k K 值，（1 ~ n，1 表示倒數第一個節點） * @return 倒數第 K 個節點 */ public Node<E> getLastKNode2(int k) { Node<E> tempA = header; // 使用臨時變數存盤頭節點，用于輔助鏈表遍歷 Node<E> tempB = header; // 使用臨時變數存盤頭節點，用于輔助鏈表遍歷 // 節點越界判斷 if (k < 1) { throw new IndexOutOfBoundsException("Index: " + k); } // A 比 B 快 K 個節點 while(tempA.next != null && k != 0) { tempA = tempA.next; k--; } // 節點越界判斷 if (k != 0) { throw new IndexOutOfBoundsException("K 值大于鏈表長度"); } // 遍歷，當 A 到鏈表末尾時，B 所處位置下一個位置即為倒數第 K 個節點 while(tempA.next != null) { tempA = tempA.next; tempB = tempB.next; } return tempB.next; }
【筆試題二：】 找到當前鏈表的中間節點（鏈表長度未知）， 【筆試題二解決思路：】 鏈表長度未知，可以采用 快慢指標 方式解決， 此處與解決 上題 倒數第 K 個節點類似，只是此時節點 B 比 節點 A 每次都快 1 個節點（即 A 每次遍歷移動一個節點，B 會遍歷移動兩個節點）， 【核心代碼如下：】 /** * 鏈表長度未知時，獲取鏈表中間節點 * @return 鏈表中間節點 */ public Node<E> getHalfNode() { Node<E> tempA = header.next; // 使用臨時變數保存第一個節點，用于輔助遍歷鏈表 Node<E> tempB = header.next; // 使用臨時變數保存第一個節點，用于輔助遍歷鏈表 // 回圈遍歷 B 節點，B 節點每次都比 A 節點快一個節點（每次多走一個節點），所以當 B 遍歷完成后，A 節點所處位置即為中間節點， while(tempB.next != null && tempB.next.next != null) { tempA = tempA.next; tempB = tempB.next.next; } return tempA; }
【筆試題三：】 反轉鏈表， 【筆試題三解決思路：】 思路一： 頭插法，新建一個鏈表，遍歷原始鏈表，將每個節點通過頭插法插入新鏈表， 頭插法，即每次均在第一個節點位置處進行插入操作， 思路二： 直接反轉， 通過三個指標來輔助，beforeNode、currentNode、afterNode，此時 beforeNode -> currentNode -> afterNode， 其中： beforeNode 為當前節點上一個節點， currentNode 為當前節點， afterNode 為當前節點下一個節點， 遍歷鏈表，使 currentNode -> beforeNode， 【核心代碼如下：】 /** * 鏈表反轉， * 方式一： * 頭插法，新建一個鏈表，遍歷原始鏈表，將每個節點通過頭插法插入新鏈表， * @return */ public SingleLinkedList<E> reverseList() { Node<E> temp = header.next; // 使用臨時變數存盤第一個節點，用于輔助遍歷原鏈表 SingleLinkedList singleLinkedList = new SingleLinkedList(new Node("newHeader")); // 新建一個鏈表 // 若原鏈表為空，則直接回傳 空的 新鏈表 if (temp == null) { return singleLinkedList; } // 遍歷原鏈表，并呼叫新鏈表的 頭插法添加節點 while(temp != null) { singleLinkedList.addFirstNode(new Node(temp.data)); temp = temp.next; } return singleLinkedList; } /** * 頭插法插入節點，每次均在第一個節點位置處進行插入 * @param node 待插入節點 */ public void addFirstNode(Node<E> node) { Node<E> temp = header.next; // 使用臨時變數保存第一個節點，用于輔助遍歷鏈表 // 若鏈表為空，則直接賦值即可 if (temp == null) { header.next = node; size++; return; } // 若鏈表不為空，則在第一個節點位置進行插入 node.next = temp; header.next = node; size++; } /** * 鏈表反轉， * 方式二： * 直接反轉，通過三個指標進行輔助，此方式會直接變化當前鏈表， */ public void reverseList2() { // 鏈表為空直接回傳 if (header.next == null) { System.out.println("當前鏈表為空"); return; } Node<E> beforeNode = null; // 指向當前節點的上個節點 Node<E> currentNode = header.next; // 指向當前節點 Node<E> afterNode = null; // 指向當前節點的下一個節點 // 遍歷節點 while(currentNode != null) { afterNode = currentNode.next; // 獲取當前節點的下一個節點 currentNode.next = beforeNode; // 將當前節點指向上一個節點 beforeNode = currentNode; // 上一個節點后移 currentNode = afterNode; // 當前節點后移，為了下一個遍歷 } header.next = beforeNode; // 遍歷結束后，beforeNode 為最后一個節點，使用 頭節點 指向該節點，即可完成鏈表反轉 }
【筆試題四：】 列印輸出反轉鏈表，不能反轉原鏈表， 【筆試題四解決思路：】 思路一（此處不重復演示，詳見上例代碼）： 由于不能反轉原鏈表，可以與上例頭插法相同， 新建一個鏈表并使用頭插法添加節點，最后遍歷輸出新鏈表， 思路二： 使用堆疊進行輔助，堆疊屬于先進后出結構， 可以先遍歷鏈表并存入堆疊中，然后依次取出堆疊頂元素即可， 思路三： 使用陣列進行輔助（有序結構存盤一般均可，比如 TreeMap 存盤，根據 key 倒序輸出亦可）， 遍歷鏈表并存入陣列，然后反序輸出陣列即可（注：若是反序存入陣列，可以順序輸出）， 【核心代碼如下：】 /** * 不改變當前鏈表下，反序輸出鏈表， * 方式一： * 借用堆疊結構進行輔助，堆疊是先進后出結構， * 先遍歷鏈表并依次存入堆疊，然后從堆疊頂挨個取出資料，即可得到反序鏈表， */ public void printReverseList() { Node<E> temp = header.next; // 使用臨時變數保存第一個節點，用于輔助鏈表遍歷 Stack<Node<E>> stack = new Stack(); // 使用堆疊存盤節點 // 判斷鏈表是否為空 if (temp == null) { System.out.println("當前鏈表為空"); return; } // 遍歷節點，使用堆疊存盤鏈表各節點， while(temp != null) { stack.push(temp); temp = temp.next; } // 遍歷輸出堆疊 while(stack.size() > 0) { System.out.print(stack.pop() + "==>"); } System.out.println(); } /** * 不改變當前鏈表下，反序輸出鏈表， * 方式二： * 采用陣列輔助， * 遍歷鏈表存入陣列，最后反序輸出陣列即可（注：若是反序存入陣列，可以順序輸出）， */ public void printReverseList2() { Node<E> temp = header.next; // 使用臨時變數保存第一個節點，用于輔助鏈表遍歷 int length = size(); Node<E>[] nodes = new Node[length]; // 使用陣列存盤鏈表節點 // 判斷鏈表是否為空 if(temp == null) { System.out.println("當前鏈表為空"); return; } // 遍歷鏈表，存入陣列，此處反序存入陣列，后面順序輸出即可 while(temp != null) { nodes[--length] = temp; temp = temp.next; } System.out.println(Arrays.toString(nodes)); }
上述所有單鏈表相關代碼完整版如下（有部分地方還需修改，僅供參考）：
【代碼：】 package com.lyh.com.lyh.linkedlist; import java.util.Arrays; import java.util.Stack; public class SingleLinkedList<E> { private int size; // 用于保存鏈表實際長度 private Node<E> header; // 用于保存鏈表頭節點，僅用作 起點，不存盤資料， public SingleLinkedList(Node<E> header) { this.header = header; } /** * 在鏈表末尾添加節點 * @param data 節點資料 */ public void addLastNode(E data) { Node<E> newNode = new Node<>(data); // 根據資料創建一個 新節點 Node<E> temp = header; // 使用臨時變數保存頭節點，用于輔助遍歷鏈表 // 遍歷鏈表 while(temp.next != null) { temp = temp.next; } // 在鏈表末尾添加節點，鏈表長度加 1 temp.next = newNode; size++; } /** * 在鏈表末尾添加節點 * @param newNode 節點 */ public void addLastNode(Node<E> newNode) { Node<E> temp = header; // 使用臨時變數保存頭節點，用于輔助遍歷鏈表 // 遍歷鏈表 while(temp.next != null) { temp = temp.next; } // 在鏈表末尾添加節點，鏈表長度加 1 temp.next = newNode; size++; } /** * 在鏈表指定位置 插入節點 * @param node 待插入節點 * @param index 指定位置（1 ~ n， 1 表示第一個節點位置） */ public void insert(Node<E> node, int index) { Node<E> temp = header; // 使用臨時變數保存頭節點，用于輔助遍歷鏈表 // 節點越界則拋出例外 if (index < 1 || index > size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } // 若節點為鏈表末尾，則呼叫 末尾添加 節點的方法 if (index == size) { addLastNode(node); return; } // 若節點不是鏈表末尾，則遍歷找到插入位置 while (index != 1) { temp = temp.next; index--; } // A -> B 變為 A -> C -> B， 即 A.next = B 變為 C.next = A.next, A.next = C，即 A 指向 C，C 指向 B， node.next = temp.next; temp.next = node; size++; } /** * 回傳鏈表長度 * @return 鏈表長度 */ public int size() { return size; } /** * 輸出鏈表 */ public void showList() { Node<E> temp = header.next; // 使用臨時變數保存第一個節點，用于輔助遍歷鏈表 if (size == 0) { System.out.println("當前鏈表為空"); return; } // 鏈表不為空時遍歷鏈表 System.out.print("當前鏈表長度為： " + size + " 當前鏈表為： "); while(temp != null) { System.out.print(temp + " ===> "); temp = temp.next; } System.out.println(); } /** * 洗掉最后一個節點 */ public void deleteLastNode() { Node<E> temp = header; // 使用臨時變數保存頭節點，用于遍歷鏈表 if (size == 0) { System.out.println("當前鏈表為空，無需洗掉"); return; } while(temp.next.next != null) { temp = temp.next; } temp.next = null; size--; } /** * 洗掉指定位置的元素 * @param index 指定位置（1 ~ n， 1 表示第一個節點位置） */ public void delete(int index) { Node<E> temp = header; // 使用臨時變數保存頭節點，用于輔助遍歷鏈表 // 節點越界則拋出例外 if (index < 1 || index > size) { throw new IndexOutOfBoundsException("Index: " + index + ", Size: " + size); } // 若節點為鏈表末尾，則呼叫 末尾洗掉 節點的方法 if (index == size) { deleteLastNode(); return; } // 遍歷鏈表，找到洗掉位置 while(index != 1) { index--; temp = temp.next; } // A -> C -> B 變為 A -> B，即 A.next = C, C.next = B 變為 A.next = C.next，即 A 直接指向 B temp.next = temp.next.next; size--; } /** * 獲取倒數第 K 個節點， * 方式一： * size 可知，遍歷 size - k 個節點即可 * @param k K 值，（1 ~ n，1 表示倒數第一個節點） * @return 倒數第 K 個節點 */ public Node<E> getLastKNode(int k) { Node<E> temp = header.next; // 使用臨時變數存盤第一個節點，用于輔助鏈表遍歷 // 判斷節點是否越界 if (k < 1 || k > size) { throw new IndexOutOfBoundsException("Index: " + k + ", Size: " + size); } // 遍歷 size - k 個節點，即可找到倒數第 K 個節點 for (int i = 0; i < size - k; i++) { temp = temp.next; } return temp; } /** * 獲取倒數第 K 個節點， * 方式二： * size 未知時，使用快慢節點， * 節點 A 比節點 B 始終快 k 個節點，A,B 同時向后遍歷，當 A 遍歷完成后，B 遍歷的位置下一個位置即為倒數第 K 個節點， * @param k K 值，（1 ~ n，1 表示倒數第一個節點） * @return 倒數第 K 個節點 */ public Node<E> getLastKNode2(int k) { Node<E> tempA = header; // 使用臨時變數存盤頭節點，用于輔助鏈表遍歷 Node<E> tempB = header; // 使用臨時變數存盤頭節點，用于輔助鏈表遍歷 // 節點越界判斷 if (k < 1) { throw new IndexOutOfBoundsException("Index: " + k); } // A 比 B 快 K 個節點 while(tempA.next != null && k != 0) { tempA = tempA.next; k--; } // 節點越界判斷 if (k != 0) { throw new IndexOutOfBoundsException("K 值大于鏈表長度"); } // 遍歷，當 A 到鏈表末尾時，B 所處位置下一個位置即為倒數第 K 個節點 while(tempA.next != null) { tempA = tempA.next; tempB = tempB.next; } return tempB.next; } /** * 鏈表長度未知時，獲取鏈表中間節點 * @return 鏈表中間節點 */ public Node<E> getHalfNode() { Node<E> tempA = header.next; // 使用臨時變數保存第一個節點，用于輔助遍歷鏈表 Node<E> tempB = header.next; // 使用臨時變數保存第一個節點，用于輔助遍歷鏈表 // 回圈遍歷 B 節點，B 節點每次都比 A 節點快一個節點（每次多走一個節點），所以當 B 遍歷完成后，A 節點所處位置即為中間節點， while(tempB.next != null && tempB.next.next != null) { tempA = tempA.next; tempB = tempB.next.next; } return tempA; } /** * 鏈表反轉， * 方式一： * 頭插法，新建一個鏈表，遍歷原始鏈表，將每個節點通過頭插法插入新鏈表， * @return */ public SingleLinkedList<E> reverseList() { Node<E> temp = header.next; // 使用臨時變數存盤第一個節點，用于輔助遍歷原鏈表 SingleLinkedList singleLinkedList = new SingleLinkedList(new Node("newHeader")); // 新建一個鏈表 // 若原鏈表為空，則直接回傳 空的 新鏈表 if (temp == null) { return singleLinkedList; } // 遍歷原鏈表，并呼叫新鏈表的 頭插法添加節點 while(temp != null) { singleLinkedList.addFirstNode(new Node(temp.data)); temp = temp.next; } return singleLinkedList; } /** * 頭插法插入節點，每次均在第一個節點位置處進行插入 * @param node 待插入節點 */ public void addFirstNode(Node<E> node) { Node<E> temp = header.next; // 使用臨時變數保存第一個節點，用于輔助遍歷鏈表 // 若鏈表為空，則直接賦值即可 if (temp == null) { header.next = node; size++; return; } // 若鏈表不為空，則在第一個節點位置進行插入 node.next = temp; header.next = node; size++; } /** * 鏈表反轉， * 方式二： * 直接反轉，通過三個指標進行輔助，此方式會直接變化當前鏈表， */ public void reverseList2() { // 鏈表為空直接回傳 if (header.next == null) { System.out.println("當前鏈表為空"); return; } Node<E> beforeNode = null; // 指向當前節點的上個節點 Node<E> currentNode = header.next; // 指向當前節點 Node<E> afterNode = null; // 指向當前節點的下一個節點 // 遍歷節點 while(currentNode != null) { afterNode = currentNode.next; // 獲取當前節點的下一個節點 currentNode.next = beforeNode; // 將當前節點指向上一個節點 beforeNode = currentNode; // 上一個節點后移 currentNode = afterNode; // 當前節點后移，為了下一個遍歷 } header.next = beforeNode; // 遍歷結束后，beforeNode 為最后一個節點，使用 頭節點 指向該節點，即可完成鏈表反轉 } /** * 不改變當前鏈表下，反序輸出鏈表， * 方式一： * 借用堆疊結構進行輔助，堆疊是先進后出結構， * 先遍歷鏈表并依次存入堆疊，然后從堆疊頂挨個取出資料，即可得到反序鏈表， */ public void printReverseList() { Node<E> temp = header.next; // 使用臨時變數保存第一個節點，用于輔助鏈表遍歷 Stack<Node<E>> stack = new Stack(); // 使用堆疊存盤節點 // 判斷鏈表是否為空 if (temp == null) { System.out.println("當前鏈表為空"); return; } // 遍歷節點，使用堆疊存盤鏈表各節點， while(temp != null) { stack.push(temp); temp = temp.next; } // 遍歷輸出堆疊 while(stack.size() > 0) { System.out.print(stack.pop() + "==>"); } System.out.println(); } /** * 不改變當前鏈表下，反序輸出鏈表， * 方式二： * 采用陣列輔助， * 遍歷鏈表存入陣列，最后反序輸出陣列即可（注：若是反序存入陣列，可以順序輸出）， */ public void printReverseList2() { Node<E> temp = header.next; // 使用臨時變數保存第一個節點，用于輔助鏈表遍歷 int length = size(); Node<E>[] nodes = new Node[length]; // 使用陣列存盤鏈表節點 // 判斷鏈表是否為空 if(temp == null) { System.out.println("當前鏈表為空"); return; } // 遍歷鏈表，存入陣列，此處反序存入陣列，后面順序輸出即可 while(temp != null) { nodes[--length] = temp; temp = temp.next; } System.out.println(Arrays.toString(nodes)); } public static void main(String[] args) { // 創建一個單鏈表 SingleLinkedList<String> singleLinkedList = new SingleLinkedList(new Node("Header")); // 輸出，此時鏈表為空 singleLinkedList.showList(); System.out.println("======================================="); // 給鏈表添加資料 singleLinkedList.addLastNode("Java"); singleLinkedList.addLastNode(new Node<>("JavaScript")); singleLinkedList.insert(new Node<>("Phthon"), 1); singleLinkedList.insert(new Node<>("C"), 3); // 輸出鏈表 singleLinkedList.showList(); System.out.println("======================================="); // 洗掉鏈表資料 // singleLinkedList.deleteLastNode(); // singleLinkedList.delete(2); // // 輸出鏈表 // singleLinkedList.showList(); // System.out.println("======================================="); // 獲取倒數第 k 個節點 // System.out.println(singleLinkedList.getLastKNode(1)); // System.out.println(singleLinkedList.getLastKNode2(2)); System.out.println("======================================="); // 獲取鏈表中間節點 // System.out.println(singleLinkedList.getHalfNode()); System.out.println("======================================="); // 反轉鏈表（頭插法新建一個新的鏈表） SingleLinkedList singleLinkedList2 = singleLinkedList.reverseList(); singleLinkedList2.showList(); System.out.println("======================================="); // 反轉鏈表（直接反轉） singleLinkedList2.reverseList2(); singleLinkedList2.showList(); System.out.println("======================================="); // 不改變原鏈表下，反序輸出鏈表（借助堆疊實作） singleLinkedList2.printReverseList(); System.out.println("======================================="); // 不改變原鏈表下，反序輸出鏈表（借助陣列實作） singleLinkedList2.printReverseList2(); System.out.println("======================================="); } } class Node<E> { E data; // 資料域，存盤節點資料 Node<E> next; // 指標域，指向下一個節點 public Node(E data) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } public Node(E data, Node<E> next) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; this.next = next; } @Override public String toString() { return "Node{ data = "https://www.cnblogs.com/l-y-h/archive/2020/09/29/+ data +" }"; } } 【輸出結果：】 當前鏈表為空 ======================================= 當前鏈表長度為： 4 當前鏈表為： Node{ data = https://www.cnblogs.com/l-y-h/archive/2020/09/29/Phthon } ===> Node{ data = Java } ===> Node{ data = JavaScript } ===> Node{ data = C } ===> ======================================= 當前鏈表長度為： 2 當前鏈表為： Node{ data = https://www.cnblogs.com/l-y-h/archive/2020/09/29/Phthon } ===> Node{ data = JavaScript } ===> ======================================= Node{ data = JavaScript } Node{ data = Phthon } ======================================= Node{ data = Phthon } ======================================= 當前鏈表長度為： 2 當前鏈表為： Node{ data = https://www.cnblogs.com/l-y-h/archive/2020/09/29/JavaScript } ===> Node{ data = Phthon } ===> ======================================= 當前鏈表長度為： 2 當前鏈表為： Node{ data = https://www.cnblogs.com/l-y-h/archive/2020/09/29/Phthon } ===> Node{ data = JavaScript } ===> ======================================= Node{ data = JavaScript }==>Node{ data = https://www.cnblogs.com/l-y-h/archive/2020/09/29/Phthon }==> ======================================= [Node{ data = JavaScript }, Node{ data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ Phthon }] =======================================View Code
4、鏈表（Linked list）-- 雙向鏈表、環形鏈表（約瑟夫環）
（1）雙向鏈表
通過上面單鏈表相關操作，可以知道 單鏈表的 查找方向唯一，
而雙向鏈表在 單鏈表的 基礎上在 添加一個指標域（pre），這個指標域用來指向 當前節點的上一個節點，從而實作 鏈表 雙向查找（某種程度上提高查找效率），
【使用指標 模擬實作 雙向鏈表：】 模擬節點： 在單鏈表的基礎上，增加了一個 指向上一個節點的 指標域， class Node2<E> { Node<E> pre; // 指標域，指向當前節點的上一個節點 Node<E> next; // 指標域，指向當前節點的下一個節點 E data; // 資料域，存盤節點資料 public Node2(E data) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } public Node2(E data, Node<E> pre, Node<E> next) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; this.pre = pre; this.next = next; } } 【增刪節點：】 直接添加節點 A 到鏈表末尾： 首先得遍歷到鏈表最后一個節點 B 的位置，條件： B.next = null， 然后將 B 下一個節點指向 A， A 上一個節點指向 B，即 B.next = A; A.pre = B， 指定位置添加節點 C： 比如： A -> B 變為 A -> C -> B， 即 A.next = B; B.pre = A; 變為 C.next = B; C.pre = B.pre; B.pre.next = C; B.pre = C; 直接洗掉鏈表末尾節點 A： 遍歷到鏈表最后一個節點 B 的位置，然后將其下一個節點指向 null 即可，即 B.next = null; 洗掉指定位置的節點 C： 比如： A -> C -> B 變為 A -> B， C.pre.next = C.next; C.next.pre = C.pre;
（2）雙向鏈表代碼實作如下：
【代碼實作：】 package com.lyh.com.lyh.linkedlist; public class DoubleLinkedList<E> { private int size = 0; // 用于保存鏈表實際長度 private Node2<E> header; // 用于保存鏈表頭節點，僅用作 起點，不存盤資料， public DoubleLinkedList(Node2<E> header) { this.header = header; } /** * 直接在鏈表末尾添加節點 * @param node 待添加節點 */ public void addLastNode(Node2<E> node) { Node2<E> temp = header; // 使用臨時變數保存頭節點，用于輔助鏈表遍歷 // 遍歷鏈表至鏈表末尾 while(temp.next != null) { temp = temp.next; } // 添加節點 temp.next = node; node.pre = temp; size++; } /** * 直接在鏈表末尾添加節點 * @param data 待添加資料 */ public void addLastNode2(E data) { Node2<E> temp = header; // 使用臨時節點保存頭節點，用于輔助鏈表遍歷 Node2<E> newNode = new Node2<>(data); // 創建新節點 // 遍歷鏈表至鏈表末尾 while(temp.next != null) { temp = temp.next; } // 添加節點 temp.next = newNode; newNode.pre = temp; size++; } /** * 遍歷輸出鏈表 */ public void showList() { Node2<E> temp = header.next; // 使用臨時變數保存第一個節點，用于輔助遍歷鏈表 // 判斷鏈表是否為空 if(temp == null) { System.out.println("當前鏈表為空"); return; } // 遍歷輸出鏈表 System.out.print("當前鏈表長度為： " + size() + " == 當前鏈表為： "); while(temp != null) { System.out.print(temp + " ==> "); temp = temp.next; } System.out.println(); } /** * 回傳鏈表長度 * @return 鏈表長度 */ public int size() { return this.size; } /** * 在指定位置添加節點 * @param index 1 ~ n（1 表示 第一個節點） */ public void insert(int index, Node2<E> newNode) { Node2<E> temp = header; // 使用臨時變數保存頭節點，用于輔助鏈表遍歷 // 遍歷找到指定位置 while(index != 0 && temp.next != null) { temp = temp.next; index--; } if (index != 0) { throw new IndexOutOfBoundsException("指定位置有誤： " + index); } newNode.next = temp; newNode.pre = temp.pre; temp.pre.next = newNode; temp.pre = newNode; size++; } /** * 洗掉指定位置的節點 * @param index 1 ~ n(1 表示第一個節點) */ public void delete(int index) { Node2<E> temp = header; // 使用臨時變數保存頭節點，用于輔助鏈表遍歷 // 遍歷找到待洗掉節點位置 while(index != 0 && temp.next != null) { index--; temp = temp.next; } // 判斷節點是否存在 if (index != 0) { throw new IndexOutOfBoundsException("指定節點位置不存在"); } temp.pre.next = temp.next; // 若節點為最后一個節點，則無需對下一個節點進行賦值操作 if (temp.next != null) { temp.next.pre = temp.pre; } size--; } /** * 直接洗掉鏈表末尾節點 */ public void deleteLastNode() { Node2<E> temp = header; // 使用臨時變數保存頭節點，用于輔助鏈表遍歷 // 判斷鏈表是否為空 if (temp.next == null) { System.out.println("當前鏈表為空"); return; } // 遍歷鏈表至最后一個節點 while(temp.next != null) { temp = temp.next; } temp.pre.next = null; size--; } public static void main(String[] args) { // 創建雙向鏈表 DoubleLinkedList<String> doubleLinkedList = new DoubleLinkedList<>(new Node2<>("header")); // 輸出鏈表 doubleLinkedList.showList(); System.out.println("=========================="); // 添加節點 doubleLinkedList.addLastNode(new Node2<>("Java")); doubleLinkedList.addLastNode2("JavaScript"); doubleLinkedList.insert(2, new Node2<>("E")); doubleLinkedList.insert(1, new Node2<>("F")); // 輸出鏈表 doubleLinkedList.showList(); System.out.println("=========================="); doubleLinkedList.delete(1); doubleLinkedList.deleteLastNode(); // 輸出鏈表 doubleLinkedList.showList(); System.out.println("=========================="); } } class Node2<E> { Node2<E> pre; // 指標域，指向當前節點的上一個節點 Node2<E> next; // 指標域，指向當前節點的下一個節點 E data; // 資料域，存盤節點資料 public Node2(E data) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } public Node2(E data, Node2<E> pre, Node2<E> next) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; this.pre = pre; this.next = next; } @Override public String toString() { return "Node2{ pre= " + (pre != null ? pre.data : null) + ", next= " + (next != null ? next.data : null) + ", data= "https://www.cnblogs.com/l-y-h/archive/2020/09/29/+ data +'}'; } } 【輸出結果：】 當前鏈表為空 ========================== 當前鏈表長度為： 4 == 當前鏈表為： Node2{ pre= header, next= Java, data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/F} ==> Node2{ pre= F, next= E, data= Java} ==> Node2{ pre= Java, next= JavaScript, data= E} ==> Node2{ pre= E, next= null, data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/JavaScript} ==> ========================== 當前鏈表長度為： 2 == 當前鏈表為： Node2{ pre= header, next= E, data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/Java} ==> Node2{ pre= Java, next= null, data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/E} ==> ==========================
（3）單向環形鏈表
單向回圈鏈表 指的是 在單鏈表基礎上，將 最后一個節點的指標域 指向第一個節點，從而使鏈表變成一個環狀結構，
其最常見的應用場景就是 約瑟夫環 問題，
【約瑟夫（josephu）環問題：】 已知 n 個人圍成一圈，編號由 1 ~ n，從編號為 k （1 <= k <= n）的人開始從 1 報數，數到 m 的那個人出列， 并從下一個人開始重新報數，再次數到 m 的人出列，依次類推，直至所有人出列，問 n 個人的出隊編號（或者最后一個出隊的是誰）， 【解決思路：】 使用一個不帶頭節點的單向回圈鏈表處理， 先構成一個有 n 個節點的單向回圈鏈表（構建一個單鏈表，并另最后一個節點 last 指向 第一個節點，即 last.next = first）， 由 k 節點開始從 1 計數，移動 m 個節點后將對應的節點從鏈表中洗掉，并從下一個節點開始計數，直至最后一個節點， 使用 兩個節點指標來輔助鏈表遍歷 -- first(指向當前第一個節點、且用于表示待移除的節點)、last(指向當前最后一個節點)， 先遍歷到 k 點（即 first 指向 k 點，last 指向 k 點上一個節點），計數（包括自身，所以 first、last 移動 m - 1 個節點）， 此時 first 指向的即為待輸出的節點，輸出后，將其移除，即 first = first.next; last.next = first; 同理，從移除節點的下一個節點開始操作，當鏈表只剩最后一個節點，即 first == last 時，遍歷結束，輸出最后一個節點 即可， 注： last.next == first 表示環滿 last == first 表示環空，即環里只有一個節點 【代碼實作：】 package com.lyh.com.lyh.linkedlist; public class CircleSingleLinkedList<E> { private Node3<E> first; // 保存第一個節點 /** * 構成單向環形鏈表 * @param num 鏈表節點個數 （1 ~ n， 1 表示 1 個節點） */ public void addNode(int num) { // 判斷 num 是否合適 if (num < 1) { throw new IndexOutOfBoundsException("資料不能構成環"); } Node3 temp = null; // 輔助指標，用于記錄尾節點 // 添加節點，構成回圈鏈表 for (int i = 1; i <= num; i++) { Node3 node = new Node3(i); // 構建新節點 if (i == 1) { // 只有一個節點時，即為首節點 first = node; temp = first; } else { // 添加尾節點 temp.next = node; temp = node; } } // 尾節點指向首節點，構成環 temp.next = first; } /** * 遍歷輸出當前環形鏈表 */ public void showList() { Node3<E> temp = first; // 使用臨時變數存盤第一個節點，用于輔助鏈表遍歷 if (temp == null) { System.out.println("當前鏈表為空"); return; } System.out.print("當前鏈表為： "); while(temp.next != first) { System.out.print(temp + " ==> "); temp = temp.next; } System.out.println(temp); } /** * 按要求輸出 移除節點 順序 * @param num 節點總數(n) * @param start 開始節點編號(1 ~ n) * @param count 計數(1 ~ m) */ public void printList(int num, int start, int count) { Node3<E> last = first; // 用于記錄當前鏈表最后一個節點 if (last == null || start < 1 || start > num) { throw new RuntimeException("引數不合法"); } // 遍歷，得到最后一個節點 while(last.next != first) { last = last.next; } // 找到開始節點, first 表示開始節點，last 表示最后一個節點（即開始節點的上一個節點） while(start != 1) { last = last.next; first = first.next; start--; } // 遍歷輸出節點（開始節點、最后節點重合時 即鏈表只存在一個節點） while(last != first) { // 找到待移除節點，由于當前節點會被計算，所以只需移動 count - 1 個節點， for (int i = 1; i < count; i++) { first = first.next; last = last.next; } System.out.print(first + " ==> "); // 移除節點（first 為被移除節點， 即 last -> first -> A 變為 fisrt = A 且 last -> A） first = first.next; last.next = first; } System.out.println(last); } public static void main(String[] args) { // 構建一個空的回圈鏈表 CircleSingleLinkedList<Integer> circleSingleLinkedList = new CircleSingleLinkedList<>(); circleSingleLinkedList.showList(); System.out.println("========================"); // 添加節點 int num = 5; // 節點個數 circleSingleLinkedList.addNode(num); circleSingleLinkedList.showList(); System.out.println("========================"); // 輸出節點 出鏈表順序 int start = 2; // 開始編號 K int count = 2; // 計數 circleSingleLinkedList.printList(num, start, count); } } class Node3<E> { Node3<E> next; // 指標域，存盤下一個節點 E data; // 資料域，存盤節點資料 public Node3(E data) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } public Node3(Node3<E> next, E data) { this.next = next; this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } @Override public String toString() { return "Node3{ data= "https://www.cnblogs.com/l-y-h/archive/2020/09/29/+ data +'}'; } } 【輸出結果：】 當前鏈表為空 ======================== 當前鏈表為： Node3{ data= 1} ==> Node3{ data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/2} ==> Node3{ data= 3} ==> Node3{ data= 4} ==> Node3{ data= 5} ======================== Node3{ data= 3} ==> Node3{ data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/5} ==> Node3{ data= 2} ==> Node3{ data= 1} ==> Node3{ data= 4}
5、堆疊（Stack）
（1）什么是堆疊？
堆疊指的是一種 受限、線性的資料結構，其僅允許在 一端 進行插入（堆疊頂插入 push）、洗掉操作（堆疊頂洗掉 pop），其允許插入、洗掉的一端為 堆疊頂（Top），另一端為堆疊底（Bottom），
堆疊可以使用 陣列 或者 鏈表 實作（一般采用陣列實作，僅在首或尾增刪，效率比鏈表高），其遵循 先進后出（First In Last Out，FILO） 原則，即先存入 堆疊的值 后取出，
（2）常用場景：
二叉樹遍歷（迭代法），
圖的深度優先搜索法，
運算式轉換與求值（比如：中綴運算式 轉 后綴運算式），
堆疊，比如：JVM 虛擬機堆疊 處理遞回、子程式呼叫時，存盤下一個指令地址 或者 引數、變數，
（3）使用陣列模擬堆疊操作
【使用陣列模擬堆疊操作：】 定義 top 用于記錄當前堆疊頂指向，初始值為 -1， 資料 data 進堆疊時，top 先加 1 再賦值，即 stack[++top] = data， 資料 data 出堆疊時，先保存出堆疊的值，top 再減 1，即 data = https://www.cnblogs.com/l-y-h/archive/2020/09/29/stack[top--] 【代碼實作：】 package com.lyh.stack; public class ArrayStack { private int maxSize; // 記錄堆疊的大小（最大容量） private String[] stack; // 用于記錄 private int top = -1; // 用于初始化堆疊頂位置 public ArrayStack(int maxSize) { this.maxSize = maxSize; this.stack = new String[maxSize]; } /** * 判斷堆疊是否為空 * @return true 為空 */ public boolean isEmpty() { return top == -1; } /** * 判斷堆疊是否已滿 * @return true 表示已滿 */ public boolean isFull() { return top == maxSize - 1; } /** * 資料入堆疊 * @param data 待入堆疊資料 */ public void push(String data) { // 判斷堆疊是夠已滿，已滿則不能再添加資料 if (isFull()) { System.out.println("堆疊滿，無法添加"); return; } // top 加 1，并存值 this.stack[++top] = data; } /** * 資料出堆疊 * @return 出堆疊資料 */ public String pop() { // 判斷堆疊是否為空，為空則無法回傳資料 if(isEmpty()) { System.out.println("堆疊空，無資料"); return null; } // 取值，top 減 1 return this.stack[top--]; } /** * 遍歷輸出堆疊元素 */ public void showList() { // 判斷堆疊是否為空 if (isEmpty()) { System.out.println("堆疊空"); return; } System.out.print("當前堆疊存盤資料個數為： " + (top + 1) + " 當前堆疊輸出為： "); for(int i = top; i >= 0; i--) { System.out.print(this.stack[i] + " == "); } System.out.println(); } public static void main(String[] args) { // 實體化堆疊 ArrayStack arrayStack = new ArrayStack(10); // 遍歷堆疊 arrayStack.showList(); System.out.println("========================"); // 資料入堆疊 arrayStack.push("Java"); arrayStack.push("Python"); arrayStack.push("JavaScript"); // 遍歷堆疊 arrayStack.showList(); System.out.println("========================"); // 資料出堆疊 System.out.println(arrayStack.pop()); System.out.println("========================"); // 遍歷堆疊 arrayStack.showList(); System.out.println("========================"); } } 【輸出結果：】 堆疊空 ======================== 當前堆疊存盤資料個數為： 3 當前堆疊輸出為： JavaScript == Python == Java == ======================== JavaScript ======================== 當前堆疊存盤資料個數為： 2 當前堆疊輸出為： Python == Java == ========================
6、使用堆疊計算 前綴（波蘭）、中綴、逆波蘭（后綴）運算式
（1）運算式的三種表示形式：
運算式可以分為三種表示形式：
前綴（波蘭）運算式，其運算子在運算元之前，
中綴運算式，常見的算術公式（運算子在運算元中間），其括號不可省，
后綴（逆波蘭）運算式，其運算子在運算元之后，
舉例（以下為運算式的三種表示形式）：
前綴運算式：+ 3 4
中綴運算式：3 + 4
后綴運算式：4 3 +
注：
中綴運算式雖然易讀，但是計算機處理起來稍微有點麻煩（比如：括號的處理），不如 前綴、后綴 處理方便（消除了括號），
所以一般處理運算式時 會對運算式進行轉換，比如：中綴運算式轉為后綴運算式，然后再對 后綴運算式進行處理，
中綴轉后綴、中綴轉前綴 程序類似，需要注意的是（詳細可見下面轉換步驟）：
中綴轉前綴時，從右至左掃描字串，且遇到右括號 ")" 直接入堆疊，
中綴轉后綴時，從左至右掃描字串，且遇到左括號 "(" 直接入堆疊，
（2）前綴運算式 以及 中綴 轉 前綴
【前綴（波蘭）運算式：】 基本概念： 前綴運算式又稱為 波蘭運算式，其運算子（+、-、*、/）位于運算元前， 舉例： 一個運算式為：(3 + 4) * 5 - 6，其 對應的前綴運算式為 - * + 3 4 5 6， 如何處理前綴運算式： Step1：需要一個堆疊來存盤運算元，從右至左掃描運算式， Step1.1：如果掃描的是數字，那么就將數字入堆疊， Step1.2：如果掃描的是字符（+、-、*、/），就彈出堆疊頂值兩次，并通過運算子進行計算，最后將結果再次入堆疊， Step2：重復 Step1 程序直至 運算式掃描完成，最后堆疊中的值即為 運算式結果， 如何處理前綴運算式（- * + 3 4 5 6）： Step1：從右至左掃描，依次將 6 5 4 3 入堆疊，此時堆疊元素為 6 5 4 3， Step1.1：掃描到 +，彈出堆疊頂值 3、4，相加（4 + 3 = 7）并入堆疊，即 此時堆疊元素為 6 5 7， Step1.2：掃描到 *，彈出堆疊頂值 7、5，相乘（5 * 7 = 35）并入堆疊，即 此時堆疊元素為 6 35， Step1.3：掃描到 -，彈出堆疊頂值 6、35，相減（35 - 6 = 29）并入堆疊，即 此時堆疊元素為 29， 【中綴運算式 轉換為 前綴運算式：】 中綴運算式轉前綴運算式步驟： Step1：初始化兩個堆疊 A、B，A 用于記錄 運算子、B 用于記錄 中間結果， Step2：從右至左掃描 中綴運算式， Step2.1：如果掃描的是數字，直接將其壓入堆疊 B， Step2.2：如果掃描的是運算子（+、-、*、/），則比較當前運算子 與 A 堆疊頂運算子 的優先級， Step2.2.1：若 A 為空 或者 堆疊頂運算子為右括號 ")"，則當前運算子 直接入堆疊， Step2.2.2：若上面條件不滿足，則比較優先級，若當前運算子優先級 比 A 堆疊頂運算子 優先級高，則當前運算子 也入堆疊， Step2.2.3：若上面條件不滿足，即當前運算子優先級低，則將 A 堆疊頂運算子彈出并壓入 B 堆疊，重新執行 Step2.2 進行運算子比較， Step2.3：如果掃描的是括號 Step2.3.1：如果為右括號 ")"，則直接壓入 A 堆疊， Step2.3.2：如果為左括號 "("，則依次彈出 A 堆疊頂元素并壓入 B 堆疊，直至遇到 右括號 ")"，此時 這對括號可以 舍棄， Step2.4：重復上面掃描步驟，直至運算式掃描完成， Step3：將 A 堆疊中剩余元素依次取出并壓入 B 堆疊， Step4：此時 B 堆疊順序取出結果即為前綴運算式， 中綴運算式 "(3 + 4) * 5 - 6" 如何 轉為前綴運算式 "- * + 3 4 5 6"： Step1：初始化兩個堆疊 A、B，A 存盤運算子，B 存盤中間結果，從右到左掃描中綴運算式， Step1.1：掃描到 6，直接存入 B 堆疊，此時 A 堆疊元素為 空，B 堆疊元素為 6， Step1.2：掃描到 -，此時 A 堆疊為空，直接存入 A 堆疊，此時 A 堆疊元素為 -，B 堆疊元素為 6， Step1.3：掃描到 5，直接存入 B 堆疊，此時 A 堆疊元素為 -，B 堆疊元素為 6 5， Step1.4：掃描到 *，當前運算子 * 比 A 堆疊頂運算子 優先級高，直接入堆疊，即此時 A 堆疊元素為 - *，B 堆疊元素為 6 5， Step1.5：掃描到 )，直接入 A 堆疊，此時 A 堆疊元素為 - * ），B 堆疊元素為 6 5， Step1.6：掃描到 4，直接存入 B 堆疊，此時 A 堆疊元素為 - * )，B 堆疊元素為 6 5 4， Step1.7：掃描到 +，由于堆疊頂元素為右括號 ")"，直接入 A 堆疊，此時 A 堆疊元素為 - * ) +，B 堆疊元素為 6 5 4， Step1.8：掃描到 3，直接入 B 堆疊，此時 A 堆疊元素為 - * ) +，B 堆疊元素為 6 5 4 3， Step1.9：掃描到左括號 "("，A 堆疊頂元素出堆疊并壓入 B 堆疊直至遇到 右括號 ")"，且移除括號，此時 A 堆疊元素為 - *， B 堆疊元素為 6 5 4 3 +， Step2：將 A 堆疊剩余元素依次取出并壓入 B 堆疊，此時 A 堆疊為空，B 堆疊元素為 6 5 4 3 + * -， Step3：將 B 依次取出即為前綴運算式 "- * + 3 4 5 6"，
（3）中綴運算式
【中綴運算式：】 基本概念： 中綴運算式就是最常見的運算運算式，其運算子在運算元中間， 注： 中綴運算式括號不可省，其用于表示運算的優先順序， 舉例： 一個運算式為：(3 + 4) * 5 - 6，這就是中綴運算式， 如何處理中綴運算式： Step1：需要兩個堆疊 A、B，A 用于存放 運算元，B 用于存放 符號（運算子、括號）， Step2：從左到右掃描 中綴運算式， Step2.1：如果掃描的是 數字，則直接壓入 A 堆疊， Step2.2：如果掃描的是 運算子（+、-、*、/），則比較當前運算子 與 B 堆疊頂運算子 的優先級， Step2.2.1：若 B 為空 或者 堆疊頂元素為左括號 "("，則當前運算子直接入堆疊， Step2.2.2：若上面條件不滿足，則比較優先級，若當前運算子 比 B 堆疊頂運算子 優先級高，則當前運算子 入 B 堆疊， Step2.2.3：若上面條件不滿足，即當前運算子優先級低，則將 B 堆疊頂運算子彈出，并彈出 A 堆疊頂兩個資料進行 計算，最后將計算結果存入 A 堆疊，重新執行 Step2.2 進行運算子比較， Step2.3：如果掃描的是括號： Step2.3.1：若為左括號 "("，則直接壓入 B 堆疊， Step2.3.2：若為右括號 ")"，則依次彈出 B 堆疊運算子直至遇到左括號 "("，B 堆疊每取一個元素，A 堆疊取兩個元素，計算后將結果重新壓入 A 堆疊， Step2.4：重復上面掃描步驟，直至運算式掃描完成， Step3：依次取出 B 堆疊頂運算子 以及 A 堆疊頂元素 計算，最后結果即為 運算式結果， 注： 直接處理中綴運算式，在于其會直接通過 運算子 進行運算， 如何處理中綴運算式 "(3 + 4) * 5 - 6"： Step1：初始化兩個堆疊 A、B，A 用于記錄 運算元， B 用于記錄 運算子， Step2：從左至右掃描 中綴運算式， Step2.1：掃描到左括號 "("，直接入 B 堆疊，此時 A 堆疊元素為空，B 堆疊元素為 (， Step2.2：掃描到 3，直接入 A 堆疊，此時 A 堆疊元素為 3，B 堆疊元素為 (， Step2.3：掃描到 +，此時 B 堆疊頂元素為左括號 "("，直接入 B 堆疊，此時 A 堆疊元素為 3，B 堆疊元素為 ( +， Step2.4：掃描到 4，直接入 A 堆疊，此時 A 堆疊元素為 4，B 堆疊元素為 ( +， Step2.5：掃描到右括號 ")"，B 堆疊頂元素 + 出堆疊，A 堆疊彈出 4、 3，計算后重新壓入 A 堆疊， B 繼續彈出堆疊頂元素為左括號 "("，直接將其出堆疊，此時 A 堆疊元素為 7，B 堆疊元素為空， Step2.6：掃描到 *，B 堆疊元素為空，直接入 B 堆疊，此時 A 堆疊元素為 7，B 堆疊元素為 *， Step2.7：掃描到 5，直接入 A 堆疊，此時 A 堆疊元素為 7 5，B 堆疊元素為 *， Step2.8：掃描到 -，當前運算子 - 比 B 堆疊頂運算子優先級 低，B 堆疊頂運算子出堆疊，A 堆疊彈出 5、7，計算后壓入 A 堆疊， 此時 B 堆疊為空，當前運算子直接壓入 B 堆疊，即此時 A 堆疊元素為 35，B 堆疊元素為 -， Step2.9：掃描到 6，直接入 A 堆疊，此時 A 堆疊元素為 35 6， B 堆疊元素為 -， Step3：取出 B 堆疊頂元素 -，A 堆疊彈出元素 6、35，計算后壓入 A 堆疊，此時 B 堆疊為空，即運算式計算結束，A 堆疊最終結果即為運算式結果，即 29，
（4）后綴運算式 以及 中綴 轉 后綴
【后綴（逆波蘭）運算式：】 基本概念： 后綴運算式又稱為 逆波蘭運算式，其運算子位于運算元之后， 舉例： 一個運算式為：(3 + 4) * 5 - 6，其 對應的前綴運算式為：3 4 + 5 * 6 - 如何處理后綴運算式： Step1：需要一個堆疊來存盤運算元，從左至右掃描運算式， Step1.1：如果掃描的是數字，那么就將數字入堆疊， Step1.2：如果掃描的是字符（+、-、*、/），就彈出堆疊頂值兩次，并通過運算子進行計算，最后將結果再次入堆疊， Step2：重復 Step1 程序直至 運算式掃描完成，最后堆疊中的值即為 運算式結果， 如何處理后綴運算式（3 4 + 5 * 6 -）： Step1：從左至右掃描，依次將 3 4 入堆疊，此時堆疊元素為 3 4， Step1.1：掃描到 +，彈出堆疊頂值 3、4，相加并入堆疊，即 此時堆疊元素為 7， Step1.2：掃描到 5，入堆疊，即 此時堆疊元素為 7 5， Step1.3：掃描到 *，彈出堆疊頂值 5、7，相乘并入堆疊，即 此時堆疊元素為 35， Step1.4：掃描到 6，入堆疊，即 此時堆疊元素為 35 6， Step1.5：掃描到 -，彈出堆疊頂值 6、35，相減并入堆疊，即 此時堆疊元素為 29， 【中綴運算式 轉換為 后綴運算式：】 中綴運算式轉后綴運算式步驟： Step1：初始化兩個堆疊 A、B，A 用于記錄 運算子、B 用于記錄 中間結果， Step2：從左至右掃描 中綴運算式， Step2.1：如果掃描的是數字，直接將其壓入堆疊 B， Step2.2：如果掃描的是運算子（+、-、*、/），則比較當前運算子 與 A 堆疊頂運算子 的優先級， Step2.2.1：若 A 為空 或者 堆疊頂運算子為左括號 "("，則當前運算子 直接入堆疊， Step2.2.2：若上面條件不滿足，則比較優先級，若當前運算子優先級 比 A 堆疊頂運算子 優先級高，則當前運算子 也入堆疊， Step2.2.3：若上面條件不滿足，即當前運算子優先級低，則將 A 堆疊頂運算子彈出并壓入 B 堆疊，重新執行 Step2.2 進行運算子比較， Step2.3：如果掃描的是括號 Step2.3.1：如果為左括號 "("，則直接壓入 A 堆疊， Step2.3.2：如果為右括號 ")"，則依次彈出 A 堆疊頂元素并壓入 B 堆疊，直至遇到 左括號 "("，此時 這對括號可以 舍棄， Step2.4：重復上面掃描步驟，直至運算式掃描完成， Step3：將 A 堆疊中剩余元素依次取出并壓入 B 堆疊， Step4：此時 B 堆疊逆序結果即為后綴運算式， 注： 實際寫代碼時，由于 B 堆疊自始至終不會進行彈出操作，且其結果的 逆序 才是 后綴運算式， 所以為了減少一次 逆序 的程序，可以直接使用 陣列 或者 鏈表 進行存盤，然后 順序讀取即可， 中綴運算式 "(3 + 4) * 5 - 6" 如何 轉為后綴運算式 "3 4 + 5 * 6 -"： Step1：初始化兩個堆疊 A、B，A 存盤運算子，B 存盤中間結果，從左至右掃描中綴運算式， Step1.1：掃描到左括號 "("，壓入 A 堆疊，此時 A 堆疊元素為 (，B 堆疊元素為空， Step1.2：掃描到 3，壓入 B 堆疊，此時 A 堆疊元素為 (，B 堆疊元素為 3， Step1.3：掃描到 +，由于 A 堆疊頂元素為左括號 "("，所以直接入堆疊，此時 A 堆疊元素為 ( +，B 堆疊元素為 3， Step1.4：掃描到 4，壓入 B 堆疊，此時 A 堆疊元素為 ( +，B 堆疊元素為 3 4， Step1.5：掃描到右括號 )，A 堆疊元素依次出堆疊壓入 B 直至遇到左括號 "("，并移除括號，此時 A 堆疊元素為 空，B 堆疊元素為 3 4 +， Step1.6：掃描到 *，由于 A 堆疊為空直接入堆疊，此時 A 堆疊元素為 *，B 堆疊元素為 3 4 +， Step1.7：掃描到 5，壓入 B 堆疊，A 堆疊元素為 *，B 堆疊元素為 3 4 + 5， Step1.8：掃描到 -，當前運算子 - 優先級低于 A 優先級，所以 A 堆疊頂元素彈出并壓入 B 堆疊，此時 A 堆疊為空，當前運算子直接存入，此時 A 堆疊元素為 -，B 堆疊元素為 3 4 + 5 *， Step1.9：掃描到 6，壓入 B 堆疊，此時 A 堆疊元素為 -，B 堆疊元素為 3 4 + 5 * 6， Step2：將 A 剩余元素出堆疊并壓入 B，此時 A 堆疊為空，B 堆疊元素為 3 4 + 5 * 6 -， Step3：將 B 堆疊元素依次取出并倒序輸出，即為 后綴運算式 "3 4 + 5 * 6 -"，
（5）中綴運算式、前綴運算式、后綴運算式代碼實作
如下代碼，實作 基本運算式（多位數且帶括號）的 +、-、*、/，
此處直接使用 Stack 類作為 堆疊 使用，不使用自定義堆疊結構，
【代碼實作：】 package com.lyh.stack; import java.util.ArrayList; import java.util.List; import java.util.Stack; public class Expression { public static void main(String[] args) { Expression expressionDemo = new Expression(); // 定義一個運算式（默認格式正確，此處不做過多的格式校驗） // String expression = ("2+3*(7-4)+8/4").trim(); String expression = ("(13-6)*5-6").trim(); System.out.println("當前運算式為： " + expression); System.out.println("================================"); List<String> infixExpressionList = expressionDemo.transfor(expression); System.out.println("運算式轉換后為中綴運算式： " + infixExpressionList); System.out.println("================================"); System.out.println("中綴運算式求值為： " + expressionDemo.infixExpression(infixExpressionList)); System.out.println("================================"); List<String> prefixExpressionList = expressionDemo.infixToPrefix(infixExpressionList); System.out.println("中綴運算式： " + infixExpressionList + " 轉為 前綴運算式： " + prefixExpressionList); System.out.println("前綴運算式求值為： " + expressionDemo.prefixExpression(prefixExpressionList)); System.out.println("================================"); List<String> suffixExpressionList = expressionDemo.infixToSuffix(infixExpressionList); System.out.println("中綴運算式： " + infixExpressionList + " 轉為 后綴運算式： " + suffixExpressionList); System.out.println("后綴運算式求值為： " + expressionDemo.suffixExpression(suffixExpressionList)); System.out.println("================================"); } /** * 字串轉換成集合保存，便于操作 * @param expression 待轉換的運算式 * @return 轉換完成的運算式 */ public List<String> transfor(String expression) { // 用于保存最終結果 List<String> result = new ArrayList<>(); // 用于轉換多位數 String temp = ""; // 遍歷字串，將其 資料取出（可能存在多位數） 挨個存入集合 for(int i = 0; i < expression.length(); i++) { // 遇到多位數，就使用 temp 拼接 while(i < expression.length() && expression.charAt(i) >= '0' && expression.charAt(i) <= '9') { temp += expression.charAt(i); i++; } // 將多位數存放到集合中 if (temp != "") { result.add(temp); temp = ""; } // 存放符號（+、-、*、/、括號） if (i < expression.length()) { result.add(String.valueOf(expression.charAt(i))); } } return result; } /** * 中綴運算式求值（從左到右掃描運算式） * @param expression 運算式 * @return 計算結果 */ public String infixExpression(List<String> expression) { Stack<String> stackA = new Stack<>(); // 用于存放運算元，簡稱 A 堆疊 Stack<String> stackB = new Stack<>(); // 用于存放運算子，簡稱 B 堆疊 // 遍歷集合，取出運算式中 資料 以及 運算子 存入堆疊中并計算 expression.forEach(x -> { // 如果取出的是資料，直接存放進 A 堆疊 if (x.matches("\\d+")) { stackA.push(x); } else { // 如果當前運算子為右括號 ")" if (")".equals(x)) { // 依次取出 B 堆疊頂運算子 以及 A 堆疊頂兩個元素進行計算，計算結果再存入 A 堆疊，直至遇到左括號 "(" while(stackB.size() > 0 && !"(".equals(stackB.peek())) { stackA.push(calculate(stackA.pop(), stackA.pop(), stackB.pop())); } // 移除左括號 "(" 與 當前運算子右括號 ")"，即此次比較結束， stackB.pop(); } else { // 比較運算子優先級，判斷當前運算子是直接進入 B 堆疊，還是先取出優先級高的運算子計算后、再將當前運算子入堆疊， while(true) { // 如果 當前運算子為左括號 "(" 或者 B 堆疊為空 或者 B 堆疊頂元素為 左括號 "(" 或者 當前運算子優先級 高于 B 堆疊頂元素優先級，則當前運算子直接入堆疊 if ("(".equals(x) || stackB.size() == 0 || "(".equals(stackB.peek()) || priority(x) > priority(stackB.peek())) { stackB.push(x); break; } // 以上條件均不滿足，即當前運算子優先級 小于等于 B 堆疊頂元素優先級 // if (priority(x) <= priority(stackB.peek())) { // 依次取出 B 堆疊頂運算子 以及 A 堆疊頂兩個元素進行計算，計算結果再存入 A 堆疊 stackA.push(calculate(stackA.pop(), stackA.pop(), stackB.pop())); // } } } } }); // 依次取出 B 堆疊頂運算子 以及 A 堆疊頂兩個元素進行計算，計算結果再存入 A 堆疊 while(stackB.size() > 0) { stackA.push(calculate(stackA.pop(), stackA.pop(), stackB.pop())); } return stackA.pop(); } /** * 回傳運算子優先級 * @param operator 運算子 * @return 優先級（0 ~ n, 0 為最小優先級） */ public int priority(String operator) { switch (operator) { case "+": return 1; case "-": return 1; case "*": return 2; case "/": return 2; default: return 0; } } /** * 根據運算子 計算 兩資料，并回傳計算結果 * @param num 資料 A * @param num2 資料 B * @param operator 運算子 * @return 計算結果 */ public String calculate(String num, String num2, String operator) { String result = ""; switch (operator) { case "+": result = String.valueOf(Integer.valueOf(num2) + Integer.valueOf(num)); break; case "-": result = String.valueOf(Integer.valueOf(num2) - Integer.valueOf(num)); break; case "*": result = String.valueOf(Integer.valueOf(num2) * Integer.valueOf(num)); break; case "/": result = String.valueOf(Integer.valueOf(num2) / Integer.valueOf(num)); break; default: result = ""; break; } return result; } /** * 前綴運算式求值（從右到左掃描運算式） * @param expression 前綴運算式 * @return 計算結果 */ public String prefixExpression(List<String> expression) { Stack<String> stackA = new Stack<>(); // 用于存盤運算元，簡稱 A 堆疊 // 從右到左掃描運算式 for (int i = expression.size() - 1; i >= 0; i--) { // 用于保存當前運算式資料（運算元 或者 運算子） String temp = expression.get(i); // 如果當前資料為 運算元，則直接存入 A 堆疊 if (temp.matches("\\d+")) { stackA.push(temp); } else { // 若為運算子，則依次彈出 A 堆疊頂兩個資料，并根據運算子進行計算，計算結果重新存入 A 堆疊 // 此處順序要注意，與后綴有區別 String num2 = stackA.pop(); String num = stackA.pop(); stackA.push(calculate(num, num2, temp)); } } // 掃描結束后，A 堆疊最終結果即為 運算式結果 return stackA.pop(); } /** * 中綴運算式轉前綴運算式（從右到左掃描運算式） * @param expression 中綴運算式 * @return 前綴運算式 */ public List<String> infixToPrefix(List<String> expression) { Stack<String> stackA = new Stack<>(); // 用于保存 運算子（運算子），簡稱 A 堆疊 Stack<String> stackB = new Stack<>(); // 用于保存 中間結果（存盤資料以及運算子，存盤程序中不會有出堆疊操作），簡稱 B 堆疊 List<String> result = new ArrayList<>(); // 用于記錄最終結果 // 從右到左掃描運算式，取出資料、運算子 并計算 for (int i = expression.size() - 1; i >= 0; i--) { // 用于表示集合當前取出的資料 String temp = expression.get(i); // 如果取出的為 運算元，直接存入 B 堆疊 if (temp.matches("\\d+")) { stackB.push(temp); } else { // 如果取出的是左括號 if ("(".equals(temp)) { // 依次彈出 A 堆疊頂元素并壓入 B 堆疊，直至遇到 右括號 ")" while(stackA.size() > 0 && !")".equals(stackA.peek())) { stackB.push(stackA.pop()); } // 移除 A 堆疊頂右括號 ")" stackA.pop(); } else { // 比較運算子優先級，判斷運算子直接進入 A 堆疊 還是 先彈出 A 堆疊頂元素并壓入 B 堆疊后、再將當前運算子入 A 堆疊 while(true) { // 如果當前運算子為右括號 ")" 或者 A 堆疊為空 或者 A 堆疊頂元素為右括號 ")" 或者 當前運算子優先級 高于 A 堆疊頂運算子，則直接入 A 堆疊 if (")".equals(temp) || stackA.size() == 0 || ")".equals(stackA.peek()) || priority(temp) > priority(stackA.peek())) { stackA.push(temp); break; } // 若上面條件均不滿足，即當前運算子優先級小于等于 A 堆疊頂運算子，則彈出 A 堆疊頂運算子并壓入 B 堆疊 stackB.push(stackA.pop()); } } } } // 依次將 A 堆疊剩余元素彈出并壓入到 B 堆疊 while(stackA.size() > 0) { stackB.push(stackA.pop()); } // 依次取出 B 堆疊元素，即為 前綴運算式 while(stackB.size() > 0) { result.add(stackB.pop()); } return result; } /** * 中綴運算式轉后綴運算式（從左到右掃描運算式） * @param expression 中綴運算式 * @return 后綴運算式 */ public List<String> infixToSuffix(List<String> expression) { Stack<String> stackA = new Stack<>(); // 用于保存 運算子（運算子），簡稱 A 堆疊 // Stack<String> stackB = new Stack<>(); // 用于保存 中間結果，簡稱 B 堆疊 // 由于 B 堆疊反序輸出才是后綴運算式，此處可以直接存放在 集合中，順序讀取即為 后綴運算式， List<String> result = new ArrayList<>(); // 用于保存 最終結果，此處用來替代 B 堆疊，后面簡稱 B 堆疊， // 從左到右掃描后綴運算式 expression.forEach(x -> { // 如果取出的是 運算元，直接存入 B 堆疊 if (x.matches("\\d+")) { result.add(x); } else { // 如果運算子是右括號 ")" if (")".equals(x)) { // 依次將 A 堆疊頂運算子彈出 并壓入 B 堆疊，直至遇到左括號 "(" while(stackA.size() > 0 && !"(".equals(stackA.peek())) { result.add(stackA.pop()); } // 移除 A 堆疊頂左括號 "(" stackA.pop(); } else { // 比較運算子優先級，判斷運算子直接進入 A 堆疊 還是 先彈出 A 堆疊頂元素并壓入 B 堆疊后、再將當前運算子入 A 堆疊 while(true) { // 如果當前運算子為左括號 "(" 或者 A 堆疊為空 或者 A 堆疊頂運算子為左括號 "(" 或者 當前運算子優先級 高于 A 堆疊頂運算子，則直接入 A 堆疊 if ("(".equals(x) || stackA.size() == 0 || "(".equals(stackA.peek()) || priority(x) > priority(stackA.peek())) { stackA.push(x); break; } // 如果上面條件均不滿足，即當前運算子 優先級 小于或等于 A 堆疊頂運算子 // 則將 A 堆疊頂運算子取出并 放入 B 堆疊 result.add(stackA.pop()); } } } }); // 依次將 A 堆疊頂運算子取出放入 B 堆疊 while(stackA.size() > 0) { result.add(stackA.pop()); } return result; } /** * 后綴運算式求值（從左到右掃描運算式） * @param expression 后綴運算式 * @return 計算結果 */ public String suffixExpression(List<String> expression) { Stack<String> stackA = new Stack<>(); // 用于保存 運算元，簡稱 A 堆疊 // 從左到右掃描運算式 expression.forEach(x -> { // 如果是 數字，直接進 A 堆疊 if (x.matches("\\d+")) { stackA.push(x); } else { // 是運算子，則取出 A 堆疊頂兩元素，并計算，將計算結果重新壓入 A 堆疊 stackA.push(calculate(stackA.pop(), stackA.pop(), x)); } }); // 掃描結束后，A 堆疊最終結果即為 運算式結果 return stackA.pop(); } } 【輸出結果：】 當前運算式為： (13-6)*5-6 ================================ 運算式轉換后為中綴運算式： [(, 13, -, 6, ), *, 5, -, 6] ================================ 中綴運算式求值為： 29 ================================ 中綴運算式： [(, 13, -, 6, ), *, 5, -, 6] 轉為 前綴運算式： [-, *, -, 13, 6, 5, 6] 前綴運算式求值為： 29 ================================ 中綴運算式： [(, 13, -, 6, ), *, 5, -, 6] 轉為 后綴運算式： [13, 6, -, 5, *, 6, -] 后綴運算式求值為： 29 ================================
7、遞回與回溯、八皇后問題
（1）遞回：
遞回指的是 方法呼叫自身方法去解決問題的程序，
其目的是 將一個復雜的大問題 轉換為 與原問題類似的小問題去求解，遞回必須得有結束條件，否則將會陷入無限遞回（導致堆疊溢位例外），
常用場景：快排、歸并排序、二分查找、漢諾塔、八皇后 等問題，
（2）回溯：
回溯指的是 類似列舉的選優搜索程序，當條件不符合時，回傳上一層（即回溯）重新判斷，
其解決的是 某種場景下有許多個解，依次判斷每個解是否合適，如果不合適就回退到上一層，重新判斷下一個解是否合適，
常見場景：八皇后 問題，
（3）八皇后問題分析
【八皇后問題介紹：】 在一個 8 * 8 的國際象棋棋盤上，擺放 八個皇后，且皇后之間不能相互攻擊，總共有多少種擺法， 不能相互攻擊 即： 任意兩個皇后 不能同時 處在 同一行、同一列、同一斜線上， 【思路分析：】 采用 回溯 方法解決， 每次放置皇后時，均從每行的第一列開始嘗試，并校驗該皇后位置是否與其他皇后位置發生沖突，如果不沖突則遞回呼叫下一個皇后進行放置， 如果沖突則嘗試當前皇后位置的下一個位置是否能夠放置，若當前皇后在當前行的所有列均放置失敗，則回溯到上一個皇后所處位置，使上一個皇后放置在其下一列 并重新判斷該位置是否沖突， 即： Step1：第一個皇后放在第一行第一列， Step2：第二個皇后放在第二行第一列，判斷是否會攻擊，如果會攻擊，則將 第二個皇后放在第二行第二列 進行判斷， 若仍會攻擊，則依次放置下去，直至第二行第八列，若仍會攻擊，則后續不用執行（此時第二個皇后 8 個位置均放置失敗），回溯到 上一行 并再次列舉， Step3：第二個皇后放好后，同理放置第三個皇后 直至 放置第八個 皇后，若均不沖突則 為一個解， 【判斷皇后之間是否攻擊：】 使用一維陣列 a[8] 存盤可行的 八皇后 放置位置（二維陣列亦可）， 每一個陣列元素存盤范圍為 0~7，分別表示第 1 ~ 8 位置， 判斷皇后之間是否攻擊：設當前為第 n 個皇后，記為 a[n]， 同一行：不需要考慮，每次都是不同行， 同一列：遍歷一維陣列，如果 a[i] == a[n]，則表示當前存在攻擊， for(int i = 0; i < n; i++) { if (a[i] == a[n]) { return false; } } 同一斜線：遍歷一維陣列，若 Math.abs(n - i) == Math.abs(a[n] - a[i])，則存在攻擊， for(int i = 0; i < n; i++) { if (Math.abs(n - i) == Math.abs(a[n] - a[i])) { return false; } } 注： i 指的是第 i+1 個皇后，a[i] 指的是第 i+1 個皇后所占據的位置（0~7）， 所以 a[i] == a[n] 時表示同一列， Math.abs(n - i) == Math.abs(a[n] - a[i]) 表示同一斜線（看成等腰直角三角形），
【八皇后代碼實作：】 package com.lyh.recursion; import java.util.Arrays; public class EightQueens { private int maxsize = 8; // 定義最大為 8 皇后 private int count = 0; // 用于記錄皇后放置總解法數 private int[] arrays = new int[maxsize]; // 用于存盤 8 皇后的解法，范圍為 0 ~ 7，表示第 1 ~ 8 位置 public EightQueens() { } public EightQueens(int maxsize) { this.maxsize = maxsize; arrays = new int[this.maxsize]; } public static void main(String[] args) { EightQueens eightQueens = new EightQueens(); eightQueens.putQueen(0); System.out.println("總解法： " + eightQueens.count); } /** * 檢查當前皇后的放置位置 是否 與其他皇后位置沖突 * @param n 當前為第 n+1 皇后 * @return true 表示不沖突 */ public boolean check(int n) { // 遍歷當前所有皇后，已放置 0 ~ n-1 個皇后，即 第 1 ~ n 皇后位置 for(int i = 0; i < n; i++) { // arrays[i] == arrays[n] 表示兩皇后在同一列 // Math.abs(n - i) == Math.abs(arrays[n] - arrays[i]) 表示兩皇后在同一斜線上（看成等腰直角三角形處理） if (arrays[i] == arrays[n] || Math.abs(n - i) == Math.abs(arrays[n] - arrays[i])) { return false; } } return true; } /** * 遞回 + 回溯 放置皇后 * @param n 第 n+1 個皇后 */ public void putQueen(int n) { // 所有皇后放置完成，列印皇后放置方法 // 此處為第一個出口，即 8 個皇后全部放置完成時， if (n == maxsize) { System.out.println(Arrays.toString(arrays)); count++; return; } // 列舉依次求解，遍歷 0 ~ maxsize - 1，表示當前皇后放置在第 1 ~ maxsize 個位置， // 此處為第二個出口，若遍歷完成，n 仍不為 8，即 第 n-1 個皇后 8 個位置均放置失敗，后續無需再做，回溯到上一個皇后放置位置的下一個位置 for (int i = 0; i < maxsize; i++) { // 放置皇后 arrays[n] = i; // 當前皇后放置不沖突，則放置下一個皇后，若沖突則結束當前回圈并判斷下一個位置是否沖突 if (check(n)) { putQueen(n + 1); } } } } 【輸出結果：】 [0, 4, 7, 5, 2, 6, 1, 3] [0, 5, 7, 2, 6, 3, 1, 4] [0, 6, 3, 5, 7, 1, 4, 2] [0, 6, 4, 7, 1, 3, 5, 2] [1, 3, 5, 7, 2, 0, 6, 4] [1, 4, 6, 0, 2, 7, 5, 3] [1, 4, 6, 3, 0, 7, 5, 2] [1, 5, 0, 6, 3, 7, 2, 4] [1, 5, 7, 2, 0, 3, 6, 4] [1, 6, 2, 5, 7, 4, 0, 3] [1, 6, 4, 7, 0, 3, 5, 2] [1, 7, 5, 0, 2, 4, 6, 3] [2, 0, 6, 4, 7, 1, 3, 5] [2, 4, 1, 7, 0, 6, 3, 5] [2, 4, 1, 7, 5, 3, 6, 0] [2, 4, 6, 0, 3, 1, 7, 5] [2, 4, 7, 3, 0, 6, 1, 5] [2, 5, 1, 4, 7, 0, 6, 3] [2, 5, 1, 6, 0, 3, 7, 4] [2, 5, 1, 6, 4, 0, 7, 3] [2, 5, 3, 0, 7, 4, 6, 1] [2, 5, 3, 1, 7, 4, 6, 0] [2, 5, 7, 0, 3, 6, 4, 1] [2, 5, 7, 0, 4, 6, 1, 3] [2, 5, 7, 1, 3, 0, 6, 4] [2, 6, 1, 7, 4, 0, 3, 5] [2, 6, 1, 7, 5, 3, 0, 4] [2, 7, 3, 6, 0, 5, 1, 4] [3, 0, 4, 7, 1, 6, 2, 5] [3, 0, 4, 7, 5, 2, 6, 1] [3, 1, 4, 7, 5, 0, 2, 6] [3, 1, 6, 2, 5, 7, 0, 4] [3, 1, 6, 2, 5, 7, 4, 0] [3, 1, 6, 4, 0, 7, 5, 2] [3, 1, 7, 4, 6, 0, 2, 5] [3, 1, 7, 5, 0, 2, 4, 6] [3, 5, 0, 4, 1, 7, 2, 6] [3, 5, 7, 1, 6, 0, 2, 4] [3, 5, 7, 2, 0, 6, 4, 1] [3, 6, 0, 7, 4, 1, 5, 2] [3, 6, 2, 7, 1, 4, 0, 5] [3, 6, 4, 1, 5, 0, 2, 7] [3, 6, 4, 2, 0, 5, 7, 1] [3, 7, 0, 2, 5, 1, 6, 4] [3, 7, 0, 4, 6, 1, 5, 2] [3, 7, 4, 2, 0, 6, 1, 5] [4, 0, 3, 5, 7, 1, 6, 2] [4, 0, 7, 3, 1, 6, 2, 5] [4, 0, 7, 5, 2, 6, 1, 3] [4, 1, 3, 5, 7, 2, 0, 6] [4, 1, 3, 6, 2, 7, 5, 0] [4, 1, 5, 0, 6, 3, 7, 2] [4, 1, 7, 0, 3, 6, 2, 5] [4, 2, 0, 5, 7, 1, 3, 6] [4, 2, 0, 6, 1, 7, 5, 3] [4, 2, 7, 3, 6, 0, 5, 1] [4, 6, 0, 2, 7, 5, 3, 1] [4, 6, 0, 3, 1, 7, 5, 2] [4, 6, 1, 3, 7, 0, 2, 5] [4, 6, 1, 5, 2, 0, 3, 7] [4, 6, 1, 5, 2, 0, 7, 3] [4, 6, 3, 0, 2, 7, 5, 1] [4, 7, 3, 0, 2, 5, 1, 6] [4, 7, 3, 0, 6, 1, 5, 2] [5, 0, 4, 1, 7, 2, 6, 3] [5, 1, 6, 0, 2, 4, 7, 3] [5, 1, 6, 0, 3, 7, 4, 2] [5, 2, 0, 6, 4, 7, 1, 3] [5, 2, 0, 7, 3, 1, 6, 4] [5, 2, 0, 7, 4, 1, 3, 6] [5, 2, 4, 6, 0, 3, 1, 7] [5, 2, 4, 7, 0, 3, 1, 6] [5, 2, 6, 1, 3, 7, 0, 4] [5, 2, 6, 1, 7, 4, 0, 3] [5, 2, 6, 3, 0, 7, 1, 4] [5, 3, 0, 4, 7, 1, 6, 2] [5, 3, 1, 7, 4, 6, 0, 2] [5, 3, 6, 0, 2, 4, 1, 7] [5, 3, 6, 0, 7, 1, 4, 2] [5, 7, 1, 3, 0, 6, 4, 2] [6, 0, 2, 7, 5, 3, 1, 4] [6, 1, 3, 0, 7, 4, 2, 5] [6, 1, 5, 2, 0, 3, 7, 4] [6, 2, 0, 5, 7, 4, 1, 3] [6, 2, 7, 1, 4, 0, 5, 3] [6, 3, 1, 4, 7, 0, 2, 5] [6, 3, 1, 7, 5, 0, 2, 4] [6, 4, 2, 0, 5, 7, 1, 3] [7, 1, 3, 0, 6, 4, 2, 5] [7, 1, 4, 2, 0, 6, 3, 5] [7, 2, 0, 5, 1, 4, 6, 3] [7, 3, 0, 2, 5, 1, 6, 4] 總解法： 92
三、排序演算法
1、常見內排序
之前總結過一篇，此處不重復介紹，對其稍作補充說明，
詳見：https://www.cnblogs.com/l-y-h/p/12391241.html
2、基數排序（Radix Sort）
（1）什么是基數排序？
基數排序是桶排序的擴展，其將 整數 按照 位數（個位、十位、百位等）進行劃分，每次劃分后將劃分的結果存放到相應的桶中，最終達到排序的目的，
基數排序屬于穩定排序，
【基數排序步驟：(此時無法處理負數)】 Step1：首先定義一個桶陣列，編號為 0 ~ 9，分別表示用于存盤符合 0 ~ 9 的資料， 且每個桶元素 又是一個陣列，用于存盤符合 0 ~ 9 的資料， Step2：對于一組資料，從每個數的 個位 開始進行劃分（個位范圍為 0 ~ 9），將資料分別存盤到 桶陣列中， 然后遍歷輸出得到新的陣列， Step3：對于新的一組資料，從每個數的 十位 開始劃分，進行 Step2 同樣操作， Step4：同理，處理 百位、千位，若一個數沒有 百位、千位，則將其視為 0 處理， 注： 首先得獲取當前資料中 最大資料 的位數，然后再進行 位數劃分， 比如： 7 99 10 8 中最大資料為 兩位數，需進行 個位、十位 劃分， 45 123 34 中最大資料為 三位數，需進行 個位、十位、百位 劃分， 【基數排序存在 負數 時處理：】 可以先找到 負數的最小值，然后將所有資料 整體加上 負數最小值的絕對值 加 1，記為 min = |負數最小值|， 即 讓所有資料均變為 非負數，然后再去排序，最后將結果 再整體減去 min 即可， 注： 若 最大值、最小值 瀕臨極限時，可能會造成資料溢位（此時慎用）， 【給資料 arr {38, 65, 97, 76, 13, 27, 49} 排序，并按照從小到大的順序輸出】 Step1：首先定義一個 二維陣列 a[10][arr.length] 表示桶，分別用于存盤符合 0 ~ 9 的資料， Step2：按照 個位 進行劃分， 38 個位為 8，進入 a[8] 桶， 65 個位為 5，進入 a[5] 桶， 97 個位為 7，進入 a[7] 桶， 76 個位為 6，進入 a[6] 桶， 13 個位為 3，進入 a[3] 桶， 27 個位為 7，進入 a[7] 桶， 49 個位為 9，進入 a[9] 桶， 即： 0 1 2 3 13 4 5 65 6 76 7 97 27 8 38 9 49 依次取出桶中元素，存入新陣列中，即 {13, 65, 76, 97, 27, 38, 49} Step3：根據新陣列按照 十位 進行劃分， 13 十位為 1，進入 a[1] 桶， 65 十位為 6，進入 a[6] 桶， 76 十位為 7，進入 a[7] 桶， 97 十位為 9，進入 a[9] 桶， 27 十位為 2，進入 a[2] 桶， 38 十位為 3，進入 a[3] 桶， 49 十位為 4，進入 a[4] 桶， 即： 0 1 13 2 27 3 38 4 49 5 6 65 7 76 8 9 97 依次取出桶中元素，存入新陣列中，即 {13, 27, 38, 49, 65, 76, 97}
（2）代碼實作
【代碼實作：】 package com.lyh.sort; import java.util.Arrays; public class RadixSort { public static void main(String[] args) { int[] arrays = new int[]{38, 65, 97, 76, 13, 27, 49}; radixSort(arrays); System.out.println("===================="); // int[] arrays = new int[]{38, 65, 0, -1, 13, 27, 49}; int[] arrays2 = new int[]{38, 65, 0, -1, 13, 27, -10}; radixSort(arrays2); } /** * 基數排序（包括負數排序） * @param arrays 待排序陣列 */ public static void radixSort(int[] arrays) { // 判斷陣列是否合法 if (arrays.length <= 0) { System.out.println("資料為空"); return; } // 獲取當前資料中最大值、最小值 int max = arrays[0]; int min = arrays[0]; for (int array : arrays) { if (max < array) { max = array; } if (min > array) { min = array; } } // min 小于 0，即當前存在負數，則將所有資料 加上 min 的絕對值，使其變為非負數 if (min < 0) { for (int i = 0; i < arrays.length; i++) { arrays[i] -= min; } max -= min; } // 定義二維陣列，用于表示 桶，存盤資料，bucket[0] ~ bucket[9] 分別用于存盤 0 ~ 9 的資料 int[][] bucket = new int[10][arrays.length]; // 定義一維陣列，用于表示 每個桶存盤 資料的個數，bucketCount[0] ~ bucketCount[9] 分別用于存盤 bucket[0] ~ bucket[9] 中資料的個數 int[] bucketCount = new int[10]; // 獲取當前 最大值 的位數，根據 位數 確定需要進行 幾次 資料劃分操作 int maxLength = (max + "").length(); // 根據位數，按照 個位、十位、百位、千位 的順序進行劃分 for (int i = 0, m = 1; i < maxLength; i++, m *= 10) { // 遍歷陣列，將資料劃分到 桶中存盤 for (int j = 0; j < arrays.length; j++) { int temp = arrays[j] / m % 10; // 獲取 個位、十位、百位 的值 bucket[temp][bucketCount[temp]++] = arrays[j]; // 桶存盤資料，相應的 bucketCount 也要加 1 } int index = 0; // 用于記錄新陣列最后一個值的索引 // 遍歷桶，取出資料組成新的陣列, k < bucketCount.length 或者 k < bucket[0].length 均可，都表示 10（0 ~ 9） for (int k = 0; k < bucketCount.length; k++) { // 當前桶存在資料時，取出資料存入陣列中，并將該桶置空 // 此處只需將 bucketCount 相應位置置 0 即可（無需將 bucket 置空，每次存盤資料時均會覆寫，盡管會存在無用值，但無影響） if (bucketCount[k] > 0) { // 將桶元素復制到新陣列中 // 源陣列 bucket[k]， 開始位置 0， 目標陣列 arrays，目標陣列起始位置 index，復制源陣列的資料個數 bucketCount[k] System.arraycopy(bucket[k],0, arrays, index, bucketCount[k]); index += bucketCount[k]; // 當前桶記錄清空 bucketCount[k] = 0; } } System.out.println("第 " + (i + 1) + " 次劃分結果： " + Arrays.toString(arrays)); } // 如果存在負數，則需要減去 相應的值 if (min < 0) { for (int i = 0; i < arrays.length; i++) { arrays[i] += min; } } System.out.println("最終排序結果為： " + Arrays.toString(arrays)); } } 【輸出結果：】 第 1 次劃分結果： [13, 65, 76, 97, 27, 38, 49] 第 2 次劃分結果： [13, 27, 38, 49, 65, 76, 97] 最終排序結果為： [13, 27, 38, 49, 65, 76, 97] ==================== 第 1 次劃分結果： [10, 0, 23, 75, 37, 48, 9] 第 2 次劃分結果： [0, 9, 10, 23, 37, 48, 75] 最終排序結果為： [-10, -1, 0, 13, 27, 38, 65]
（3）分析：
若資料中出現相同的值，且向桶存放資料以及從桶取資料的程序中不會出現交換值的情況，故排序是穩定的，
每次均會遍歷資料 n，且最大位數為 k，即 時間復雜度為 O(n*k)，
需要使用二維陣列存盤 桶元素，使用一維陣列存盤 桶存盤元素個數，即空間復雜度為 O(10 * n + 10)，即空間復雜度為 O(n)，
四、查找演算法
1、順序（線性）查找
（1）什么是 線性查找？
最簡單直接的一種查找方式，基本思想是 對于待查找資料 key， 從資料的第一個記錄開始，逐個 與 key 比較，若存在與 key 相同的值則查找成功，若不存在則查找失敗，
（2）代碼實作
【代碼實作：】 package com.lyh.search; public class LinearSearch { public static void main(String[] args) { int[] arrays = new int[]{100, 40, 78, 24, 10, 16}; int key = 10; int index = linearSearch(arrays, key); if (index != -1) { System.out.println("查找成功，下標為： " + index); } else { System.out.println("查找失敗"); } } /** * 順序查找，回傳元素下標 * @param arrays 待查找陣列 * @param key 待查找資料 * @return 查找失敗回傳 -1，查找成功回傳 0 ~ n-1 */ public static int linearSearch(int[] arrays, int key) { // 遍歷陣列，挨個匹配 for (int i = 0; i < arrays.length; i++) { if (arrays[i] == key) { return i; } } return -1; } } 【輸出結果：】 查找成功，下標為： 4
（3）分析
順序查找效率是比較低的，n 個資料最壞情況下需要比較 n 次，即時間復雜度為 O(n)，
2、二分（折半）查找
（1）什么是 折半查找？
是一個效率較高的查找方法，其要求必須采用 順序存盤結構 且 存盤資料有序，
【基本實作思路：】 Step1：確定陣列的中間下標， middle = (left + right) / 2，將資料 分為左右兩部分， Step2：將待查找資料 key 與 中間元素 arrays[middle] 比較， Step2.1：如果 key > arrays[middle]，則說明要查找資料在 middle 下標右側，需要在右側資料進行查找（遞回）， Step2.2：如果 key < arrays[middle]，則說明要查找資料在 middle 下標左側，需要在左側資料進行查找（遞回）， Step2.3：如果 key == arrays[middle]，則說明查找成功， 上面遞回結束條件： 查找成功，結束遞回， 查找失敗，即 left > right 時，退出遞回， 【舉例：】 在 {13, 27, 38, 49, 65, 76, 97} 中查找 key = 27， 第一次折半： left = 0, right = 6, middle = 3 即 a[left] = 13, a[right] = 97, a[middle] = 49， 由于待查找資料 key < a[middle]，則從左側剩余資料 {13, 27, 38, 49} 開始查找， 第二次折半： left = 0, right = 2, middle = 1 即 a[left] = 0, a[right] = 38, a[middle] = 27， 由于待查找資料 key == a[middle]，則查找成功，
（2）代碼實作
【代碼實作：】 package com.lyh.search; public class BinarySearch { public static void main(String[] args) { int[] arrays = new int[]{13, 27, 38, 49, 65, 76, 97}; int key = 27; int index = binarySearch(arrays, 0, arrays.length - 1, key); if (index != -1) { System.out.println("查找成功，下標為： " + index); } else { System.out.println("查找失敗"); } } /** * 折半查找，回傳元素下標 * @param arrays 待查找陣列 * @param left 最左側下標 * @param right 最右側下標 * @param key 待查找資料 * @return 查找失敗回傳 -1，查找成功回傳元素下標 0 ~ n */ public static int binarySearch(int[] arrays, int left, int right, int key) { // 若 left > right，則表示查找失敗 if (left <= right) { // 獲取中間下標 int middle = (left + right) / 2; if (key == arrays[middle]) { return middle; } else if (key > arrays[middle]) { return binarySearch(arrays, middle + 1, right, key); } else { return binarySearch(arrays, left, middle - 1, key); } } return -1; } } 【輸出結果：】 查找成功，下標為： 1
（3）分析：
每次查找資料均折半，設折半次數為 x，則 2^x = n，即折半次數為 x = logn，時間復雜度為 O(logn)，效率比順序查找高，
3、插值查找
（1）什么是插值查找？
插值查找類似于 折半查找，其區別在于 中間節點 是自適應的，
采用自適應節點是為了 使 middle 值更靠近 key，從而 減少 key 比較次數，
【插值查找、折半查找區別：】 折半查找 求 middle： middle = (left + right) / 2 = left + (right - left) / 2. 插值查找 求 middle： middle = left + (right - left) * (key - a[left]) / (a[right] - a[left]). 即 使用 (key - a[left]) / (a[right] - a[left]) 去替換 1 / 2，可以在某種情況下提高查找效率， 對于資料量較大、且資料分布較均勻的 資料來說，使用 插值查找 速度較快（較少比較次數）， 注： 除法可能會遇到例外（java.lang.ArithmeticException: / by zero）， 【舉例：】 對于 0 ~ 99 的數，查找 27， 若采用 折半查找，需要折半 5 次， 若采用 插值查找，需要折半 1 次，
（2）代碼實作
【代碼實作：】 package com.lyh.search; public class InsertionSearch { public static void main(String[] args) { int[] arrays = new int[100]; for(int i = 0; i < arrays.length; i++) { arrays[i] = i; } int key = 27; int index = insertionSearch(arrays, 0, arrays.length - 1, key); if (index != -1) { System.out.println("查找成功，下標為： " + index); } else { System.out.println("查找失敗"); } } /** * 插值查找，回傳元素下標 * @param arrays 待查找陣列 * @param left 最左側下標 * @param right 最右側下標 * @param key 待查找資料 * @return 查找失敗回傳 -1，查找成功回傳元素下標 0 ~ n */ public static int insertionSearch(int[] arrays, int left, int right, int key) { // 資料不符合時，退出遞回 if (left > right || key > arrays[right] || key < arrays[left]) { return -1; } // 自適應節點 int middle = left + (right - left) * (key - arrays[left]) / (arrays[right] - arrays[left]); if (key == arrays[middle]) { return middle; } else if (key > arrays[middle]) { return insertionSearch(arrays, middle + 1, right, key); } else { return insertionSearch(arrays, left, middle + 1, key); } } } 【輸出結果：】 查找成功，下標為： 27
4、斐波那契（黃金分割）查找
（1）什么是 斐波那契 查找？
斐波那契查找 與 折半查找、插值查找 類似，都是改變中間節點的位置，
此時的 中間節點 位于 黃金分割點 附近，
【黃金分割比例：】 黃金分割比例指 將一個整體分為兩個部分，其中 較小部分 : 較大部分 = 較大部分 : 整體，且值約為 0.618，此比例稱為黃金分割比例， 比如： 1 米長繩子，分為 0.618 與 0.382 兩部分，則 0.382 ：0.618 == 0.618 ：1， 【斐波那契數列：】 斐波那契公式： f(1) = 1; f(2) = 1; f(n) = f(n - 1) + f(n - 2); n > 2 即：數列 {1, 1, 2, 3, 5, 8, 13, 21, 34, 55, ...} 斐波那契數列兩個相鄰數的比例，近似于 0.618， 比如： 21 : 34 == 0.6176470588235294 : 1 34 : 55 == 0.6181818181818182 : 1 【斐波那契查找演算法原理：】 如何求黃金分割點： 由于斐波那契數列公式為 f(n) = f(n - 1) + f(n - 2)， 且 f(n -1 ) : f(n - 2) == 0.618， 想要使用 斐波那契處理 資料，即將資料按照 f(n-1) 與 f(n-2) 分成兩部分即可， 比如：f(n) - 1 = (f(n - 1) - 1) + (f(n - 2) - 1 + 1); 分為 (f(n - 1) - 1) 與 (f(n - 2) - 1 + 1) 兩部分， 此時 left + (f(n - 1) - 1) 即為黃金分割點 middle， 斐波那契查找： 其將一組資料長度 看成是 斐波那契數列 進行處理，若當前資料長度 不滿足 斐波那契數列，則使用 最后一個元素將其補齊， 長度符合后，記新陣列為 temp，根據 middle 計算出中間節點，并進行判斷， 若 key > temp[middle]，則需要在右側進行遞回判斷，而此時右側屬于 f(n - 2) 部分，即 k = k - 2; 若 key < temp[middle]，則需要在左側進行遞回判斷，而此時左側屬于 f(n - 1) 部分，即 k = k - 1; 若 key == temp[middle]，則查找成功， 【舉例：】 在 {13, 27, 38, 49, 65, 76, 97} 中查找 key = 27， Step1：補齊資料， 當前資料 arrays 長度為 7，而與之相近的斐波那契數列值為 8（f(n) = 8， n = 5），需要將其補齊， 即資料變為 temp = {13, 27, 38, 49, 65, 76, 97, 97}. Step2：開始第一次查找操作，中間節點 middle = left + (f(n - 1) - 1) left = 0，right = 7，n = 5，middle = 4, key < temp[middle]，即下次在左側 {13, 27, 38, 49} 進行查找（right = middle - 1 = 3）， 左側部分等同于 f(n - 1) 區，所以 n 減 1, 即 n = 4， Step3：開始第二次查找， left = 0， right = 3，n = 4， middle = 2 key < temp[middle]，即下次在左側 {13, 27} 進行查找（right = middle - 1 = 1）， 左側部分等同于 f(n - 1) 區，所以 n 減 1， 即 n = 3， Step3：開始第三次查找， left = 0， right = 1，n = 3， middle = 1 key == temp[middle]，查找成功，
（2）代碼實作
【代碼實作：】 package com.lyh.search; import java.util.Arrays; public class FibonacciSearch { public static void main(String[] args) { int[] arrays = new int[]{13, 27, 38, 49, 65, 76, 97}; int key = 27; int index = fibonacciSearch(arrays, key); if (index != -1) { System.out.println("查找成功，當前下標為： " + index); } else { System.out.println("查找失敗"); } } /** * 回傳斐波那契陣列（使用 迭代 實作） * @return 斐波那契陣列 */ public static int[] fibonacci(int length) { if (length < 0) { return null; } int[] fib = new int[length]; if (length >= 1) { fib[0] = 1; } if (length >= 2) { fib[1] = 1; } for (int i = 2; i < length; i++) { fib[i] = fib[i - 1] + fib[i - 2]; } return fib; } /** * 斐波那契查找，回傳對應資料下標 * 將資料長度看成 斐波那契數列，將資料分為 f(n - 1)、 f(n - 2) 兩部分 * @param arrays 待查找陣列 * @param key 待查找資料 * @return 查找失敗回傳 -1，查找成功回傳相應的下標 */ public static int fibonacciSearch(int[] arrays, int key) { int n = 0; // 用于記錄當前 分隔點 下標 int[] fibs = fibonacci(arrays.length); // 用于記錄斐波那契數列 // 獲取第一次分割點下標 while (arrays.length > fibs[n]) { n++; } // 若當前陣列長度 不滿足 斐波那契數列，則使用最后一個元素 去填充新陣列，使新長度滿足 斐波那契數列 int[] temp = Arrays.copyOf(arrays, fibs[n]); for (int i = arrays.length; i < fibs[n]; i++) { temp[i] = arrays[arrays.length - 1]; } // 開始查找 int left = 0; int right = temp.length - 1; while(left <= right) { // 獲取中間節點，將資料區域分為 f(n - 1), f(n - 2) 兩部分 int middle = left + fibs[n - 1] - 1; if (key == temp[middle]) { // 查找成功 return middle; } else if (key > temp[middle]) { // 當前查找失敗，下次在右側 f(n - 2) 區域進行查找 left = middle + 1; n -= 2; } else { // 當前查找失敗，下次在左側 f(n - 1) 區域進行查找 right = middle - 1; n -= 1; } } // 查找失敗，即 left > right，回傳 -1 return -1; } } 【輸出結果：】 查找成功，當前下標為： 1
五、哈希表、樹
1、哈希表（散串列）
（1）什么是哈希表？
哈希表是一種 根據 關鍵碼（key） 直接訪問值（value）的 一種資料映射結構，其通過一個映射函式，將 關鍵碼 映射到 表中的某一個位置 進行訪問（可以提高查找速度），
哈希表可以使用 陣列 + 鏈表、 或者 陣列 + 二叉樹 的形式實作，
適用于 查詢性能要求高、資料之間無邏輯關系 的場景，
【陣列 + 鏈表 形式實作哈希表：】 基本結構： 使用 陣列（連續的存盤空間） 表示一個散串列， 每個陣列元素 存盤的 是一個 單鏈表（用于存盤 映射函式 相同的值）， 即 鏈表陣列，定義一個 鏈表結構，在用其 定義陣列， 基本程序： 對于一個數，通過 散列函式（hash()，可以通過 取模 或者 位運算） 計算 key，并將其映射到 散串列（陣列）的 某個位置， 對于相同的 hash 值（產生 hash 沖突），通常采用 拉鏈法來解決， 簡單地講，就是將 hash(key) 得到的結果 作為 陣列的下標，若多個 key 的 hash(key) 相同，那么在當前陣列下標的位置建立一個鏈表來保存資料， 【陣列 + 鏈表 形式實作哈希表 核心代碼結構：】 Step1：定義鏈表節點： /** * 鏈表節點 * @param <K> key * @param <V> value */ class Node<K, V> { K key; // key，用于 散列函式 計算的值 V value; // value，節點真實存盤資料 Node<K, V> next; // 指向下一個節點 public Node(K key, V value) { this.key = key; this.value =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ value; } } Step2：構建鏈表： /** * 鏈表，用于存盤資料 * @param <K> * @param <V> */ class NodeList<K, V> { Node<K, V> first; // 第一個節點，即存盤真實資料，非頭指標 } Step3：構建鏈表陣列，以及散列函式， /** * 定義 哈希 結構，鏈表陣列 * @param <K> * @param <V> */ class HashTable<K, V> { private int size = 16; // 默認大小為 16 NodeList<K, V>[] table; // 鏈表陣列，散列函式 確定 陣列下標位置，陣列元素（鏈表） 用于存盤值 public HashTable() { this(16); } public HashTable(int size) { // 保存哈希表大小 this.size = size; // 構建哈希表（陣列） this.table = new NodeList[this.size]; // 初始化每個陣列元素 -- 鏈表，否則默認為 null for (int i = 0; i < this.size; i++) { this.table[i] = new NodeList<>(); } } /** * 散列函式，此處以 模運算 為例，可以使用 位運算 * @param key 待計算的 key * @return 哈希值（陣列下標） */ public int hash(K key) { return key.hashCode() % size; } } 【實作簡單的增、查：】 添加節點： 首先根據 key 通過 散列函式 計算后，得到 陣列下標， 根據陣列下標定位到 相應的鏈表，然后進行添加操作， 若當前鏈表為空，則添加資料為第一個節點， 若當前鏈表不空，則遍歷鏈表，若發現相同 key，則替換其 value， 若沒有相同 key，則遍歷到鏈表末尾并添加節點， 查找節點： 同樣根據 key 計算出陣列下標，然后定位到相應的鏈表， 遍歷鏈表，并比較 key，若 key 相同則回傳 value， 若鏈表遍歷完成仍不存在相同 key 則回傳 null，
（2）代碼實作
【代碼實作：】 package com.lyh.tree; public class HashTableDemo { public static void main(String[] args) { HashTable<Integer, String> hashTable = new HashTable<>(4); hashTable.list(); System.out.println("================="); for (int i = 0; i < 10; i++) { hashTable.put(i, i + ""); } hashTable.list(); System.out.println("================="); hashTable.put(1, "Java"); hashTable.put(2, "Python"); hashTable.list(); System.out.println("================="); System.out.println("key = 2 的 value 為： " + hashTable.get(2)); } } /** * 定義 哈希 結構，鏈表陣列 * @param <K> * @param <V> */ class HashTable<K, V> { private int size = 16; // 默認大小為 16 NodeList<K, V>[] table; // 鏈表陣列，散列函式 確定 陣列下標位置，陣列元素（鏈表） 用于存盤值 public HashTable() { this(16); } public HashTable(int size) { // 保存哈希表大小 this.size = size; // 構建哈希表（陣列） this.table = new NodeList[this.size]; // 初始化每個陣列元素 -- 鏈表，否則默認為 null for (int i = 0; i < this.size; i++) { this.table[i] = new NodeList<>(); } } /** * 散列函式，此處以 模運算 為例，可以使用 位運算 * @param key 待計算的 key * @return 哈希值（陣列下標） */ public int hash(K key) { return key.hashCode() % size; } /** * 向哈希表中添加資料 * @param key * @param value */ public void put(K key, V value) { // 通過 散列函式 根據 key 計算出 陣列下標位置，然后向鏈表中添加資料 this.table[hash(key)].add(key, value); } /** * 查找節點 * @param key 查找條件 * @return 節點資料 */ public V get(K key) { // 通過 散列函式 根據 key 計算出 陣列下標位置，然后從鏈表中取出資料 return this.table[hash(key)].find(key); } /** * 輸出哈希表 */ public void list() { // 遍歷陣列，輸出每個鏈表 for (int i = 0; i < this.size; i++) { this.table[i].list(i); } } } /** * 鏈表，用于存盤資料 * @param <K> * @param <V> */ class NodeList<K, V> { Node<K, V> first; // 第一個節點，即存盤真實資料，非頭指標 /** * 在鏈表末尾添加節點 * @param key key * @param value value */ public void add(K key, V value) { // 保存資料到 鏈表第一個節點 if (first == null) { first = new Node<>(key, value); return; } Node<K, V> temp = first; // 使用臨時變數保存 第一個節點，用于輔助鏈表遍歷 // 遍歷鏈表到末尾，并添加節點 while(temp.next != null) { // 如果 key 相等，則替換原來的 value if (key.equals(temp.key)) { temp.value = value; return; } temp = temp.next; } temp.next = new Node<>(key, value); } /** * 遍歷輸出鏈表 * @param i 當前陣列下標，表示當前為第 i+1 鏈表 */ public void list(int i) { Node<K, V> temp = first; // 使用臨時變數保存 第一個節點，用于輔助鏈表遍歷 // 判斷鏈表是否為空 if (temp == null) { System.out.println("第 " + (i + 1) + " 鏈表為空"); return; } // 遍歷輸出鏈表 System.out.print("第 " + (i + 1) + " 鏈表為： "); while(temp != null) { System.out.print("[ key = " + temp.key + ", value = "https://www.cnblogs.com/l-y-h/archive/2020/09/29/+ temp.value +" ] ==> "); temp = temp.next; } System.out.println(); } /** * 查找節點 * @param key 查找條件 * @return 查找失敗回傳 null，查找成功回傳相應節點的 value */ public V find(K key) { Node<K, V> temp = first; // 使用臨時變數保存 第一個節點，用于輔助鏈表遍歷 // 遍歷鏈表，若發現相同 key，則回傳 while(temp != null) { if (key.equals(temp.key)) { return temp.value; } temp = temp.next; } return null; } } /** * 鏈表節點 * @param <K> key * @param <V> value */ class Node<K, V> { K key; // key，用于 散列函式 計算的值 V value; // value，節點真實存盤資料 Node<K, V> next; // 指向下一個節點 public Node(K key, V value) { this.key = key; this.value =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ value; } } 【輸出結果：】 第 1 鏈表為空 第 2 鏈表為空 第 3 鏈表為空 第 4 鏈表為空 ================= 第 1 鏈表為： [ key = 0, value = https://www.cnblogs.com/l-y-h/archive/2020/09/29/0 ] ==> [ key = 4, value = 4 ] ==> [ key = 8, value = 8 ] ==> 第 2 鏈表為： [ key = 1, value = https://www.cnblogs.com/l-y-h/archive/2020/09/29/1 ] ==> [ key = 5, value = 5 ] ==> [ key = 9, value = 9 ] ==> 第 3 鏈表為： [ key = 2, value = https://www.cnblogs.com/l-y-h/archive/2020/09/29/2 ] ==> [ key = 6, value = 6 ] ==> 第 4 鏈表為： [ key = 3, value = https://www.cnblogs.com/l-y-h/archive/2020/09/29/3 ] ==> [ key = 7, value = 7 ] ==> ================= 第 1 鏈表為： [ key = 0, value = https://www.cnblogs.com/l-y-h/archive/2020/09/29/0 ] ==> [ key = 4, value = 4 ] ==> [ key = 8, value = 8 ] ==> 第 2 鏈表為： [ key = 1, value = https://www.cnblogs.com/l-y-h/archive/2020/09/29/Java ] ==> [ key = 5, value = 5 ] ==> [ key = 9, value = 9 ] ==> 第 3 鏈表為： [ key = 2, value = https://www.cnblogs.com/l-y-h/archive/2020/09/29/Python ] ==> [ key = 6, value = 6 ] ==> 第 4 鏈表為： [ key = 3, value = https://www.cnblogs.com/l-y-h/archive/2020/09/29/3 ] ==> [ key = 7, value = 7 ] ==> ================= key = 2 的 value 為： Python
2、樹
（1）什么是樹？
樹是一種 由 n 個節點組成的一種 具有層次關系的、類似樹形的 資料結構，
其每個節點 均有 零個或 多個 子節點，每一個節點最多只有一個 父節點，沒有父節點的 節點 稱為 根節點，
（2）為什么需要樹 這種 資料結構？
前面介紹了 陣列、鏈表、以及 哈希表 等資料結構，可以用來存盤資料，
所謂 存在即合理，每種資料結構的出現，必然能解決某種問題，下面分析一下優缺點，
【陣列存盤：】 陣列采用 連續的 存盤方式來 存盤元素，查詢快、增刪慢， 優點： 可以通過 下標的方式 來訪問（查找）元素，速度快， 且對于有序陣列，可以通過 折半查找、插值查找 等方式提高 查找（檢索）效率， 缺點： 對于 插入操作，可能會伴隨著 陣列擴容、陣列元素整體后移等操作，效率較低， 【鏈表存盤：】 鏈表采用 不連續的 存盤方式來 存盤元素，增刪快、查詢慢， 優點： 插入、洗掉節點時，無需整體移動元素，只需要修改 前、后 指標域 即可，效率較高， 缺點： 進行查找時，需要從頭開始遍歷鏈表，若鏈表過長，查詢效率將會較低， 【哈希存盤：】 哈希 采用 陣列 + 鏈表 的方式存盤元素，每個 陣列元素 存盤的是一個 鏈表， 優點： 其結合了 陣列、鏈表 的優點，增、刪、改、查 效率都可以，時間復雜度為 O(1)， 缺點： 由于哈希 存盤的元素是無序的，若想按 順序輸出，實作起來就有點 麻煩， 且哈希只是單次查詢效率高，若執行 n 次查找，時間復雜度將退化到 O(n)， 哈希表由陣列實作，擴容也是影響效率的一個問題， 【樹存盤：（以二叉排序樹為例）】 二叉排序樹要求 任何一個 非葉子節點，其左子節點小于 當前節點，其右子節點 大于當前節點， 即 資料是有序的（中序遍歷可得到有序序列），其在一定程度上保證 增刪 以及 查找的速率 較高， 注： 二叉排序樹可能存在三種定義： 左子節點 小于等于 當前節點，右子節點 大于 當前節點， 左子節點 小于 當前節點，右子節點 大于等于 當前節點， 左子節點 小于 當前節點，右子節點 大于 當前節點，
（3）常見樹分類：
二叉樹、二叉排序樹（BST）、平衡二叉樹（AVL）、2-3 樹、B 樹（B-Tree）、B+ 樹、赫夫曼樹、紅黑樹 等，
3、二叉樹、遍歷二叉樹(遞回實作 前序、中序、后序 遍歷)
（1）二叉樹基本概念：
二叉樹 是一種要求 每個節點 最多只有 兩個子節點 的樹結構，
注：
樹 轉 陣列：
可以通過 前序遍歷、中序遍歷、后序遍歷 三種遍歷形式 遍歷 二叉樹 得到，
陣列 轉 樹：
根據 前序遍歷 + 中序遍歷 得到的陣列資料 逆向推出 二叉樹，
根據 中序遍歷 + 后序遍歷 得到的陣列資料 逆向推出 二叉樹，
根據順序二叉樹的 特點（2*n + 1 、2*n + 2） 構建 順序二叉樹，
【二叉樹常見分類：】 滿二叉樹： 如果 一個 n 層的二叉樹 的所有葉子節點均在最后一層， 且節點總數為 2^n - 1，則該樹為 滿二叉樹， 完全二叉樹： 一棵深度為 k 的有 n 個結點的二叉樹，對樹中的結點按從上至下、從左到右的順序進行編號， 如果編號為 i（1 ≤ i ≤ n）的結點與滿二叉樹中編號為 i 的結點在二叉樹中的位置相同，則這棵二叉樹稱為完全二叉樹， 順序二叉樹： 是二叉樹的一種 存盤形式（按照陣列順序，從上到下、從左到右 依次 給二叉樹 添加樹節點，得到一個完全二叉樹 或者 滿二叉樹）， 其 可以在 陣列 與 樹 之間相互轉換，即 根據一個陣列，可以得到 樹 的結構，從樹也可以反推 陣列， 特點： 順序二叉樹通常只考慮 完全二叉樹， 其第 n 個元素的左子節點為 2*n + 1， 其第 n 個元素的右子節點為 2*n + 2， 其第 n 個元素的父節點為 (n - 1) / 2， （n 從 0 開始，即從陣列第一個元素下標開始計數）， 線索二叉樹： 對于 n 個節點的 二叉樹，其總共含有 2*n - (n - 1) = n + 1 個空的指標域， 利用這些空的指標域，存放 當前節點 在 某次遍歷（前序、中序、后續）下的 前驅、后繼 節點的指標， 這些指向 前驅、后繼 節點的指標稱為 線索，使用這種線索的二叉樹 稱為線索二叉樹， 即 線索二叉樹的本質 是 將二叉樹 當前節點的空閑指標 改為 指向當前節點 前驅 或者 后繼 節點的程序， 而根據遍歷的分類，前驅、后繼節點會不同，可以分為： 前序線索二叉樹、中序線索二叉樹、后序線索二叉樹， 還有 二叉搜索樹（BST）、平衡二叉搜索樹（AVT）等后續介紹，
（2）二叉樹三種遍歷方式（樹 轉 陣列）
樹 轉 陣列：
樹 轉 陣列，也即 樹的各節點 的遍歷順序，按照 當前節點、左子節點、右子節點 遍歷的先后可以分為三種遍歷：前序遍歷、中序遍歷、后序遍歷，
此時以 遞回方式實作，后續會補充 迭代實作，
【前序遍歷：】 節點遍歷順序： 先輸出 當前節點，再輸出 左子節點，最后輸出 右子節點， 遍歷、查找步驟: 對于一顆 二叉樹，若二叉樹為空，則直接結束， 否則 輸出 當前節點（若為查找，則在此處進行 值 比較，查找成功則退出）， 前序遍歷 左子樹， 前序遍歷 右子樹， 洗掉節點： 洗掉的規則可以自定義，不同的規則對應不同的代碼實作， 比如：洗掉某帶有左、右子樹的節點，是整體洗掉 還是 將子節點 旋轉到當前節點位置， 此處以整體洗掉為例： 由于二叉樹是單向的（此處可以理解成 單鏈表 洗掉處理）， 需要判斷 當前節點的 子節點 是否為待洗掉的節點，若是，則直接將當前節點 子節點 置 null 即可， 即: if (this.left.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/= key) { this.left = null; return; } if (this.right.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/= key) { this.right = null; return; } 【中序遍歷：】 節點遍歷順序： 先輸出 左子節點，再輸出 當前節點，最后輸出 右子節點， 遍歷、查找步驟: 對于一顆 二叉樹，若二叉樹為空，則直接結束， 否則 前序遍歷 左子樹， 輸出 當前節點（若為查找，則在此處進行 值 比較）， 前序遍歷 右子樹， 【后序遍歷：】 節點遍歷順序： 先輸出 左子節點，再輸出 右子節點，最后輸出 當前節點， 遍歷、查找步驟: 對于一顆 二叉樹，若二叉樹為空，則直接結束， 否則 前序遍歷 左子樹， 前序遍歷 右子樹， 輸出 當前節點（若為查找，則在此處進行 值 比較）， 【代碼實作：】 package com.lyh.tree; /** * 構建二叉樹 * @param <K> */ public class BinaryTree<K> { private TreeNode<K> root; // 設定根節點 public BinaryTree(TreeNode<K> root) { this.root = root; } public static void main(String[] args) { // 構建二叉樹 TreeNode<String> root = new TreeNode<>("0"); TreeNode<String> treeNode = new TreeNode<>("1"); TreeNode<String> treeNode2 = new TreeNode<>("2"); TreeNode<String> treeNode3 = new TreeNode<>("3"); TreeNode<String> treeNode4 = new TreeNode<>("4"); root.left = treeNode; root.right = treeNode2; treeNode.left = treeNode3; treeNode.right = treeNode4; // 設定樹 根節點 BinaryTree<String> binaryTree = new BinaryTree<>(root); // 前序遍歷 System.out.print("前序遍歷： "); binaryTree.prefixList(); System.out.println("\n====================="); // 中序遍歷 System.out.print("中序遍歷： "); binaryTree.infixList(); System.out.println("\n====================="); // 后序遍歷 System.out.print("后序遍歷： "); binaryTree.suffixList(); System.out.println("\n====================="); // 前序查找 System.out.print("前序查找， "); TreeNode<String> search = binaryTree.prefixSearch("1"); if (search != null) { System.out.println("查找成功， 當前節點為： " + search + " ，其左節點為： " + search.left + " ，其右節點為： " + search.right); } else { System.out.println("查找失敗"); } System.out.println("\n====================="); // 洗掉節點 System.out.print("洗掉節點， "); int result = binaryTree.deleteNode("3"); if (result != -1) { System.out.println("成功"); } else { System.out.println("失敗"); } System.out.print("當前樹的前序遍歷為： "); binaryTree.prefixList(); System.out.println("\n====================="); } /** * 前序遍歷 */ public void prefixList() { // 判斷根節點是否存在 if (root == null) { System.out.println("當前樹為 空樹"); return; } // 存在根節點，則進行前序遍歷 root.prefixList(); } /** * 前序查找 */ public TreeNode<K> prefixSearch(K data) { // 判斷根節點是否存在 if (root == null) { return null; } // 存在根節點，則進行前序遍歷 return root.prefixSearch(data); } /** * 中序遍歷 */ public void infixList() { // 判斷根節點是否存在 if (root == null) { System.out.println("當前樹為 空樹"); return; } // 存在根節點，則進行中序遍歷 root.infixList(); } /** * 后序遍歷 */ public void suffixList() { // 判斷根節點是否存在 if (root == null) { System.out.println("當前樹為 空樹"); return; } // 存在根節點，則進行后序遍歷 root.suffixList(); } /** * 洗掉節點，洗掉失敗回傳 -1，否則回傳 1 * @param data 待洗掉節點 * @return 洗掉失敗回傳 -1，否則回傳 1 */ public int deleteNode(K data) { // 當根節點存在時，才可以進行洗掉節點操作 if (root != null) { // 若恰好為 根節點，則直接將根節點置 null if (data.equals(root.data)) { root = null; return 1; } // 否則遞回洗掉 return root.deleteNode(data); } return -1; } } /** * 定義樹節點 * @param <K> */ class TreeNode<K> { K data; // 保存節點資料 TreeNode<K> left; // 保存節點的 左子節點 TreeNode<K> right; // 保存節點的 右子節點 public TreeNode(K data) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } @Override public String toString() { return "TreeNode{ data= "https://www.cnblogs.com/l-y-h/archive/2020/09/29/+ data +"}"; } /** * 前序遍歷 */ public void prefixList() { // 輸出當前節點 System.out.print(this + " "); // 若左子樹不為空，則遞回前序遍歷 左子樹 if (this.left != null) { this.left.prefixList(); } // 若右子樹不為空，則遞回前序遍歷 右子樹 if (this.right != null) { this.right.prefixList(); } } /** * 前序查找 * @param data 待查找資料 * @return 查找失敗回傳 null，查找成功回傳相應的資料 */ public TreeNode<K> prefixSearch(K data) { // 若當前節點即為待查找節點，則直接回傳 if (data.equals(this.data)) { return this; } TreeNode<K> result = null; // 用于保存查找節點 // 如果左子樹不為空，則遞回前序查找 左子樹 if (this.left != null) { result = this.left.prefixSearch(data); } // 若左子樹查找成功，則回傳 if (result != null) { return result; } // 如果右子樹不為空，則遞回前序查找 右子樹 if (this.right != null) { result = this.right.prefixSearch(data); } return result; } /** * 中序遍歷 */ public void infixList() { // 若左子樹不為空，則遞回中序遍歷 左子樹 if (this.left != null) { this.left.infixList(); } // 輸出當前節點 System.out.print(this + " "); // 若右子樹不為空，則遞回中序遍歷 右子樹 if (this.right != null) { this.right.infixList(); } } /** * 后序遍歷 */ public void suffixList() { // 若左子樹不為空，則遞回后序遍歷 左子樹 if (this.left != null) { this.left.suffixList(); } // 若右子樹不為空，則遞回后序遍歷 右子樹 if (this.right != null) { this.right.suffixList(); } // 輸出當前節點 System.out.print(this + " "); } /** * 洗掉節點，此處若為非葉子節點，直接連同其 子節點 一起洗掉 * @param data 待洗掉資料 * @return 洗掉失敗回傳 -1，否則 回傳 1 */ public int deleteNode(K data) { // 如果洗掉節點 恰好為 左子節點，則直接將 左子節點 置 null if (this.left != null && data.equals(this.left.data)) { this.left = null; return 1; } // 如果洗掉節點 恰好為 右子節點，則直接將 右子節點 置 null if (this.right != null && data.equals(this.right.data)) { this.right = null; return 1; } int result = -1; // 若左子樹不為 null，則遞回左子樹 查找節點并洗掉 if (this.left != null) { result = this.left.deleteNode(data); if (result != -1) { return result; } } // 若右子樹不為 null，則遞回右子樹 查找節點并洗掉 if (this.right != null) { result = this.right.deleteNode(data); } return result; } } 【輸出結果：】 前序遍歷： TreeNode{ data= 0} TreeNode{ data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/1} TreeNode{ data= 3} TreeNode{ data= 4} TreeNode{ data= 2} ===================== 中序遍歷： TreeNode{ data= 3} TreeNode{ data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/1} TreeNode{ data= 4} TreeNode{ data= 0} TreeNode{ data= 2} ===================== 后序遍歷： TreeNode{ data= 3} TreeNode{ data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/4} TreeNode{ data= 1} TreeNode{ data= 2} TreeNode{ data= 0} ===================== 前序查找， 查找成功， 當前節點為： TreeNode{ data= 1} ，其左節點為： TreeNode{ data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/3} ，其右節點為： TreeNode{ data= 4} ===================== 洗掉節點， 成功 當前樹的前序遍歷為： TreeNode{ data= 0} TreeNode{ data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/1} TreeNode{ data= 4} TreeNode{ data= 2} =====================
4、還原二叉樹（前序 + 中序、后序 + 中序）
（1） 還原二叉樹（陣列 轉 樹）
前面通過 前序、中序、后序 遍歷 可以 得到樹的節點資料，那么根據 前序遍歷、中序遍歷、后序遍歷 得到的資料能否反推 出 樹結構呢？
陣列 轉 樹（此處 不考慮 陣列中存在相同值的情況，即各個樹節點均不同）：
使用 前序遍歷 + 中序遍歷 或者 后序遍歷 + 中序遍歷 的形式可以反推，
其中：
前序遍歷、后序遍歷 存在是為了 定位 根節點 所在位置，
根節點定位后，就可以將 中序遍歷 陣列 分為 左、右 兩部分（形成左、右 子樹），遞回處理即可，
使用 前序 + 后序 陣列的方式 雖然可以定位 根節點，但是不知道如何 劃分 左、右子樹，從而無法正確推匯出 二叉樹，
（2）思路分析、代碼實作
【前序遍歷結果 + 中序遍歷結果 還原 二叉樹：】 前序遍歷結果格式為： [{根節點}{左子樹}{右子樹}] 中序遍歷結果格式為： [{左子樹}{根節點}{右子樹}] 還原步驟： 前序結果 第一個值 必為 根節點（當前節點）， 通過該節點，可以將 中序結果 劃分為 左子樹、右子樹， 通過 中序結果 劃分的左子樹的大小 可以將 前序結果 除根節點外 的值 劃分為 左子樹、右子樹， 然后將 前序、中序 劃分的 左子樹、右子樹 進行遞回處理， 舉例： 前序遍歷結果： [0, 1, 3, 4, 2] 中序遍歷結果： [3, 1, 4, 0, 2] 第一次劃分： 前序結果：[0, 1, 3, 4, 2]，中序結果：[3, 1, 4, 0, 2] 根節點為 0，將中序結果劃分為 左子樹：[3, 1, 4], 右子樹: [2] 根據中序結果 左子樹大小劃分 前序結果為 左子樹：[1, 3 ,4], 右子樹：[2] 第二次劃分： 前序結果：[1, 3, 4]，中序結果：[3, 1, 4] 根節點為 1，將中序結果劃分為 左子樹：[3], 右子樹: [4] 根據中序結果 左子樹大小劃分 前序結果為 左子樹：[3], 右子樹：[4] 第三次劃分： 前序結果：[3]，中序結果：[3] 根節點為 3，將中序結果劃分為 左子樹：[], 右子樹: [] 根據中序結果 左子樹大小劃分 前序結果為 左子樹：[], 右子樹：[] 第四次劃分： 前序結果、中序結果 均為空，退出， 同理依次進行處理，，， 【后序遍歷結果 + 中序遍歷結果 還原 二叉樹：】 后序遍歷結果格式為： [{左子樹}{右子樹}{根節點}] 中序遍歷結果格式為： [{左子樹}{根節點}{右子樹}] 與 前序遍歷 處理類似，只是此時根節點 位于末尾， 還原步驟： 后序結果 最后一個值 必為 根節點（當前節點）， 通過該節點，可以將 中序結果 劃分為 左子樹、右子樹， 通過 中序結果 劃分的左子樹的大小 可以將 后序結果 除根節點外 的值 劃分為 左子樹、右子樹， 然后將 后序、中序 劃分的 左子樹、右子樹 進行遞回處理， 【代碼實作：】 package com.lyh.tree; import java.util.ArrayList; import java.util.Arrays; import java.util.List; public class ArrayToBinaryTree<K> { public static void main(String[] args) { // 構建二叉樹 TreeNode6<String> root = new TreeNode6<>("0"); TreeNode6<String> treeNode = new TreeNode6<>("1"); TreeNode6<String> treeNode2 = new TreeNode6<>("2"); TreeNode6<String> treeNode3 = new TreeNode6<>("3"); TreeNode6<String> treeNode4 = new TreeNode6<>("4"); root.left = treeNode; root.right = treeNode2; treeNode.left = treeNode3; treeNode.right = treeNode4; // 設定樹 根節點 ArrayToBinaryTree<String> binaryTree = new ArrayToBinaryTree<>(); // 獲取前序遍歷結果 List<String> prefixResult = binaryTree.prefixList(root); List<String> prefixResult2 = binaryTree.prefixList2(root); System.out.println("前序遍歷結果（方式一）： " + prefixResult); System.out.println("前序遍歷結果（方式二）： " + prefixResult2); System.out.println("================================="); // 獲取中序遍歷結果 List<String> infixResult = binaryTree.infixList(root); System.out.println("中序遍歷結果： " + infixResult); System.out.println("================================="); // 獲取后序遍歷結果 List<String> suffixResult = binaryTree.suffixList(root); System.out.println("后序遍歷結果： " + suffixResult); System.out.println("================================="); // 使用 前序遍歷結果 + 中序遍歷結果 還原 二叉樹 TreeNode6 root2 = binaryTree.prefixAndInfixToTree(prefixResult.toArray(new String[]{}), infixResult.toArray(new String[]{})); System.out.println("還原后的二叉樹前序遍歷如下： " + binaryTree.prefixList(root2)); System.out.println("還原后的二叉樹中序遍歷如下： " + binaryTree.infixList(root2)); System.out.println("還原后的二叉樹后序遍歷如下： " + binaryTree.suffixList(root2)); System.out.println("================================="); // 使用 后序遍歷結果 + 中序遍歷結果 還原 二叉樹 TreeNode6 root3 = binaryTree.suffixAndInfixToTree(suffixResult.toArray(new String[]{}), infixResult.toArray(new String[]{})); System.out.println("還原后的二叉樹前序遍歷如下： " + binaryTree.prefixList(root3)); System.out.println("還原后的二叉樹中序遍歷如下： " + binaryTree.infixList(root3)); System.out.println("還原后的二叉樹后序遍歷如下： " + binaryTree.suffixList(root3)); System.out.println("================================="); } /** * 根據 前序遍歷結果 + 中序遍歷結果 還原 二叉樹（此處不考慮 二叉樹 節點相同值，即默認 二叉樹 節點均不相同、沒有重復元素） * @param prefixResult 前序遍歷結果 * @param infixResult 中序遍歷結果 * @return 樹的根節點 */ public TreeNode6<K> prefixAndInfixToTree(K[] prefixResult, K[] infixResult) { // 遞回結束條件 if (prefixResult == null || infixResult == null || prefixResult.length <= 0 || infixResult.length <= 0) { return null; } // 前序遍歷結果 第一個值 肯定為 樹的根節點 TreeNode6<K> root = new TreeNode6<>(prefixResult[0]); // 查找、記錄 中序序列 中 根節點 位置 int index = 0; for (int i = 0; i < infixResult.length; i++) { if (prefixResult[0].equals(infixResult[i])) { index = i; break; } } // 根據 根節點，將 中序遍歷結果 劃分為 左子樹 以及 右子樹，中序結果 左邊即為左子樹，右邊即為 右子樹 // 中序遍歷結果：[{左子樹}{根節點}{右子樹}] K[] leftInfixResult = Arrays.copyOfRange(infixResult, 0, index); K[] rightInfixResult = Arrays.copyOfRange(infixResult, index + 1, infixResult.length); // 根據左子樹 個數，將剩余 前序遍歷 結果劃分為 左子樹、右子樹 // 前序遍歷結果為：[{根節點}{左子樹}{右子樹}] K[] leftPrefixResult = Arrays.copyOfRange(prefixResult, 1, leftInfixResult.length + 1); K[] rightPrefixResult = Arrays.copyOfRange(prefixResult, leftInfixResult.length + 1, prefixResult.length); // 設定 根（當前）節點 左、右子樹 root.left = prefixAndInfixToTree(leftPrefixResult, leftInfixResult); root.right = prefixAndInfixToTree(rightPrefixResult, rightInfixResult); return root; } /** * 根據 后序遍歷結果 + 前序遍歷結果 還原 二叉樹 * @param suffixResult 后序遍歷結果 * @param infixResult 前序遍歷結果 * @return 樹的根節點 */ public TreeNode6<K> suffixAndInfixToTree(K[] suffixResult, K[] infixResult) { if (suffixResult == null || infixResult == null || suffixResult.length <= 0 || infixResult.length <= 0) { return null; } // 后序遍歷結果 最后一個值 肯定為 根節點（當前節點） TreeNode6<K> root = new TreeNode6<>(suffixResult[suffixResult.length - 1]); // 查找、記錄 中序序列 中 根節點 位置 int index = 0; for(int i = 0; i < infixResult.length; i++) { if (root.data.equals(infixResult[i])) { index = i; break; } } // 根據 根節點，將 中序遍歷結果 劃分為 左子樹 以及 右子樹，中序結果 左邊即為左子樹，右邊即為 右子樹 // 中序遍歷結果：[{左子樹}{根節點}{右子樹}] K[] leftInfixResult = Arrays.copyOfRange(infixResult, 0, index); K[] rightInfixResult = Arrays.copyOfRange(infixResult, index + 1, infixResult.length); // 根據左子樹 個數，將剩余 后序遍歷 結果劃分為 左子樹、右子樹 // 后序遍歷結果為：[{左子樹}{右子樹}{根節點}] K[] leftSuffixResult = Arrays.copyOfRange(suffixResult, 0, leftInfixResult.length); K[] rightSuffixResult = Arrays.copyOfRange(suffixResult, leftInfixResult.length, suffixResult.length - 1); // 設定 根（當前）節點 左、右子樹 root.left = suffixAndInfixToTree(leftSuffixResult, leftInfixResult); root.right = suffixAndInfixToTree(rightSuffixResult, rightInfixResult); return root; } /** * 回傳前序遍歷結果（方式一） * @param root 樹的根節點 * @return 前序遍歷結果 */ public List<K> prefixList(TreeNode6<K> root) { if (root == null) { System.out.println("當前為空樹"); return null; } return root.prefixList(new ArrayList<>()); } /** * 回傳前序遍歷結果（方式二） * @param root 樹的根節點 * @return 前序遍歷結果 */ public List<K> prefixList2(TreeNode6<K> root) { if (root == null) { System.out.println("當前為空樹"); return null; } List<K> result = new ArrayList<>(); root.prefixList2(result); return result; } /** * 中序遍歷 * @param root 樹的根節點 * @return 中序遍歷結果 */ public List<K> infixList(TreeNode6<K> root) { if (root == null) { System.out.println("當前為空樹"); return null; } List<K> result = new ArrayList<>(); root.infixList(result); return result; } /** * 后序遍歷 * @param root 樹的根節點 * @return 后序遍歷結果 */ public List<K> suffixList(TreeNode6<K> root) { if (root == null) { System.out.println("當前為空樹"); return null; } List<K> result = new ArrayList<>(); root.suffixList(result); return result; } } /** * 定義樹節點 * @param <K> */ class TreeNode6<K> { K data; // 保存節點資料 TreeNode6<K> left; // 保存 左子節點 TreeNode6<K> right; // 保存 右子節點 public TreeNode6(K data) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } /** * 前序遍歷（第一種方式：帶有回傳值的遍歷） * @param list 前序遍歷序列 * @return 前序遍歷結果 */ public List<K> prefixList(List<K> list) { // 用于保存當前序列，作用域只存在當前方法，回傳時 作用域消失，即 遞回時無需考慮會影響 上一次結果 List<K> result = new ArrayList<>(list); // 添加當前節點 result.add(this.data); // 遞回添加左子節點 if (this.left != null) { result = this.left.prefixList(result); } // 遞回添加右子節點 if (this.right != null) { result = this.right.prefixList(result); } return result; } /** * 前序遍歷（第二種方式：無回傳值的遍歷） * @param result 前序遍歷序列 */ public void prefixList2(List<K> result) { // 保存當前節點 result.add(this.data); // 遞回添加左子節點 if (this.left != null) { this.left.prefixList2(result); } // 遞回添加右子節點 if (this.right != null) { this.right.prefixList2(result); } } /** * 中序遍歷 * @param result 中序遍歷序列 */ public void infixList(List<K> result) { // 遞回遍歷 左子節點 if (this.left != null) { this.left.infixList(result); } // 保存當前節點 result.add(this.data); // 遞回遍歷 右子節點 if (this.right != null) { this.right.infixList(result); } } /** * 后序遍歷 * @param result 后序遍歷序列 */ public void suffixList(List<K> result) { // 遞回遍歷 左子節點 if (this.left != null) { this.left.suffixList(result); } // 遞回遍歷 右子節點 if (this.right != null) { this.right.suffixList(result); } // 保存當前節點 result.add(this.data); } } 【輸出結果：】 前序遍歷結果（方式一）： [0, 1, 3, 4, 2] 前序遍歷結果（方式二）： [0, 1, 3, 4, 2] ================================= 中序遍歷結果： [3, 1, 4, 0, 2] ================================= 后序遍歷結果： [3, 4, 1, 2, 0] ================================= 還原后的二叉樹前序遍歷如下： [0, 1, 3, 4, 2] 還原后的二叉樹中序遍歷如下： [3, 1, 4, 0, 2] 還原后的二叉樹后序遍歷如下： [3, 4, 1, 2, 0] ================================= 還原后的二叉樹前序遍歷如下： [0, 1, 3, 4, 2] 還原后的二叉樹中序遍歷如下： [3, 1, 4, 0, 2] 還原后的二叉樹后序遍歷如下： [3, 4, 1, 2, 0] =================================
5、順序二叉樹（陣列 與 樹 互轉）
（1）什么是順序二叉樹：
是二叉樹的一種 存盤形式（按照陣列順序，從上到下、從左到右 依次 給二叉樹 添加樹節點，得到一個完全二叉樹 或者 滿二叉樹），
其 可以在 陣列 與 樹 之間相互轉換，即 根據一個陣列，可以得到 樹 的結構，從樹也可以反推 陣列，
特點：
順序二叉樹通常只考慮 完全二叉樹，
其第 n 個元素的左子節點為 2*n + 1，
其第 n 個元素的右子節點為 2*n + 2，
其第 n 個元素的父節點為 (n - 1) / 2， （n 從 0 開始，即從陣列第一個元素下標開始計數），
（2）代碼實作：
【核心：】 對于第 n 個元素（n 從 0 開始計數）： 其左子節點為 2*n + 1， 其右子節點為 2*n + 2， 無論 陣列 轉 樹 還是 樹 轉 陣列，都是根據這兩個 值進行對應， 注： 通過先序、中序、后序 可以遍歷樹， 那么在遍歷的同時將節點 設定到相應的 陣列下標處，那么即可完成 樹 轉 陣列， 【代碼實作：】 package com.lyh.tree; import java.util.Arrays; public class ArrayBinaryTree<K> { private K[] arrays; public ArrayBinaryTree(K[] arrays) { this.arrays = arrays; } public static void main(String[] args) { // 構建陣列 Integer[] arrays = new Integer[]{1, 2, 3, 4, 5, 6, 7}; ArrayBinaryTree<Integer> arrayBinaryTree = new ArrayBinaryTree<>(arrays); // 陣列轉為 樹 TreeNode2 root = arrayBinaryTree.arraysToTree(); // 輸出陣列 System.out.println("陣列為： " + Arrays.toString(arrays)); System.out.println("=============================="); // 輸出樹 的前序遍歷結果 System.out.print("樹 的前序遍歷為： "); root.prefixList(); System.out.println("\n=============================="); // 輸出樹 的中序遍歷結果 System.out.print("樹 的中序遍歷為： "); root.infixList(); System.out.println("\n=============================="); // 輸出樹 的后序遍歷結果 System.out.print("樹 的后序遍歷為： "); root.suffixList(); System.out.println("\n=============================="); System.out.print("樹 轉為陣列為： "); Object[] result = arrayBinaryTree.treeToArray(root); System.out.println(Arrays.toString(result)); } /** * 陣列 轉 樹 * @return 樹的根節點，若陣列為空 則回傳 null， */ public TreeNode2<K> arraysToTree() { // 若陣列為空，則不進行 轉樹 操作 if (arrays == null || arrays.length == 0) { System.out.println("資料為空，無法轉為樹"); return null; } // 設定根節點 TreeNode2 root = new TreeNode2(arrays[0]); // 根據陣列值 構建樹 root.arrayToTree(arrays, 0); return root; } public Object[] treeToArray(TreeNode2<K> root) { // 判斷樹 是否為空樹 if (root == null) { System.out.println("資料為空，無法轉為陣列"); return null; } // 樹非空，計算樹節點個數 int length = root.size() + 1; // 宣告一個陣列 Object[] arrays = new Object[length]; // 將樹的資料 放入 陣列對應 下標處 root.treeToArray(arrays, 0); return arrays; } } /** * 定義樹節點 * @param <K> */ class TreeNode2<K> { K data; // 保存節點資料 TreeNode2<K> left; // 保存節點的 左子節點 TreeNode2<K> right; // 保存節點的 右子節點 public TreeNode2(K data) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } @Override public String toString() { return "TreeNode2{ data = "https://www.cnblogs.com/l-y-h/archive/2020/09/29/+ data +" }"; } /** * 陣列 轉 樹 * @param arrays 待轉換陣列 * @param index 當前陣列下標（從 0 開始，表示陣列第一個元素，同樣表示為 根節點） */ public void arrayToTree(K[] arrays, int index) { // 若當前節點存在 左節點，則遞回構建 左子樹 if (index * 2 + 1 < arrays.length) { this.left = new TreeNode2<>(arrays[index * 2 + 1]); this.left.arrayToTree(arrays, index * 2 + 1); } // 若當前節點存在 右節點，則遞回構建 右子樹 if (index * 2 + 2 < arrays.length) { this.right = new TreeNode2<>(arrays[index * 2 + 2]); this.right.arrayToTree(arrays, index * 2 + 2); } } /** * 二叉樹 轉 陣列（先序遍歷實作） * @param arrays 待轉換陣列 * @param index 陣列下標 */ public void treeToArray(Object[] arrays, int index) { // 設定當前節點 到相應的陣列下標處 arrays[index] = this.data; // 遍歷左子樹 if (this.left != null) { this.left.treeToArray(arrays, index * 2 + 1); } // 遍歷右子樹 if (this.right != null) { this.right.treeToArray(arrays, index * 2 + 2); } } /** * 前序遍歷 */ public void prefixList() { // 輸出當前節點 System.out.print(this + " "); // 若左子樹不為空，則遞回前序遍歷 左子樹 if (this.left != null) { this.left.prefixList(); } // 若右子樹不為空，則遞回前序遍歷 右子樹 if (this.right != null) { this.right.prefixList(); } } /** * 中序遍歷 */ public void infixList() { // 若左子樹不為空，則遞回中序遍歷 左子樹 if (this.left != null) { this.left.infixList(); } // 輸出當前節點 System.out.print(this + " "); // 若右子樹不為空，則遞回中序遍歷 右子樹 if (this.right != null) { this.right.infixList(); } } /** * 后序遍歷 */ public void suffixList() { // 若左子樹不為空，則遞回后序遍歷 左子樹 if (this.left != null) { this.left.suffixList(); } // 若右子樹不為空，則遞回后序遍歷 右子樹 if (this.right != null) { this.right.suffixList(); } // 輸出當前節點 System.out.print(this + " "); } /** * 求樹節點總數 * @return 樹節點總數 */ public int size() { int left = 0; // 左節點個數 int right = 0; // 右節點個數 // 遞回求左節點個數 if (this.left != null) { left = 1 + this.left.size(); } // 遞回求右節點個數 if (this.right != null) { right = 1 + this.right.size(); } // 回傳總個數 return left + right; } } 【輸出結果：】 陣列為： [1, 2, 3, 4, 5, 6, 7] ============================== 樹 的前序遍歷為： TreeNode2{ data = 1 } TreeNode2{ data = https://www.cnblogs.com/l-y-h/archive/2020/09/29/2 } TreeNode2{ data = 4 } TreeNode2{ data = 5 } TreeNode2{ data = 3 } TreeNode2{ data = 6 } TreeNode2{ data = 7 } ============================== 樹 的中序遍歷為： TreeNode2{ data = 4 } TreeNode2{ data = https://www.cnblogs.com/l-y-h/archive/2020/09/29/2 } TreeNode2{ data = 5 } TreeNode2{ data = 1 } TreeNode2{ data = 6 } TreeNode2{ data = 3 } TreeNode2{ data = 7 } ============================== 樹 的后序遍歷為： TreeNode2{ data = 4 } TreeNode2{ data = https://www.cnblogs.com/l-y-h/archive/2020/09/29/5 } TreeNode2{ data = 2 } TreeNode2{ data = 6 } TreeNode2{ data = 7 } TreeNode2{ data = 3 } TreeNode2{ data = 1 } ============================== 樹 轉為陣列為： [1, 2, 3, 4, 5, 6, 7]
6、線索二叉樹
（1）什么是線索二叉樹？
對于 n 個節點的 二叉樹，其總共含有 2*n - (n - 1) = n + 1 個空的指標域，
利用這些空的指標域，存放 當前節點 在 某次遍歷（前序、中序、后續）下的 前驅、后繼 節點的指標，
這些指向 前驅、后繼 節點的指標稱為 線索，使用這種線索的二叉樹 稱為線索二叉樹，
即 線索二叉樹的本質 是 將二叉樹 當前節點的空閑指標 改為 指向當前節點 前驅 或者 后繼 節點的程序，
而根據遍歷的分類，前驅、后繼節點會不同，可以分為：
前序線索二叉樹、中序線索二叉樹、后序線索二叉樹，
（2）代碼實作 中序線索二叉樹
【定義樹節點：】 對于每個節點的 左、右指標域 來說，可能是 空閑指標域，也可能指向 左、右 子節點， 需要對其進行區分，可以定義指標型別，比如：leftType，值為 0 時表示指向子節點， 值為 1 時表示為 空閑指標域（存盤線索 -- 前驅、后繼節點） 樹節點： class TreeNode3<K> { K data; // 保存節點資料 TreeNode3<K> left; // 保存左子節點 TreeNode3<K> right; // 保存右子節點 byte leftType; // 值為 0 時表示為 左子節點，值為 1 時表示存盤線索 -- 前驅節點 byte rightType; // 值為 0 時表示為 右子節點，值為 1 時表示存盤線索 -- 后繼節點 public TreeNode3(K data) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } @Override public String toString() { return "TreeNode3{ data= "https://www.cnblogs.com/l-y-h/archive/2020/09/29/+ data +" }"; } } 【構建線索二叉樹（以 中序遍歷 構建 線索二叉樹 為例）：】 首先得構建一個 二叉樹，可以使用 順序二叉樹（詳見上例，陣列 轉 二叉樹） 或者 手動構建， 中序遍歷二叉樹時，無法直接 明確 當前節點的 前驅、后繼 節點， 可以使用變數 preNode 用于記錄 當前節點的前驅節點， 若 當前節點 node 的左指標域 left 為 null，則將其 指向 前驅節點 preNode，并修改指標型別為 線索， 若 前驅節點 preNode 的右指標域 right 為 null，則將其 指向 當前節點 node，并修改指標型別為 線索， 在進入下一個 節點前，需要使用 前驅節點 保存 當前節點， 注： 此處使用變數記錄 前驅節點 即可，當然使用 另一個變數 nextNode 記錄 后繼節點亦可實作， 即： // 設定前驅節點 if (node.left == null) { node.left = preNode; // 指向 當前節點 的前驅節點 node.leftType = 1; // 修改左指標域 指標型別為 線索 } // 設定后繼節點 if (preNode != null && preNode.right == null) { preNode.right = node; preNode.rightType = 1; // 修改右指標域 指標型別為 線索 } // 進入下一個節點前，保存當前節點，作為前驅節點 preNode = node; 【遍歷 線索二叉樹（使用中序遍歷 并根據 后繼節點 的方式輸出 中序線索二叉樹）：】 由于 樹節點 的 左、右指標 并不一定為空（存放了 前驅、后繼 節點），原始的二叉樹 前序、中序、后序遍歷 方式已不適用， 但是一般通過其 前驅節點 或者 后繼節點 查找， 以后繼節點為例： 與 原始遍歷 相同，按照 左子節點、當前節點、右子節點 的順序 訪問， 訪問左子樹，若 當前節點 左子節點為 線索（指向 前驅節點），則輸出 當前節點，若不是，則按照 中序遍歷 方式進行遍歷， 訪問右子樹，若 當前節點 右子節點為 線索（指向 后繼節點），則輸出 后繼節點，若不是，則按照 中序遍歷 方式進行遍歷， 即： // 從 根節點 開始遍歷（中序方式） while(node != null) { // 遍歷左指標域, leftType = 0 時為左子樹，依次往下遍歷，直至 leftType = 1，表示當前節點的左指標域 線索化（即當前節點為有效節點） while(node.leftType == 0) { node = node.left; } // 操作當前節點 System.out.print(node + " "); // 遍歷右指標域，若當前節點的 右指標域 線索化，則輸出當前節點的 后繼節點 while(node.rightType == 1) { node = node.right; System.out.print(node + " "); } // 當前節點 右指標域 非線索化，則替換當前節點，開始下一次回圈 node = node.right; } 前驅節點方式： 與后繼節點相反處理，按照 右子節點、當前節點、左子節點 的順序訪問， 最后回傳的是 樹的 逆序中序遍歷 的順序， 【代碼實作：】 package com.lyh.tree; import java.util.Arrays; /** * 線索二叉樹 * @param <K> */ public class ThreadBinaryTree<K> { private TreeNode3<K> preNode; // 用于記錄當前節點的上一個節點 public static void main(String[] args) { // 將陣列 轉為 順序二叉樹 Integer[] arrays = new Integer[]{1, 2, 3, 4, 5}; ThreadBinaryTree<Integer> threadBinaryTree = new ThreadBinaryTree<>(); TreeNode3<Integer> root = threadBinaryTree.arrayToTree(arrays, 0); // 使用 中序遍歷 遍歷 順序二叉樹，并添加線索，使其成為 中序線索二叉樹 threadBinaryTree.infixCreateThreadBinaryTree(root); // 中序遍歷 以 后繼節點 的方式 輸出 中序線索二叉樹 System.out.println("原陣列為： " + Arrays.toString(arrays)); System.out.println("陣列 ==> 轉為中序線索二叉樹（后繼節點方式） 輸出為： "); threadBinaryTree.infixNextNodeList(root); System.out.println("\n陣列 ==> 轉為中序線索二叉樹（前驅節點方式） 輸出為： "); threadBinaryTree.infixPreNodeList(root); } /** * 根據陣列構建一個 順序二叉樹 * @param arrays 陣列 * @param index 陣列下標 * @return 順序二叉樹 */ public TreeNode3<K> arrayToTree(K[] arrays, int index) { TreeNode3<K> root = null; // 設定根節點 // 遞回陣列并將對應的值存入 順序二叉樹 if (index >= 0 && index < arrays.length) { // 設定當前節點 root = new TreeNode3<>(arrays[index]); // 設定當前節點左子節點 root.left = arrayToTree(arrays, index * 2 + 1); // 設定當前節點右子節點 root.right = arrayToTree(arrays, index * 2 + 2); } return root; } /** * 中序遍歷并創建線索化二叉樹 * @param node 樹節點 */ public void infixCreateThreadBinaryTree(TreeNode3<K> node) { // 判斷當前節點是否為空，即 葉子節點 或者 空樹 if (node == null) { return; } // 遍歷左子節點 infixCreateThreadBinaryTree(node.left); // 操作當前節點 // 設定前驅節點 if (node.left == null) { node.left = preNode; // 指向 當前節點 的前驅節點 node.leftType = 1; // 修改左指標域 指標型別為 線索 } // 設定后繼節點 if (preNode != null && preNode.right == null) { preNode.right = node; preNode.rightType = 1; // 修改右指標域 指標型別為 線索 } // 進入下一個節點前，保存當前節點，作為前驅節點 preNode = node; // 遍歷右子節點 infixCreateThreadBinaryTree(node.right); } /** * 以中序遍歷方式 并根據 后繼節點 輸出 中序線索二叉樹 * @param node 根節點 */ public void infixNextNodeList(TreeNode3<K> node) { // 從 根節點 開始遍歷（中序方式） while(node != null) { // 遍歷左指標域, leftType = 0 時為左子樹，依次往下遍歷，直至 leftType = 1，表示當前節點的左指標域 線索化（即當前節點為有效節點） while(node.leftType == 0) { node = node.left; } // 操作當前節點 System.out.print(node + " "); // 遍歷右指標域，若當前節點的 右指標域 線索化，則輸出當前節點的 后繼節點 while(node.rightType == 1) { node = node.right; System.out.print(node + " "); } // 當前節點 右指標域 非線索化，則替換當前節點，開始下一次回圈 node = node.right; } } /** * 以中序遍歷方式 并根據 前驅節點 反向輸出 中序線索二叉樹 * @param node 根節點 */ public void infixPreNodeList(TreeNode3 node) { // 從根節點開始遍歷 while(node != null) { // 遍歷右指標域，找到線索化 節點 while(node.right != null && node.rightType == 0) { node = node.right; } // 操作當前節點 System.out.print(node + " "); // 遍歷左指標域，若當前左指標域 線索化，則輸出當前節點的 前驅節點 while(node.left != null && node.leftType == 1) { node = node.left; System.out.print(node + " "); } // 當前節點 左指標域 非線索化，則替換當前節點，開始下一次回圈 node = node.left; } } } /** * 定義樹節點 * @param <K> */ class TreeNode3<K> { K data; // 保存節點資料 TreeNode3<K> left; // 保存左子節點 TreeNode3<K> right; // 保存右子節點 byte leftType; // 值為 0 時表示為 左子節點，值為 1 時表示存盤線索 -- 前驅節點 byte rightType; // 值為 0 時表示為 右子節點，值為 1 時表示存盤線索 -- 后繼節點 public TreeNode3(K data) { this.data =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ data; } @Override public String toString() { return "TreeNode3{ data= "https://www.cnblogs.com/l-y-h/archive/2020/09/29/+ data +" }"; } } 【輸出結果：】 原陣列為： [1, 2, 3, 4, 5] 陣列 ==> 轉為中序線索二叉樹（后繼節點方式） 輸出為： TreeNode3{ data= 4 } TreeNode3{ data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/2 } TreeNode3{ data= 5 } TreeNode3{ data= 1 } TreeNode3{ data= 3 } 陣列 ==> 轉為中序線索二叉樹（前驅節點方式） 輸出為： TreeNode3{ data= 3 } TreeNode3{ data= https://www.cnblogs.com/l-y-h/archive/2020/09/29/1 } TreeNode3{ data= 5 } TreeNode3{ data= 2 } TreeNode3{ data= 4 }
7、哈夫曼樹（HuffmanTree、最優二叉樹）
（1）什么是哈夫曼樹？
哈夫曼樹 又稱 最優二叉樹，對于 n 個節點 且 每個節點有一個值（權值），將這 n 個節點構建成一個 二叉樹，使得該樹的 帶權路徑長度（weighted path length，簡稱 wpl）最小，這樣的二叉樹 稱為 最優二叉樹（或者 哈夫曼樹），
注：
哈夫曼樹構建完成后，n 個節點 均為 哈夫曼樹 的葉子節點，
【基本關鍵詞概念：】
路徑 與 路徑長度：
在一棵樹中，一個節點 到達 另一個節點 之間的 分支通路 稱為 路徑，
通路中 分支的總數 稱為 路徑長度，
節點的權：
簡單的理解為 節點中帶有某含義的值，
節點的帶權路徑長度：
從根節點 到 該節點之間的路徑長度 與 該節點的 權的乘積，
樹的帶權路徑長度：
該樹所有的 葉子節點 的帶權路徑長度 之和，
哈夫曼樹（最優二叉樹）：
樹的帶權路徑（wpl）最小的二叉樹 為 哈夫曼樹，
一般權值越大的節點 離 根節點 越近 的二叉樹才是最優二叉樹，
wpl 相同的二叉樹 其 哈夫曼樹可能不同，
（2）創建 哈夫曼樹
【哈夫曼樹創建步驟：】 Step1：對于一組資料，先將資料 按照 權值 從小到大 排序， Step2：將資料中每一個值 視為一個樹節點（最簡單的二叉樹）， Step2.1：從資料中選取 權值 最小的兩個值 作為 左、右子節點 并構建一個新的二叉樹， Step2.2：新的二叉樹 權值為 左、右子節點 權值之和， Step2.3：洗掉已被選擇的左、右節點，并將新的節點 加入 資料中（按照權值從小到大排序）， Step3：重復 Step2 操作，直至資料中只剩 一個值，即 哈夫曼樹的 根節點， 注： 一般來說 權值最大 的葉子節點 離 根節點越近的 二叉樹為 最優二叉樹， 所以每次拼接時，均選取當前節點中 最小權值的兩個節點進行拼接，將最大權值的節點留在最后拼接， 【代碼實作：】 package com.lyh.tree; import java.util.ArrayList; import java.util.Arrays; import java.util.Collections; import java.util.List; /** * 哈夫曼樹 */ public class HuffmanTree<K> { public static void main(String[] args) { // 根據陣列構建哈夫曼樹（此處構建規則為 左子節點權值 小于 右子節點） int[] arrays = new int[]{8, 3, 7, 13}; HuffmanTree<String> huffmanTree = new HuffmanTree<>(); TreeNode4 root = huffmanTree.createHuffmanTree(arrays); // 輸出哈夫曼樹前序遍歷 System.out.print("哈夫曼樹前序遍歷為： "); root.prefixList(); } /** * 構建哈夫曼樹，回傳樹的根節點 * @param arrays 待構建樹的陣列（節點 權值 組成的陣列） * @return 哈夫曼樹根節點 */ public TreeNode4<K> createHuffmanTree(int[] arrays) { // 構建樹節點，此處借用 集合，并利用集合進行排序操作 List<TreeNode4<K>> lists = new ArrayList<>(); Arrays.stream(arrays).forEach( x -> { lists.add(new TreeNode4<>(x)); }); // 遍歷構建哈夫曼樹，此處規則為 左子節點權值 小于 右子節點權值 while (lists.size() > 1) { // 節點按權值 從小到大排序 Collections.sort(lists); // 獲取左子節點 TreeNode4<K> leftNode = lists.get(0); // 獲取右子節點 TreeNode4<K> rightNode = lists.get(1); // 組合成 二叉樹 TreeNode4<K> parentNode = new TreeNode4<>(leftNode.value + rightNode.value); parentNode.left = leftNode; parentNode.right = rightNode; // 從集合中移除已使用節點，并將新節點添加到集合中 lists.remove(leftNode); lists.remove(rightNode); lists.add(parentNode); } // 集合中最后元素即為 哈夫曼樹 根節點 return lists.get(0); } } /** * 定義樹節點 * @param <K> */ class TreeNode4<K> implements Comparable<TreeNode4<K>>{ K data; // 保存節點值 int value; // 保存節點權值 TreeNode4<K> left; // 保存左子節點 TreeNode4<K> right; // 保存右子節點 public TreeNode4(int value) { this.value =https://www.cnblogs.com/l-y-h/archive/2020/09/29/ value; } @Override public String toString() { return "TreeNode4{ value = "https://www.cnblogs.com/l-y-h/archive/2020/09/29/+ value +" }"; } @Override public int compareTo(TreeNode4<K> o) { return this.value - o.value; } /** * 前序遍歷 */ public void prefixList() { // 輸出當前節點 System.out.print(this + " "); // 遍歷左子節點 if (this.left != null) { this.left.prefixList(); } // 遍歷右子節點 if (this.right != null) { this.right.prefixList(); } } } 【輸出結果：】 哈夫曼樹前序遍歷為： TreeNode4{ value = 31 } TreeNode4{ value = https://www.cnblogs.com/l-y-h/archive/2020/09/29/13 } TreeNode4{ value = 18 } TreeNode4{ value = 8 } TreeNode4{ value = 10 } TreeNode4{ value = 3 } TreeNode4{ value = 7 }
8、哈夫曼編碼 實作 檔案壓縮、解壓
（1）什么是 哈夫曼編碼？
哈夫曼編碼 是一種 可變字長編碼，可用于資料壓縮、節省存盤空間，
將檔案轉為 位元組陣列，并根據 各位元組 出現頻率為權值，構建哈夫曼樹，并得到每個位元組的 哈夫曼編碼（出現頻率越高的位元組 其編碼 越短，從而達到縮減存盤空間的目的），再根據 哈夫曼編碼將 位元組轉換為對應的 二進制 串，最后以 8 位為單位 壓縮二進制串 成 位元組陣列，即可實作 檔案的壓縮，
（2）補充點 二進制 與 整數 相互轉換的概念
【Java 中二進制 與 整數 互相轉換：】 String 轉 int： int parseInt(String s, int radix); 其中： s 表示 二進制字串， radix 表示進制， 即 按照 幾進制 去 處理 二進制字串， int 轉 String： String toBinaryString(int i); 其中： i 表示待轉換的整數， 注： 若結果為非負數，輸出結果 前面的 0 會省略（處理時需要額外注意）， 比如： 5 可以為 101、0101、00101,，但是最終輸出結果為 101. int 轉 byte(強轉)： byte (byte)parseInt(String s, int radix) 【Java 中整數以 二進制 補碼形式存盤：】 Java 中整數使用 二進制 補碼 的形式存盤， 正數的 補碼、反碼、原碼 均相同， 負數的 補碼為 反碼 加 1， 反碼為 符號位不變，其余各位取反， 比如： "10000101" 轉為 int 型整數時， 即 Integer.parseInt("10000101", 2); 由于 "1000 0101" 轉為 int，而 int 為 4 位元組，即為 "0000 0000 0000 0000 0000 0000 1000 0101", 其符號位為 0，即整數，補碼與原碼相同，即最終顯示為整數 133. "10000101" 轉為 byte 型整數時，即 (byte)Integer.parseInt("10000101", 2); 由于 "10000101" 轉為 byte，而 byte 為 1 位元組，即為 "10000101"， 其符號位為 1，表示負數，其反碼為符號位不變，各位取反，即 "11111010"， 而 補碼為其反碼 加 1，即最終為 "11111011",即最終顯示為整數 -123. 注： byte 范圍為 -128 ~ 127，即 10000000 ~ 01111111，符號位不做計算， 【壓縮處理最后一個位元組可能遇到的問題：】 以 8 位為單位 將 二進制串 轉為 位元組（整數）陣列 的時候，若 最后一個二進制串 不足 8 位，需要額外注意： 若不足 8 位直接存盤為 位元組，則解碼時 可能會出錯， 比如： (byte)Integer.parseInt("0101", 2); 轉為 byte 時其值為 5. (byte)Integer.parseInt("00101", 2); 轉為 byte 時其值也為 5. 若直接存盤，那么解碼時， Integer.toBinaryString(5); 輸出為 101， 由于轉換的是非負數，其前面的 0 會省略，并不知道其前面到底有 幾個 0，從而解碼失敗， 我的解決方法是： 額外增加一個位元組用于記錄 最后一個 二進制串 的實際位數， 若 最后一個二進制串 轉換為 byte 整數時 為 負數，則其符號位肯定為 1，肯定滿足 8 位，此時記錄 有效位數為 8 位， 若 最后一個二進制串 轉換為 非負數，則其 解碼時 前面的 0 會省略，此時先將其 高位補 0，然后根據最后一個 位元組記錄的 有效位數 去截取即可， 比如： 0101 轉為 byte 整數 5，則額外增加一個位元組整數 4，表示有效位數為 4 位， 00101 轉為 byte 整數 5，則額外增加一個位元組整數 5，表示有效位數為 5 位， 10000101 轉為 byte 整數 -123，則額外增加要給位元組整數 8，表示有效位數為 8 位， 注： 由于 0 會被省略，所以需要對 非負數 進行 高位補位，即 0101 需要變為 00000101， 可以與 256 進行 按位與運算，即 5 | 256 = 0101 | 100000000 = 100000101， 此時截取 后 8 位二進制串即為 補位成功的 二進制串， 此時，對于 0101，其有效位數為 4 位，即截取 后四位 二進制串， 對于 00101，其有效位數為 5 位，即截取 后五為 二進制串，
（3）哈夫曼如何 壓縮、解壓
【壓縮檔案的流程：】 Step1：讀取檔案，根據檔案中 位元組（字符） 出現的頻率 作為權值，構建出 哈夫曼樹， 將 位元組 頻率按 從小到大 排序，并構建 哈夫曼樹， Step2：通過 哈夫曼樹，可以得到每個 位元組 的唯一編碼， 將指向左子節點分支命名為 0，指向右子節點分支命名為 1， 則從根節點 到 某個節點的路徑 記為 該節點的 編碼（比如：00，010，001 等）， Step3：使用編碼 去替換掉 位元組， 將檔案中所有的 位元組 替換成 二進制編碼， Step4：將 8 位二進制 作為一個位元組 進行轉碼，轉成位元組陣列 進行存盤， 最后一個 二進制串 不足 8 位時按 8 位處理，并額外增加一個位元組用于記錄其實際位數， Step5：將 位元組陣列 以及 編碼表 同時 輸出到檔案中（完成壓縮）， 【解壓檔案的流程：】 Step1：讀取檔案中的 位元組陣列 以及 編碼表， Step2：將 位元組陣列 轉為對應 的二進制串， Step3：根據編碼表 得到解碼表，并根據 解碼表 將 二進制串 轉為字符， Step4：輸出到檔案即可，
（3）代碼實作
【代碼實作：】 package com.lyh.tree; import java.io.*; import java.util.*; public class HuffmanCode { private Map<Byte, String> huffmanCodes = new HashMap<>(); // 用于保存 編碼集，位元組為 key，編碼為 value private Map<String, Byte> huffmanDeCodes = new HashMap<>(); // 用于保存 解碼集，位元組為 value，編碼為 key public static void main(String[] args) { // 測驗 普通字串 test(); // 測驗讀取、壓縮檔案 // String srcFile = "G:/1.pdf"; // String zipFile = "G:/zip.pdf"; // String unzipFile = "G:/unzip.pdf"; // testZipFile(srcFile, zipFile); // testUnzipFile(zipFile, unzipFile); } /** * 測驗檔案 壓縮 */ public static void testZipFile(String srcFile, String zipFile) { FileInputStream fis = null; OutputStream os = null; ObjectOutputStream oos = null; try { // 讀取檔案，將檔案轉為 對應的位元組陣列 fis = new FileInputStream(srcFile); byte[] b = new byte[fis.available()]; fis.read(b); // 根據 位元組陣列 生成 哈夫曼樹 以及 哈夫曼編碼，根據 哈夫曼編碼將 原位元組陣列 壓縮 成新的位元組陣列 HuffmanCode huffmanCode = new HuffmanCode(); byte[] zipResult = huffmanCode.zipFile(b); // 輸出檔案，將 位元組陣列 輸出到檔案中,以物件的形式存盤 資料，方便讀取， os = new FileOutputStream(zipFile); oos = new ObjectOutputStream(os); // 記錄壓縮后的位元組陣列 oos.writeObject(zipResult); // 記錄編碼集 oos.writeObject(huffmanCode.huffmanCodes); } catch (Exception e) { System.out.println("檔案操作例外"); } finally { try { fis.close(); oos.close(); os.close(); } catch (IOException e) { System.out.println("檔案關閉失敗"); } } } /** * 測驗檔案 解壓 */ public static void testUnzipFile(String srcFile, String unzipFile) { InputStream is = null; ObjectInputStream ois = null; FileOutputStream fos = null; try { // 讀取檔案，將檔案轉為 對應的 位元組陣列 以及 哈夫曼編碼 is = new FileInputStream(srcFile); ois = new ObjectInputStream(is); // 讀取 位元組陣列 byte[] b = (byte[])ois.readObject(); // 讀取 編碼集 Map<Byte, String> codes = (Map<Byte, String>) ois.readObject(); // 根據 編碼集 將 位元組陣列 解碼，得到解壓后的陣列 HuffmanCode huffmanCode = new HuffmanCode(); huffmanCode.huffmanCodes = codes; byte[] unzipResult = huffmanCode.deCompressAndConvert(b); // 將解壓后的陣列寫入檔案 fos = new FileOutputStream(unzipFile); fos.write(unzipResult); } catch (Exception e) { System.out.println("檔案操作例外"); } finally { try { ois.close(); is.close(); fos.close(); } catch (Exception e) { System.out.println("檔案"); } } } /** * 測驗 壓縮、解壓 普通字串 * Step1：讀取 普通字串 轉為位元組陣列， * Step2：根據位元組陣列 構建 哈夫曼樹， * Step3: 根據 哈夫曼樹 得到 所有葉子節點的 編碼，組成編碼集， */ public static void test() { // 將字符轉為 位元組陣列，并生成對應的 哈夫曼樹 HuffmanCode huffmanCode = new HuffmanCode(); String data = "Java C++"; TreeNode5 root = huffmanCode.createHuffman(data.getBytes()); System.out.println("當前字串為： " + data); System.out.println("轉為位元組陣列為： " + Arrays.toString(data.getBytes())); // 前序遍歷輸出 哈夫曼樹 System.out.println("位元組陣列轉哈夫曼樹后，前序遍歷輸出哈夫曼樹： "); root.prefixList(); System.out.println("\n==============================="); // 根據 哈夫曼樹，生成 位元組對應的 編碼表 huffmanCode.getCodes(root); System.out.println("輸出當前哈夫曼樹 葉子節點 對應的編碼表： "); huffmanCode.hufumanCodesList(); System.out.println("\n==============================="); // 根據編碼集，將 字串對應的位元組陣列 轉為 二進制，并以 8 位為單位 進一步轉為 位元組陣列存盤 System.out.println("壓縮前的位元組陣列為： " + Arrays.toString(data.getBytes())); byte[] result = huffmanCode.convertAndCompress(data.getBytes()); System.out.println("壓縮后的位元組陣列為： " + Arrays.toString(result)); System.out.println("\n==============================="); // 解壓位元組陣列 byte[] newReult = huffmanCode.deCompressAndConvert(result); System.out.println("解壓后的位元組陣列為： " + Arrays.toString(newReult)); System.out.println("解壓后的字串為：" + new String(newReult)); } /** * 壓縮檔案 * @param arrays 待壓縮位元組陣列 * @return 壓縮后的位元組陣列 */ public byte[] zipFile(byte[] arrays) { // 根據位元組陣列 位元組出現頻率 構建 哈夫曼樹，根據 哈夫曼樹 生成對應的 哈夫曼編碼 getCodes(createHuffman(arrays)); // 根據 哈夫曼編碼 將位元組陣列 對應的位元組 轉為 二進制串，二進制串 以 8 位為單位再轉為 位元組陣列存盤 return convertAndCompress(arrays); } /** * 解壓檔案 * @param arrays 待解壓位元組陣列 * @return 解壓后的位元組陣列 */ public byte[] unzipFile(byte[] arrays) { return deCompressAndConvert(arrays); } /** * 構建哈夫曼樹 * @param arrays 位元組陣列 * @return 哈夫曼樹根節點 */ public TreeNode5 createHuffman(byte[] arrays) { // 遍歷位元組陣列，記錄 每個位元組 出現的頻率作為 權值，使用 哈希表，key 存位元組，value 存位元組出現頻率 Map<Byte, Long> map = new HashMap<>(); for (byte temp : arrays) { map.put(temp, map.getOrDefault(temp, 0L) + 1); } // 根據 權值 創建樹節點 List<TreeNode5> lists = new ArrayList<>(); for (Map.Entry<Byte, Long> temp : map.entrySet()) { lists.add(new TreeNode5(temp.getKey(), temp.getValue())); } // Collections.sort(lists); // System.out.println("權值集合為： " + lists); // System.out.println("==============================="); // 遍歷構建 哈夫曼樹 while(lists.size() > 1) { // 排序，從小到大排序（即 哈夫曼樹 左子節點權值 小于 右子節點） Collections.sort(lists); // 獲取左子節點 TreeNode5 leftNode = lists.get(0); // 獲取右子節點 TreeNode5 rightNode = lists.get(1); // 創建二叉樹（此處非葉子節點 值為 null，只含有權值） TreeNode5 parentNode = new TreeNode5(null, leftNode.value + rightNode.value); parentNode.left = leftNode; parentNode.right = rightNode; // 移除已使用節點，添加新節點 lists.remove(leftNode); lists.remove(rightNode); lists.add(parentNode); } // 回傳哈夫曼樹根節點 return lists.get(0); } /** * 獲取 哈夫曼樹 所有 葉子節點 的路徑，即 編碼字串， * 規定：左分支為 0，右分支 為 1. * @param node 哈夫曼樹根節點 */ public void getCodes(TreeNode5 node, String code, StringBuilder stringBuilder) { // 構建一個新的 StringBuilder 用于拼接字串，當某次遞回方法呼叫結束后，此變數作用域會消失，即不會影響之前的 StringBuilder StringBuilder stringBuilder2 = new StringBuilder(stringBuilder); stringBuilder2.append(code); // 判斷當前節點是否為 空 if (node != null) { // 若當前節點值不為 null，即為 葉子節點 if (node.data != null) { // 保存到 編碼集 中 huffmanCodes.put(node.data, stringBuilder2.toString()); } else { // 遞回遍歷左子樹（左子節點），左分支為 0 getCodes(node.left, "0", stringBuilder2); // 遞回遍歷右子樹（右子節點），右分支為 1 getCodes(node.right, "1", stringBuilder2); } } } /** * 多載 獲取 編碼集方法，根據 根節點 遍歷 哈夫曼樹 * @param root 哈夫曼樹根節點 */ public void getCodes(TreeNode5 root) { getCodes(root, "", new StringBuilder()); } /** * 根據 編碼集 得到 解碼集 * @param huffmanCodes 解碼集 */ public void getDeCodes(Map<Byte, String> huffmanCodes) { for (Map.Entry<Byte, String> temp : huffmanCodes.entrySet()) { huffmanDeCodes.put(temp.getValue(), temp.getKey()); } } /** * 輸出 編碼表 */ public void hufumanCodesList() { for(Map.Entry<Byte, String> map : huffmanCodes.entrySet()) { System.out.print("[ Byte = " + map.getKey() + ", String = " + map.getValue() + " ] ==> "); } } /** * 輸出 解碼表 */ public void hufumanDeCodesList() { for(Map.Entry<String, Byte> map : huffmanDeCodes.entrySet()) { System.out.print("[ String = " + map.getKey() + ", Byte = " + map.getValue() + " ] ==> "); } } /** * 將 字串 對應的位元組陣列，根據 編碼表 轉為 對應的 二進制串， * 將 二進制串 以 8 位為 一個單位，進一步轉為 位元組陣列 * @param arrays 待壓縮的位元組陣列（字串轉換的位元組陣列） * @return 壓縮后的位元組陣列 */ public byte[] convertAndCompress(byte[] arrays) { // 根據 編碼表，將 位元組陣列 轉為對應的 二進制串 并 拼接 StringBuilder stringBuilder = new StringBuilder(); for (byte temp : arrays) { stringBuilder.append(huffmanCodes.get(temp)); } // System.out.println("轉換的二進制串為： " + stringBuilder.toString()); // 以 8 位二進制為單位，將 二進制串 轉為位元組陣列，不足 8 位 按 8 位處理，并額外增加一個位元組用于記錄其實際長度， // byte[] result = new byte[stringBuilder.length() % 8 == 0 ? stringBuilder.length() / 8 : stringBuilder.length() / 8 + 1]; byte[] result = new byte[(stringBuilder.length() + 7) / 8 + 1]; for(int i = 0, j = 0; i < result.length && j < stringBuilder.length(); i++, j += 8) { if (j + 8 < stringBuilder.length()) { /** * 整數使用 補碼 的形式存盤， * 正數的 補碼、反碼、原碼 均相同， * 負數的 補碼為 反碼 加 1， * 反碼為 符號位不變，其余各位取反， * 比如： 1110 0110，其符號位為 1，表示負數，則其轉為整數后 為 其反碼 加 1，即 1001 1010，即 -26 */ result[i] = (byte)Integer.parseInt(stringBuilder.substring(j, j + 8), 2); } else { // 額外增加一個位元組用于記錄其實際長度，若 恰好為 8 位，則記錄 8 位，否則 記錄 1 ~ 7 result[i] = (byte)Integer.parseInt(stringBuilder.substring(j), 2); result[i + 1] = (byte)stringBuilder.substring(j).length(); } } return result; } /** * 將壓縮后的位元組陣列 轉為 二進制字串，并根據 編碼表(解碼表) 轉為 位元組陣列 * @param arrays 壓縮后的位元組陣列 * @return 解壓后的位元組陣列 */ public byte[] deCompressAndConvert(byte[] arrays) { // 用于字串拼接 StringBuilder stringBuilder = new StringBuilder(); // 遍歷壓縮后的位元組陣列，轉為對應的 二進制 字串 for (int i = 0; i < arrays.length - 1; i++) { /** * 使用 Integer.toBinaryString() 可以將 int 型 轉為 二進制 字串， * 所以先將 byte 轉為 int，但由于 int 為 4 位元組，byte 為 1 位元組，所以需要截取 int 后 8 位作為 byte 對應的 二進制字串， * Integer.toBinaryString() 對于非負數，其前面的 0 會默認不顯示，可能造成不足 8 位的情況，所以需要對其 進行 補位， * 比如： * Integer.toBinaryString(5) 輸出為 101，但其真實對應的應該為 0000 0101， * 可以使用 5 | 256 的方式，即 101 | 1 0000 0000 進行 按位與運算，結果為 1 0000 0101，再截取 后 8 位即為對應的 二進制字串， * * Integer.toBinaryString() 對于負數，轉換為 int 后，會顯示 32 位，首位為 1，所以無需補位，直接截取低 8 位即可， * * 倒數最后一個位元組，表示 倒數第二個位元組 實際轉換的 二進制串 位數， * 所以 處理倒數第二個位元組時，需要根據 倒數最后一個位元組 進行 字串截取操作，轉載請註明出處，本文鏈接：https://www.uj5u.com/houduan/139689.html
標籤：其他
下一篇：基于Scrapy的互動式漫畫爬蟲