推薦學習：《》

第1章 資料結構與演演算法基礎概述

1.1 資料結構和演演算法的重要性

• 演演算法是程式的靈魂，優秀的程式可以在海量資料計算時，依然保持高速計算

• 資料結構和演演算法的關係：

  • 程式 = 資料結構 + 演演算法
  • 資料結構是演演算法的基礎, 換言之，想要學好演演算法，需要把資料結構學到位。

• 資料結構和演演算法學習大綱
  

1.2 資料結構概述

• 資料結構可以簡單的理解為資料與資料之間所存在的一些關係，資料的結構分為資料的儲存結構和資料的邏輯結構。

邏輯結構

• 集合結構：資料元素同屬於一個集合，他們之間是並列關係，無其他的關係；可以理解為中學時期學習的集合，在一個範圍之內，有很多的元素，元素間沒有什麼關係
• 線性結構：元素之間存在著一對一的關係；可以理解為每個學生對應著一個學號，學號與姓名就是線性結構
• 樹形結構：元素之間存在著一對多的關係，可以簡單理解為家庭族譜一樣，一代接一代
• 圖形結構：元素之間存在多對多的關係，每一個元素可能對應著多個元素，或被多個元素對應，網狀圖

儲存結構

• 順序儲存結構：就是將資料進行連續的儲存，我們可以將它比喻成學校食堂打飯排隊一樣，一個接著一個；
• 鏈式儲存結構：不是按照順序儲存的，後一個進來的數只需要將他的地址告訴前一個節點，前一個節點中就存放了它後面那個數的地址，所以最後一個數的儲存地址就是為null；可以將這種結構比喻成商場吃飯叫號，上面的號碼比喻成是地址，你可以之後後面的地址是什麼，上面的其他內容就是該節點的內容；
• 區別：
  • 順序儲存的特點是查詢快，插入或者刪除慢
  • 鏈式儲存的特點是查詢慢，插入或者刪除快

1.3 演演算法概述

• 同一問題不同解決方法
• 通過時間和空間複雜度判斷演演算法的優劣
• 演演算法沒有最好的，只有最合適的，學習演演算法是為了積累學習思路，掌握學習思路，並不是為了解決某問題去記住某種演演算法；對於時間複雜度與空間複雜度，現在大多數開發情況下，我們都在使用以空間換時間，耗費更多的記憶體，來保證擁有更快的速度。
• 各排序演演算法複雜度及穩定性：
  

如何理解「大O記法」

對於演演算法進行特別具體的細緻分析雖然很好，但在實踐中的實際價值有限。對於演演算法的時間性質和空間性質，最重要的是其數量級和趨勢，這些是分析演演算法效率的主要部分。而計量演演算法基本運算元量的規模函數中那些常數因子可以忽略不計。例如，可以認為 3n^2 和 100n^2 屬於同一個量級，如果兩個演演算法處理同樣規模範例的代價分別為這兩個函數，就認為它們的效率「差不多」，都為n^2級。

時間複雜度

一個演演算法花費的時間與演演算法中語句的執行次數成正比例，哪個演演算法中語句執行次數多,它花費時間就多。演演算法中的語句執行次數稱為語句頻度或時間頻度,記為T(n)。n 稱為問題的規模，當 n 不斷變化時，時間頻度T(n)也會不斷變化。但有時我們想知道它變化時呈現什麼規律。為此，我們引入時間複雜度概念。

一般情況下，演演算法中基本操作重複執行的次數是問題規模 n 的某個函數,用T(n)表示，若有某個輔助函數f(n)，使得當 n 趨近於無究大時，T(n)/f(n)的極限值為不等於零的常數，則稱f(n)是T(n)的同數量級函數。記作T(n)=O(f(n))，稱O(f(n))為演演算法的漸進時間複雜度，簡稱時間複雜度。

有時候，演演算法中基本操作重複執行的次數還隨問題的輸入資料集不同而不同,如在氣泡排序中，輸入資料有序而無序，結果是不一樣的。此時，我們計算平均值。

時間複雜度基本計算規則：

• 基本操作，即只有常數項，認為其時間複雜度為O(1)
• 順序結構，時間複雜度按加法進行計算
• 迴圈結構，時間複雜度按乘法進行計算
• 分支結構，時間複雜度取最大值
• 判斷一個演演算法的效率時，往往只需要關注運算元量的最高次項，其它次要項和常數項可以忽略
• 在沒有特殊說明時，我們所分析的演演算法的時間複雜度都是指最壞時間複雜度

常用時間複雜度：

• 注意：經常將log2n（以2為底的對數）簡寫成logn

常見時間複雜度之間的關係：

• 所以時間消耗由小到大為：O(1) < O(log n) < O(n) < O(nlog n) < O(n^2) < O(2^n) < O(n!) < O(n^n)

案例1：

count = 0;				      (1)
	for(i = 0;i <= n;i++)	  (2)
		for(j = 0;j <= n;j++) (3)
			count++;          (4)

• 語句（1）執行1次
• 語句（2）執行n次
• 語句（3）執行n^2次
• 語句（4）執行n^2次
• 時間複雜度為：T(n) = 1+n+n^2+n^2 = O(n^2)

案例2：

a = 1; 						(1)
b = 2;						(2)
for(int i = 1;i <= n;i++) { (3)
	int s = a + b;			(4)
	b = a;					(5)
	a = s;					(6)
}	

• 語句（1）、（2）執行1次
• 語句（3）執行n次
• 語句（4）、（5）、（6）執行n次
• 時間複雜度為：T(n) = 1+1+4n = o(n)

案例3：

i = 1;		 (1)while(i<n) {
	i = i*2; (2)}

• 語句（1）的頻度是1
• 設語句（2）的頻度是f(n)，則2f(n)<=n;f(n)<=log2n,取最大值f(n) = log2n
• 時間複雜度為：T(n) = O(log2n)

空間複雜度

• 演演算法的空間複雜度計算公式：S(n) = 0( f(n) )，其中 n 為輸入規模，f(n)為語句關於 n 所佔儲存空間的函數

• 一個演演算法在計算機記憶體上所佔用的儲存空間，包括三個方面

  • 儲存演演算法本身所佔用的儲存空間
  • 演演算法的輸入輸出資料所佔用的儲存空間
  • 演演算法在執行過程中臨時佔用的儲存空間

案例：指定的陣列進行反轉，並返回反轉的內容

解法一：

public static int[] reverse1(int[] arr) {
    int n = arr.length; //申請4個位元組
    int temp; //申請4個位元組
    for (int start = 0, end = n - 1; start <= end; start++, end--) {
        temp = arr[start];
        arr[start] = arr[end];
        arr[end] = temp;
    }
    return arr;}

• 空間複雜度為：S(n) = 4+4 = O(8) = O(1)

解法二：

public static int[] reverse2(int[] arr) {
    int n = arr.length; //申請4個位元組
    int[] temp = new int[n]; //申請n*4個位元組+陣列自身頭資訊開銷24個位元組
    for (int i = n - 1; i >= 0; i--) {
        temp[n - 1 - i] = arr[i];
    }
    return temp;}

• 空間複雜度為：S(n) = 4+4n+24 = O(n+28) = O(n)

根據大O推導法則，演演算法一的空間複雜度為0(1),演演算法二的空間複雜度為0(n)，所以從空間佔用的角度講，演演算法一要優於演演算法二。

由於java中有記憶體垃圾回收機制，並且jvm對程式的記憶體佔用也有優化(例如即時編譯) , 我們無法精確的評估一個java程式的記憶體佔用情況，但是瞭解了java的基本記憶體佔用，使我們可以對java程式的記憶體佔用情況進行估算。

由於現在的計算機裝置記憶體一般都比較大，基本上個人計算機都是4G起步，大的可以達到32G ，所以記憶體佔用一般情況下並不是我們演演算法的瓶頸，普通情況下直接說複雜度，預設為演演算法的時間複雜度。

但是，如果你做的程式是嵌入式開發，尤其是一些感測器裝置上的內建程式,由於這些裝置的記憶體很小, 一般為幾kb，這個時候對演演算法的空間複雜度就有要求了，但是一般做java開發的，基本上都是伺服器開發, 一般不存在這樣的問題。

第2章 陣列

2.1 陣列概念

陣列是一種線性表資料結構，它用一組連續的記憶體空間，來儲存一組具有相同型別的資料。這裡我們要抽取出三個跟陣列相關的關鍵詞：線性表，連續記憶體空間，相同資料型別；陣列具有連續的記憶體空間，儲存相同型別的資料，正是該特性使得陣列具有一個特性：隨機存取。但是有利有弊，這個特性雖然使得存取陣列邊得非常容易，但是也使得陣列插入和刪除操作會變得很低效，插入和刪除資料後為了保證連續性,要做很多資料搬遷工作。

查詢陣列中的方法有兩種：

• 線性查詢：線性查詢就是簡單的查詢陣列中的元素
• 二分法查詢：二分法查詢要求目標陣列必須是有序的。

2.2 無序陣列

• 實現類：

public class MyArray {
	//宣告一個陣列
	private long[] arr;
	
	//有效資料的長度
	private int elements;
	
	//無參建構函式，預設長度為50
	public MyArray(){
		arr = new long[50];
	}
	
	public MyArray(int maxsize){
		arr = new long[maxsize];
	}
	
	
	//新增資料
	public void insert(long value){
		arr[elements] = value;
		elements++;
	}
	
	//顯示資料
	public void display(){
		System.out.print("[");
		for(int i = 0;i < elements;i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println("]");
	}
	
	//根據下標查詢資料
	public long get(int index){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			return arr[index];
		}
	}
	
	/**
	 * 根據值查詢
	 * @param value 需要被查詢的值
	 * @return 被查詢值的下標
	 */
	public int search(int value){
		//宣告一個變數i用來記錄該資料的下標值
		int i ;
		for(i = 0;i < elements;i++){
			if(value == arr[i]){
				break;
			}
		}
		//如果查詢到最後一個元素依然沒有找到
		if(i == elements){
			return -1;
		}else{
			return i;
		}
	}
	
	//根據下標刪除資料
	public void delete(int index){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			//刪除該元素後，後面所有元素前移一位
			for(int i = index; i < elements;i++){
				arr[i] = arr[i+1];
			}
			elements--;
		}
		
	}
	/**
	 * 替換資料
	 * @param index 被替換的下標
	 * @param newvalue 新的資料
	 */
	public void change(int index,int newvalue){
		if(index >= elements || index < 0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			arr[index] = newvalue;
		}
	} }

• 優點：插入快（時間複雜度為：O(1)）、如果知道下標，可以很快儲存
• 缺點：查詢慢（時間複雜度為：O(n)）、刪除慢

2.3 有序陣列

• 實現類：

public class MyOrderArray { 
	private long[] arr;
	
	private int elements;
	
	public MyOrderArray(){
		arr = new long[50];
	}
	
	public MyOrderArray(int maxsize){
		arr = new long[maxsize];
	}
	
	//新增資料
	public void insert(int value){
		int i;
		for(i = 0;i < elements;i++){
			if(arr[i] > value){
				break;
			}
		}
		for(int j = elements;j > i;j--){
			arr[j] = arr[j -1];
		}
		arr[i] = value;
		elements++;
	}
	
	
	//刪除資料
	public void delete(int index){
		if(index >=elements || index <0){
			throw new ArrayIndexOutOfBoundsException();
		}else{
			for(int i = index;i < elements; i++){
				arr[i] = arr[i+1];
			}
			elements--;
		}
	}
	
	//修改資料
	public void change(int index,int value){
		if(index >= elements || index < 0){
			throw new IndexOutOfBoundsException();
		}else{
			arr[index] = value;
		}
	}
	
	//根據下標查詢資料
	public long get(int index){
		if(index >= elements || index < 0){
			throw new IndexOutOfBoundsException();
		}else{
			return arr[index];
		}
	}
	
	//展示資料
	public void display(){
		System.out.print("[");
		for(int i = 0; i < elements;i++){
			System.out.print(arr[i] + " ");
		}
		System.out.println("]");
	}
	
	
	//二分法查詢資料
	public int binarySearch(long value){
			//宣告三個指標分別指向陣列的頭，尾，中間
			int low = 0;
			int pow = elements;
			int middle = 0;
			
			while(true){
				middle = (low + pow) / 2;
				//如果中指標所指的值等於帶查詢數
				if(arr[middle] == value){
					return middle;
				}else if(low > pow){
					return -1;
				}else{
					if(arr[middle] > value){
						//待查詢的數在左邊,右指標重新改變指向
						pow = middle-1;
					}else{
						//帶查詢的數在右邊，左指標重新改變指向
						low = middle +1;
					}
				}
			}
	}}

• 優點：查詢快（時間複雜度為：O(logn)）
• 缺點：增刪慢（時間複雜度為：O(n)）

第三章 棧

3.1 棧概念

棧（stack），有些地方稱為堆疊，是一種容器，可存入資料元素、存取元素、刪除元素，它的特點在於只能允許在容器的一端（稱為棧頂端指標，英語：top）進行加入資料（英語：push）和輸出資料（英語：pop）的運算。沒有了位置概念，保證任何時候可以存取、刪除的元素都是此前最後存入的那個元素，確定了一種預設的存取順序。

由於棧資料結構只允許在一端進行操作，因而按照後進先出的原理運作。

棧可以用順序表實現，也可以用連結串列實現。

3.2 棧的操作

• Stack() 建立一個新的空棧
• push(element) 新增一個新的元素element到棧頂
• pop() 取出棧頂元素
• peek() 返回棧頂元素
• is_empty() 判斷棧是否為空
• size() 返回棧的元素個數

實現類：

package mystack;public class MyStack {

    //棧的底層使用陣列來儲存資料
    //private int[] elements;
    int[] elements; //測試時使用

    public MyStack() {
        elements = new int[0];
    }

    //新增元素
    public void push(int element) {
        //建立一個新的陣列
        int[] newArr = new int[elements.length + 1];
        //把原陣列中的元素複製到新陣列中
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        //把新增的元素放入新陣列中
        newArr[elements.length] = element;
        //使用新陣列替換舊陣列
        elements = newArr;
    }

    //取出棧頂元素
    public int pop() {
        //當棧中沒有元素
        if (is_empty()) {
            throw new RuntimeException("棧空");
        }
        //取出陣列的最後一個元素
        int element = elements[elements.length - 1];
        //建立一個新陣列
        int[] newArr = new int[elements.length - 1];
        //原陣列中除了最後一個元素其他元素放入新陣列
        for (int i = 0; i < elements.length - 1; i++) {
            newArr[i] = elements[i];
        }
        elements = newArr;
        return element;
    }

    //檢視棧頂元素
    public int peek() {
        return elements[elements.length - 1];
    }

    //判斷棧是否為空
    public boolean is_empty() {
        return elements.length == 0;
    }

    //檢視棧的元素個數
    public int size() {
        return elements.length;
    }}

測試類：

package mystack;public class Demo {
    public static void main(String[] args) {
        MyStack ms = new MyStack();
        //新增元素
        ms.push(9);
        ms.push(8);
        ms.push(7);

        //取出棧頂元素//        System.out.println(ms.pop()); //7//        System.out.println(ms.pop()); //8//        System.out.println(ms.pop()); //9

        //檢視棧頂元素
        System.out.println(ms.peek()); //7
        System.out.println(ms.peek()); //7

        //檢視棧中元素個數
        System.out.println(ms.size()); //3
    }}

第4章 佇列

4.1 佇列概念

佇列（Queue）是隻允許在一端進行插入操作，而在另一端進行刪除操作的線性表。

佇列是一種先進先出的（First In First Out）的線性表，簡稱FIFO。允許插入的一端為隊尾，允許刪除的一端為隊頭。佇列不允許在中間部位進行操作！假設佇列是q=（a1，a2，……，an），那麼a1就是隊頭元素，而an是隊尾元素。這樣我們就可以刪除時，總是從a1開始，而插入時，總是在佇列最後。這也比較符合我們通常生活中的習慣，排在第一個的優先出列，最後來的當然排在隊伍最後。

同棧一樣，佇列也可以用順序表或者連結串列實現。

4.2 佇列的操作

• Queue() 建立一個空的佇列
• enqueue(element) 往佇列中新增一個element元素
• dequeue() 從佇列頭部刪除一個元素
• is_empty() 判斷一個佇列是否為空
• size() 返回佇列的大小

實現類：

public class MyQueue {

    int[] elements;

    public MyQueue() {
        elements = new int[0];
    }

    //入隊
    public void enqueue(int element) {
        //建立一個新的陣列
        int[] newArr = new int[elements.length + 1];
        //把原陣列中的元素複製到新陣列中
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        //把新增的元素放入新陣列中
        newArr[elements.length] = element;
        //使用新陣列替換舊陣列
        elements = newArr;
    }

    //出隊
    public int dequeue() {
        if (isEmpty()) {
            throw new RuntimeException("隊空，無資料");
        }
        //把陣列中第1個元素取出來
        int element = elements[0];
        //建立一個新陣列
        int[] newArr = new int[elements.length - 1];
        //把原陣列除了第一個資料，其他存入新陣列
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i + 1];
        }
        //新陣列替換舊陣列
        elements = newArr;

        return element;
    }

    //判斷是否隊空
    public boolean isEmpty() {
        return elements.length==0;
    }

    //獲取佇列長度
    public int size() {
        return elements.length;
    }}

測試類：

public class Demo {
    public static void main(String[] args) {
        MyQueue mq = new MyQueue();

        //入隊
        mq.enqueue(1);
        mq.enqueue(2);
        mq.enqueue(3);

        //出隊
        System.out.println(mq.dequeue()); //1
        System.out.println(mq.dequeue()); //2
        System.out.println(mq.dequeue()); //3
    }}

第5章 連結串列

5.1 單連結串列

單連結串列概念

單連結串列也叫單向連結串列，是連結串列中最簡單的一種形式，它的每個節點包含兩個域，一個資訊域（元素域）和一個連結域。這個連結指向連結串列中的下一個節點，而最後一個節點的連結域則指向一個空值。

• 表元素域data用來存放具體的資料。
• 連結域next用來存放下一個節點的位置

單連結串列操作

• is_empty() 連結串列是否為空
• length() 連結串列長度
• travel() 遍歷整個連結串列
• add(item) 連結串列頭部新增元素
• append(item) 連結串列尾部新增元素
• insert(pos, item) 指定位置新增元素
• remove(item) 刪除節點
• search(item) 查詢節點是否存在

實現類：

//一個節點public class Node {

    //節點內容
    int data;
    //下一個節點
    Node next;

    public Node(int data) {
        this.data = data;
    }

    //為節點追加節點
    public Node append(Node node) {
        //當前節點
        Node currentNode = this;
        //迴圈向後找
        while (true) {
            //取出下一個節點
            Node nextNode = currentNode.next();
            //如果下一個節點為null，當前節點已經是最後一個節點
            if (nextNode == null) {
                break;
            }
            //賦給當前節點，無線向後找
            currentNode = nextNode;
        }
        //把需要追加的節點，追加為找到的當前節點（最後一個節點）的下一個節點
        currentNode.next = node;
        return this;
    }

    //顯示所有節點資訊
    public void show() {
        Node currentNode = this;
        while (true) {
            System.out.print(currentNode.data + " ");
            //取出下一個節點
            currentNode = currentNode.next;
            //如果是最後一個節點
            if (currentNode == null) {
                break;
            }
        }
        System.out.println();
    }

    //插入一個節點作為當前節點的下一個節點
    public void after(Node node) {
        //取出下一個節點，作為下下一個節點
        Node nextNext = next;
        //把新節點作為當前節點的下一個節點
        this.next = node;
        //把下下一個節點設定為新節點的下一個節點
        node.next = nextNext;

    }

    //刪除下一個節點
    public void removeNode() {
        //取出下下一個節點
        Node newNext = next.next;
        //把下下一個節點設定為當前節點的下一個節點
        this.next = newNext;
    }

    //獲取下一個節點
    public Node next() {
        return this.next;
    }

    //獲取節點中的資料
    public int getData() {
        return this.data;
    }

    //判斷節點是否為最後一個節點
    public boolean isLast() {
        return next == null;
    }}

測試類：

public class Demo {
    public static void main(String[] args) {
        //建立節點
        Node n1 = new Node(1);
        Node n2 = new Node(2);
        Node n3 = new Node(3);
        //追加節點
        n1.append(n2).append(n3);
        //取出下一個節點資料
        System.out.println(n1.next().next().getData()); //3
        //判斷節點是否為最後一個節點
        System.out.println(n1.isLast()); //false
        System.out.println(n1.next().next().isLast()); //true
        //顯示所有節點資訊
        n1.show(); //1 2 3
        //刪除一個節點//        n1.next.removeNode();//        n1.show(); //1 2
        //插入一個新節點
        n1.next.after(new Node(0));
        n1.show(); //1 2 0 3
    }}

5.2 迴圈連結串列

迴圈連結串列概念

單連結串列的一個變形是單向迴圈連結串列，連結串列中最後一個節點的 next 域不再為 None，而是指向連結串列的頭節點。

迴圈連結串列操作

實現類：

//表示一個節點public class LoopNode {

    //節點內容
    int data;
    //下一個節點
    LoopNode next = this; //與單連結串列的區別，追加了一個this，當只有一個節點時指向自己

    public LoopNode(int data) {
        this.data = data;
    }

    //插入一個節點
    public void after(LoopNode node) {
        LoopNode afterNode = this.next;
        this.next = node;
        node.next = afterNode;
    }

    //刪除一個節點
    public void removeNext() {
        LoopNode newNode = this.next.next;
        this.next = newNode;
    }

    //獲取下一個節點
    public LoopNode next() {
        return this.next;
    }

    //獲取節點中的資料
    public int getData() {
        return this.data;
    }}

測試類：

public class Demo {
    public static void main(String[] args) {
        //建立節點
        LoopNode n1 = new LoopNode(1);
        LoopNode n2 = new LoopNode(2);
        LoopNode n3 = new LoopNode(3);
        LoopNode n4 = new LoopNode(4);

        //增加節點
        n1.after(n2);
        n2.after(n3);
        n3.after(n4);
        System.out.println(n1.next().getData()); //2
        System.out.println(n2.next().getData()); //3
        System.out.println(n3.next().getData()); //4
        System.out.println(n4.next().getData()); //1
    }}

5.3 雙向迴圈連結串列

雙向迴圈連結串列概念

在雙向連結串列中有兩個指標域，一個是指向前驅結點的prev，一個是指向後繼結點的next指標

雙向迴圈連結串列操作

實現類：

public class DoubleNode {
    //上一個節點
    DoubleNode pre = this;
    //下一個節點
    DoubleNode next = this;
    //節點資料
    int data;

    public DoubleNode(int data) {
        this.data = data;
    }

    //增加節點
    public void after(DoubleNode node) {
        //原來的下一個節點
        DoubleNode nextNext = next;
        //新節點作為當前節點的下一個節點
        this.next = node;
        //當前節點作為新節點的前一個節點
        node.pre = this;
        //原來的下一個節點作為新節點的下一個節點
        node.next = nextNext;
        //原來的下一個節點的上一個節點為新節點
        nextNext.pre = node;
    }

    //獲取下一個節點
    public DoubleNode getNext() {
        return this.next;
    }

    //獲取上一個節點
    public DoubleNode getPre() {
        return this.pre;
    }

    //獲取資料
    public int getData() {
        return this.data;
    }}

測試類：

public class Demo {
    public static void main(String[] args) {
        //建立節點
        DoubleNode n1 = new DoubleNode(1);
        DoubleNode n2 = new DoubleNode(2);
        DoubleNode n3 = new DoubleNode(3);

        //追加節點
        n1.after(n2);
        n2.after(n3);

        //檢視上一個，自己，下一個節點內容
        System.out.println(n2.getPre().getData()); //1
        System.out.println(n2.getData()); //2
        System.out.println(n2.getNext().getData()); //3

        System.out.println(n1.getPre().getData()); //3
        System.out.println(n3.getNext().getData()); //1
    }}

第6章 樹結構基礎

6.1 為什麼要使用樹結構

線性結構中不論是陣列還是連結串列，他們都存在著詬病；比如查詢某個數必須從頭開始查，消耗較多的時間。使用樹結構，在插入和查詢的效能上相對都會比線性結構要好

6.2 樹結構基本概念

示意圖

1、根節點：最頂上的唯一的一個；如：A

2、雙親節點：子節點的父節點就叫做雙親節點；如A是B、C、D的雙親節點，B是E、F的雙親節點

3、子節點：雙親節點所產生的節點就是子節點

4、路徑：從根節點到目標節點所走的路程叫做路徑；如A要存取F，路徑為A-B-F

5、節點的度：有多少個子節點就有多少的度（最下面的度一定為0，所以是葉子節點）

6、節點的權：在節點中所存的數位

7、葉子節點：沒有子節點的節點，就是沒有下一代的節點；如：E、F、C、G

8、子樹：在整棵樹中將一部分看成也是一棵樹，即使只有一個節點也是一棵樹，不過這個樹是在整個大樹職中的，包含的關係

9、層：就是族譜中有多少代的人；如：A是1，B、C、D是2，E、F、G是3

10、樹的高度：樹的最大的層數：就是層數中的最大值

11、森林：多個樹組成的集合

6.3 樹的種類

無序樹：樹中任意節點的子節點之間沒有順序關係，這種樹稱為無序樹，也稱為自由樹；

有序樹：樹中任意節點的子節點之間有順序關係，這種樹稱為有序樹；

• 二元樹：每個節點最多含有兩個子樹的樹稱為二元樹；
  • 完全二元樹：對於一顆二元樹，假設其深度為d(d>1)。除了第d層外，其它各層的節點數目均已達最大值，且第d層所有節點從左向右連續地緊密排列，這樣的二元樹被稱為完全二元樹，其中滿二元樹的定義是所有葉節點都在最底層的完全二元樹;
  • 平衡二元樹（AVL樹）：當且僅當任何節點的兩棵子樹的高度差不大於1的二元樹；
  • 排序二元樹（二叉查詢樹（英語：Binary Search Tree），也稱二元搜尋樹、有序二元樹）；
• 霍夫曼樹（用於資訊編碼）：帶權路徑最短的二元樹稱為哈夫曼樹或最優二元樹；
• B樹：一種對讀寫操作進行優化的自平衡的二叉查詢樹，能夠保持資料有序，擁有多餘兩個子樹。

6.4 樹的儲存與表示

順序儲存：將資料結構儲存在固定的陣列中，然在遍歷速度上有一定的優勢，但因所佔空間比較大，是非主流二元樹。二元樹通常以鏈式儲存。

鏈式儲存：

由於對節點的個數無法掌握，常見樹的儲存表示都轉換成二元樹進行處理，子節點個數最多為2

6.5 常見的一些樹的應用場景

1、xml，html等，那麼編寫這些東西的解析器的時候，不可避免用到樹

2、路由協定就是使用了樹的演演算法

3、mysql資料庫索引

4、檔案系統的目錄結構

5、所以很多經典的AI演演算法其實都是樹搜尋，此外機器學習中的decision tree也是樹結構

第7章 二元樹大全

7.1 二元樹的定義

任何一個節點的子節點數量不超過 2，那就是二元樹；二元樹的子節點分為左節點和右節點，不能顛倒位置

7.2 二元樹的性質(特性)

性質1：在二元樹的第i層上至多有2^(i-1)個結點（i>0）

性質2：深度為k的二元樹至多有2^k - 1個結點（k>0）

性質3：對於任意一棵二元樹，如果其葉結點數為N0，而度數為2的結點總數為N2，則N0=N2+1;

性質4：具有n個結點的完全二元樹的深度必為 log2(n+1)

性質5：對完全二元樹，若從上至下、從左至右編號，則編號為i 的結點，其左孩子編號必為2i，其右孩子編號必為2i＋1；其雙親的編號必為i/2（i＝1 時為根,除外）

7.3 滿二元樹與完全二元樹

滿二元樹： 所有葉子結點都集中在二元樹的最下面一層上，而且結點總數為：2^n-1 (n為層數 / 高度）

完全二元樹： 所有的葉子節點都在最後一層或者倒數第二層，且最後一層葉子節點在左邊連續，倒數第二層在右邊連續（滿二元樹也是屬於完全二元樹）（從上往下，從左往右能挨著數滿）

7.4 鏈式儲存的二元樹

建立二元樹：首先需要一個樹的類，還需要另一個類用來存放節點，設定節點；將節點放入樹中，就形成了二元樹；（節點中需要權值，左子樹，右子樹，並且都能對他們的值進行設定）。

樹的遍歷：

• 先序遍歷：根節點，左節點，右節點（如果節點有子樹，先從左往右遍歷子樹，再遍歷兄弟節點）
  先序遍歷結果為：A B D H I E J C F K G

• 中序遍歷：左節點，根節點，右節點（中序遍歷可以看成，二元樹每個節點，垂直方向投影下來（可以理解為每個節點從最左邊開始垂直掉到地上），然後從左往右數）
  中遍歷結果為：H D I B E J A F K C G

• 後序遍歷：左節點，右節點，根節點
  後序遍歷結果：H I D J E B K F G C A

• 層次遍歷：從上往下，從左往右
  層次遍歷結果：A B C D E F G H I J K
  

查詢節點：先對樹進行一次遍歷，然後找出要找的那個數；因為有三種排序方法，所以查詢節點也分為先序查詢，中序查詢，後序查詢；

刪除節點：由於鏈式儲存，不能找到要刪的數直接刪除，需要找到他的父節點，然後將指向該數設定為null；所以需要一個變數來指向父節點，找到數後，再斷開連線。

程式碼實現：

• 樹類

public class BinaryTree {

    TreeNode root;

    //設定根節點
    public void setRoot(TreeNode root) {
        this.root = root;
    }

    //獲取根節點
    public TreeNode getRoot() {
        return root;
    }

    //先序遍歷
    public void frontShow() {
        if (root != null) {
            root.frontShow();
        }
    }

    //中序遍歷
    public void middleShow() {
        if (root != null) {
            root.middleShow();
        }
    }

    //後序遍歷
    public void afterShow() {
        if (root != null) {
            root.afterShow();
        }
    }

    //先序查詢
    public TreeNode frontSearch(int i) {
        return root.frontSearch(i);
    }

    //刪除一個子樹
    public void delete(int i) {
        if (root.value == i) {
            root = null;
        } else {
            root.delete(i);
        }
    }}

• 節點類

public class TreeNode {
    //節點的權
    int value;
    //左兒子
    TreeNode leftNode;
    //右兒子
    TreeNode rightNode;

    public TreeNode(int value) {
        this.value = value;
    }

    //設定左兒子
    public void setLeftNode(TreeNode leftNode) {
        this.leftNode = leftNode;
    }

    //設定右兒子
    public void setRightNode(TreeNode rightNode) {
        this.rightNode = rightNode;
    }

    //先序遍歷
    public void frontShow() {
        //先遍歷當前節點的值
        System.out.print(value + " ");
        //左節點
        if (leftNode != null) {
            leftNode.frontShow(); //遞迴思想
        }
        //右節點
        if (rightNode != null) {
            rightNode.frontShow();
        }
    }

    //中序遍歷
    public void middleShow() {
        //左節點
        if (leftNode != null) {
            leftNode.middleShow(); //遞迴思想
        }
        //先遍歷當前節點的值
        System.out.print(value + " ");
        //右節點
        if (rightNode != null) {
            rightNode.middleShow();
        }
    }

    //後續遍歷
    public void afterShow() {
        //左節點
        if (leftNode != null) {
            leftNode.afterShow(); //遞迴思想
        }
        //右節點
        if (rightNode != null) {
            rightNode.afterShow();
        }
        //先遍歷當前節點的值
        System.out.print(value + " ");
    }

    //先序查詢
    public TreeNode frontSearch(int i) {
        TreeNode target = null;
        //對比當前節點的值
        if (this.value == i) {
            return this;
            //當前節點不是要查詢的節點
        } else {
            //查詢左兒子
            if (leftNode != null) {
                //查詢的話t賦值給target，查不到target還是null
                target = leftNode.frontSearch(i);
            }
            //如果target不為空，說明在左兒子中已經找到
            if (target != null) {
                return target;
            }
            //如果左兒子沒有查到，再查詢右兒子
            if (rightNode != null) {
                target = rightNode.frontSearch(i);
            }
        }
        return target;
    }

    //刪除一個子樹
    public void delete(int i) {
        TreeNode parent = this;
        //判斷左兒子
        if (parent.leftNode != null && parent.leftNode.value == i) {
            parent.leftNode = null;
            return;
        }
        //判斷右兒子
        if (parent.rightNode != null && parent.rightNode.value == i) {
            parent.rightNode = null;
            return;
        }
        //如果都不是，遞迴檢查並刪除左兒子
        parent = leftNode;
        if (parent != null) {
            parent.delete(i);
        }
        //遞迴檢查並刪除右兒子
        parent = rightNode;
        if (parent != null) {
            parent.delete(i);
        }

    }}

• 測試類

public class Demo {
    public static void main(String[] args) {
        //建立一棵樹
        BinaryTree binaryTree = new BinaryTree();
        //建立一個根節點
        TreeNode root = new TreeNode(1);
        //把根節點賦給樹
        binaryTree.setRoot(root);
        //建立左,右節點
        TreeNode rootLeft = new TreeNode(2);
        TreeNode rootRight = new TreeNode(3);
        //把新建的節點設定為根節點的子節點
        root.setLeftNode(rootLeft);
        root.setRightNode(rootRight);
        //為第二層的左節點建立兩個子節點
        rootLeft.setLeftNode(new TreeNode(4));
        rootLeft.setRightNode(new TreeNode(5));
        //為第二層的右節點建立兩個子節點
        rootRight.setLeftNode(new TreeNode(6));
        rootRight.setRightNode(new TreeNode(7));

        //先序遍歷
        binaryTree.frontShow(); //1 2 4 5 3 6 7
        System.out.println();
        //中序遍歷
        binaryTree.middleShow(); //4 2 5 1 6 3 7
        System.out.println();
        //後序遍歷
        binaryTree.afterShow(); //4 5 2 6 7 3 1
        System.out.println();

        //先序查詢
        TreeNode result = binaryTree.frontSearch(5);
        System.out.println(result); //binarytree.TreeNode@1b6d3586

        //刪除一個子樹
        binaryTree.delete(2);
        binaryTree.frontShow(); //1 3 6 7 ，2和他的子節點被刪除了
    }}

7.5 順序儲存的二元樹

概述：順序儲存使用陣列的形式實現；由於非完全二元樹會導致陣列中出現空缺，有的位置不能填上數位，所以順序儲存二元樹通常情況下只考慮完全二元樹

原理： 順序儲存在陣列中是按照第一層第二層一次往下儲存的，遍歷方式也有先序遍歷、中序遍歷、後續遍歷

性質：

• 第n個元素的左子節點是：2*n+1；
• 第n個元素的右子節點是：2*n+2；
• 第n個元素的父節點是：（n-1)/2

程式碼實現：

• 樹類

public class ArrayBinaryTree {

    int[] data;

    public ArrayBinaryTree(int[] data) {
        this.data = data;
    }

    //過載先序遍歷方法，不用每次傳引數了,保證每次從頭開始
    public void frontShow() {
        frontShow(0);
    }

    //先序遍歷
    public void frontShow(int index) {
        if (data == null || data.length == 0) {
            return;
        }
        //先遍歷當前節點的內容
        System.out.print(data[index] + " ");
        //處理左子樹：2*index+1
        if (2 * index + 1 < data.length) {
            frontShow(2 * index + 1);
        }
        //處理右子樹：2*index+2
        if (2 * index + 2 < data.length) {
            frontShow(2 * index + 2);
        }
    }}

• 測試類

public class Demo {
    public static void main(String[] args) {
        int[] data = {1,2,3,4,5,6,7};
        ArrayBinaryTree tree = new ArrayBinaryTree(data);
        //先序遍歷
        tree.frontShow(); //1 2 4 5 3 6 7
    }}

7.6 線索二元樹(Threaded BinaryTree)

為什麼使用線索二元樹？

當用二元連結串列作為二元樹的儲存結構時，可以很方便的找到某個結點的左右孩子；但一般情況下，無法直接找到該結點在某種遍歷序列中的前驅和後繼結點

原理：n個結點的二元連結串列中含有n+1(2n-(n-1)=n+1個空指標域。利用二元連結串列中的空指標域，存放指向結點在某種遍歷次序下的前驅和後繼結點的指標。

例如：某個結點的左孩子為空，則將空的左孩子指標域改為指向其前驅；如果某個結點的右孩子為空，則將空的右孩子指標域改為指向其後繼（這種附加的指標稱為"線索"）

程式碼實現：

• 樹類

public class ThreadedBinaryTree {

    ThreadedNode root;
    //用於臨時儲存前驅節點
    ThreadedNode pre = null;
    
    //設定根節點
    public void setRoot(ThreadedNode root) {
        this.root = root;
    }

    //中序線索化二元樹
    public void threadNodes() {
        threadNodes(root);
    }

    public void threadNodes(ThreadedNode node) {
        //當前節點如果為null，直接返回
        if (node == null) {
            return;
        }
        //處理左子樹
        threadNodes(node.leftNode);

        //處理前驅節點
        if (node.leftNode == null) {
            //讓當前節點的左指標指向前驅節點
            node.leftNode = pre;
            //改變當前節點左指標型別
            node.leftType = 1;
        }
        //處理前驅的右指標，如果前驅節點的右指標是null（沒有右子樹）
        if (pre != null && pre.rightNode == null) {
            //讓前驅節點的右指標指向當前節點
            pre.rightNode = node;
            //改變前驅節點的右指標型別
            pre.rightType = 1;
        }

        //每處理一個節點，當前節點是下一個節點的前驅節點
        pre = node;

        //處理右子樹
        threadNodes(node.rightNode);
    }

    //遍歷線索二元樹
    public void threadIterate() {
        //用於臨時儲存當前遍歷節點
        ThreadedNode node = root;
        while (node != null) {
            //迴圈找到最開始的節點
            while (node.leftType == 0) {
                node = node.leftNode;
            }
            //列印當前節點的值
            System.out.print(node.value + " ");
            //如果當前節點的右指標指向的是後繼節點，可能後繼節點還有後繼節點
            while (node.rightType == 1) {
                node = node.rightNode;
                System.out.print(node.value + " ");
            }
            //替換遍歷的節點
            node = node.rightNode;

        }
    }

    //獲取根節點
    public ThreadedNode getRoot() {
        return root;
    }

    //先序遍歷
    public void frontShow() {
        if (root != null) {
            root.frontShow();
        }
    }

    //中序遍歷
    public void middleShow() {
        if (root != null) {
            root.middleShow();
        }
    }

    //後序遍歷
    public void afterShow() {
        if (root != null) {
            root.afterShow();
        }
    }

    //先序查詢
    public ThreadedNode frontSearch(int i) {
        return root.frontSearch(i);
    }

    //刪除一個子樹
    public void delete(int i) {
        if (root.value == i) {
            root = null;
        } else {
            root.delete(i);
        }
    }}

• 節點類

public class ThreadedNode {
    //節點的權
    int value;
    //左兒子
    ThreadedNode leftNode;
    //右兒子
    ThreadedNode rightNode;
    //標識指標型別,1表示指向上一個節點，0
    int leftType;
    int rightType;

    public ThreadedNode(int value) {
        this.value = value;
    }

    //設定左兒子
    public void setLeftNode(ThreadedNode leftNode) {
        this.leftNode = leftNode;
    }

    //設定右兒子
    public void setRightNode(ThreadedNode rightNode) {
        this.rightNode = rightNode;
    }

    //先序遍歷
    public void frontShow() {
        //先遍歷當前節點的值
        System.out.print(value + " ");
        //左節點
        if (leftNode != null) {
            leftNode.frontShow(); //遞迴思想
        }
        //右節點
        if (rightNode != null) {
            rightNode.frontShow();
        }
    }

    //中序遍歷
    public void middleShow() {
        //左節點
        if (leftNode != null) {
            leftNode.middleShow(); //遞迴思想
        }
        //先遍歷當前節點的值
        System.out.print(value + " ");
        //右節點
        if (rightNode != null) {
            rightNode.middleShow();
        }
    }

    //後續遍歷
    public void afterShow() {
        //左節點
        if (leftNode != null) {
            leftNode.afterShow(); //遞迴思想
        }
        //右節點
        if (rightNode != null) {
            rightNode.afterShow();
        }
        //先遍歷當前節點的值
        System.out.print(value + " ");
    }

    //先序查詢
    public ThreadedNode frontSearch(int i) {
        ThreadedNode target = null;
        //對比當前節點的值
        if (this.value == i) {
            return this;
            //當前節點不是要查詢的節點
        } else {
            //查詢左兒子
            if (leftNode != null) {
                //查詢的話t賦值給target，查不到target還是null
                target = leftNode.frontSearch(i);
            }
            //如果target不為空，說明在左兒子中已經找到
            if (target != null) {
                return target;
            }
            //如果左兒子沒有查到，再查詢右兒子
            if (rightNode != null) {
                target = rightNode.frontSearch(i);
            }
        }
        return target;
    }

    //刪除一個子樹
    public void delete(int i) {
        ThreadedNode parent = this;
        //判斷左兒子
        if (parent.leftNode != null && parent.leftNode.value == i) {
            parent.leftNode = null;
            return;
        }
        //判斷右兒子
        if (parent.rightNode != null && parent.rightNode.value == i) {
            parent.rightNode = null;
            return;
        }
        //如果都不是，遞迴檢查並刪除左兒子
        parent = leftNode;
        if (parent != null) {
            parent.delete(i);
        }
        //遞迴檢查並刪除右兒子
        parent = rightNode;
        if (parent != null) {
            parent.delete(i);
        }

    }}

• 測試類

public class Demo {
    public static void main(String[] args) {
        //建立一棵樹
        ThreadedBinaryTree binaryTree = new ThreadedBinaryTree();
        //建立一個根節點
        ThreadedNode root = new ThreadedNode(1);
        //把根節點賦給樹
        binaryTree.setRoot(root);
        //建立左,右節點
        ThreadedNode rootLeft = new ThreadedNode(2);
        ThreadedNode rootRight = new ThreadedNode(3);
        //把新建的節點設定為根節點的子節點
        root.setLeftNode(rootLeft);
        root.setRightNode(rootRight);
        //為第二層的左節點建立兩個子節點
        rootLeft.setLeftNode(new ThreadedNode(4));
        ThreadedNode fiveNode = new ThreadedNode(5);
        rootLeft.setRightNode(fiveNode);
        //為第二層的右節點建立兩個子節點
        rootRight.setLeftNode(new ThreadedNode(6));
        rootRight.setRightNode(new ThreadedNode(7));

        //中序遍歷
        binaryTree.middleShow(); //4 2 5 1 6 3 7
        System.out.println();
        //中序線索化二元樹
        binaryTree.threadNodes();//        //獲取5的後繼節點//        ThreadedNode afterFive = fiveNode.rightNode;//        System.out.println(afterFive.value); //1
        binaryTree.threadIterate(); //4 2 5 1 6 3 7
    }}

7.7 二叉排序樹（Binary Sort Tree）

無序序列：
二叉排序樹圖解：

概述：二叉排序樹（Binary Sort Tree）也叫二叉查詢樹或者是一顆空樹，對於二元樹中的任何一個非葉子節點，要求左子節點比當前節點值小，右子節點比當前節點值大

特點：

• 查詢效能與插入刪除效能都適中還不錯
• 中序遍歷的結果剛好是從大到小

建立二叉排序樹原理：其實就是不斷地插入節點，然後進行比較。

刪除節點

• 刪除葉子節點，只需要找到父節點，將父節點與他的連線斷開即可
• 刪除有一個子節點的就需要將他的子節點換到他現在的位置
• 刪除有兩個子節點的節點，需要使用他的前驅節點或者後繼節點進行替換，就是左子樹最右下方的數（最大的那個）或右子樹最左邊的樹（最小的數）；即離節點值最接近的值；（還要註解要去判斷這個值有沒有右節點，有就要將右節點移上來）

程式碼實現：

• 樹類

public class BinarySortTree {
    Node root;

    //新增節點
    public void add(Node node) {
        //如果是一顆空樹
        if (root == null) {
            root = node;
        } else {
            root.add(node);
        }
    }

    //中序遍歷
    public void middleShow() {
        if (root != null) {
            root.middleShow(root);
        }
    }

    //查詢節點
    public Node search(int value) {
        if (root == null) {
            return null;
        }
        return root.search(value);
    }

    //查詢父節點
    public Node searchParent(int value) {
        if (root == null) {
            return null;
        }
        return root.searchParent(value);
    }

    //刪除節點
    public void delete(int value) {
        if (root == null) {
            return;
        } else {
            //找到這個節點
            Node target = search(value);
            //如果沒有這個節點
            if (target == null) {
                return;
            }
            //找到他的父節點
            Node parent = searchParent(value);
            //要刪除的節點是葉子節點
            if (target.left == null && target.left == null) {
                //要刪除的節點是父節點的左子節點
                if (parent.left.value == value) {
                    parent.left = null;
                }
                //要刪除的節點是父節點的右子節點
                else {
                    parent.right = null;
                }
            }
            //要刪除的節點有兩個子節點的情況
            else if (target.left != null && target.right != null) {
                //刪除右子樹中值最小的節點，並且獲取到值
                int min = deletMin(target.right);
                //替換目標節點中的值
                target.value = min;
            }
            //要刪除的節點有一個左子節點或右子節點
            else {
                //有左子節點
                if (target.left != null) {
                    //要刪除的節點是父節點的左子節點
                    if (parent.left.value == value) {
                        parent.left = target.left;
                    }
                    //要刪除的節點是父節點的右子節點
                    else {
                        parent.right = target.left;
                    }

                }
                //有右子節點
                else {
                    //要刪除的節點是父節點的左子節點
                    if (parent.left.value == value) {
                        parent.left = target.right;
                    }
                    //要刪除的節點是父節點的右子節點
                    else {
                        parent.right = target.right;
                    }
                }
            }
        }
    }

    //刪除一棵樹中最小的節點
    private int deletMin(Node node) {
        Node target = node;
        //遞迴向左找最小值
        while (target.left != null) {
            target = target.left;
        }
        //刪除最小的節點
        delete(target.value);
        return target.value;
    }}

• 節點類

public class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //向子樹中新增節點
    public void add(Node node) {
        if (node == null) {
            return;
        }
        /*判斷傳入的節點的值比當前紫薯的根節點的值大還是小*/
        //新增的節點比當前節點更小(傳給左節點）
        if (node.value < this.value) {
            //如果左節點為空
            if (this.left == null) {
                this.left = node;

            }
            //如果不為空
            else {
                this.left.add(node);
            }

        }
        //新增的節點比當前節點更大(傳給右節點）
        else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
    }

    //中序遍歷二叉排序樹，結果剛好是從小到大
    public void middleShow(Node node) {
        if (node == null) {
            return;
        }
        middleShow(node.left);
        System.out.print(node.value + " ");
        middleShow(node.right);
    }

    //查詢節點
    public Node search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (left == null) {
                return null;
            }
            return left.search(value);
        } else {
            if (right == null) {
                return null;
            }
            return right.search(value);
        }
    }

    //查詢父節點
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            if (this.value > value && this.left != null) {
                return this.left.searchParent(value);
            } else if (this.value < value && this.right != null) {
                return this.right.searchParent(value);
            }
            return null;
        }
    }}

• 測試類

public class Demo {
    public static void main(String[] args) {
        int[] arr = {8, 3, 10, 1, 6, 14, 4, 7, 13};
        //建立一顆二叉排序樹
        BinarySortTree bst = new BinarySortTree();
        //迴圈新增/*        for(int i=0;i< arr.length;i++) {
            bst.add(new Node(arr[i]));
        }*/
        for (int i : arr) {
            bst.add(new Node(i));
        }

        //中序遍歷
        bst.middleShow(); //1 3 4 6 7 8 10 13 14
        System.out.println();

        //查詢節點
        Node node = bst.search(10);
        System.out.println(node.value);//10

        Node node2 = bst.search(20);
        System.out.println(node2); //null

        //查詢父節點
        Node node3 = bst.searchParent(1);
        Node node4 = bst.searchParent(14);
        System.out.println(node3.value); //3
        System.out.println(node4.value); //10

        //刪除葉子節點//        bst.delete(13);//        bst.middleShow(); //1 3 4 6 7 8 10 14//        System.out.println();//        //刪除只有一個子節點的節點//        bst.delete(10);//        bst.middleShow(); //1 3 4 6 7 8 ；10和14都沒了

        //刪除有兩個子節點的節點
        bst.delete(3);
        bst.middleShow(); //1 4 6 7 8 10 13 14
    }}

7.8 平衡二元樹（ Balanced Binary Tree）

為什麼使用平衡二元樹？

平衡二元樹（Balanced Binary Tree）又被稱為AVL樹，且具有以下性質：它是一棵空樹或它的左右兩個子樹的高度差的絕對值不超過1，並且左右兩個子樹都是一棵平衡二元樹。這個方案很好的解決了二叉查詢樹退化成連結串列的問題，把插入，查詢，刪除的時間複雜度最好情況和最壞情況都維持在O(logN)。但是頻繁旋轉會使插入和刪除犧牲掉O(logN)左右的時間，不過相對二叉查詢樹來說，時間上穩定了很多。

二叉排序樹插入 {1,2,3,4,5,6} 這種資料結果如下圖所示：

平衡二元樹插入 {1,2,3,4,5,6} 這種資料結果如下圖所示：

如何判斷平衡二元樹？

• 1、是二叉排序樹
• 2、任何一個節點的左子樹或者右子樹都是平衡二元樹（左右高度差小於等於 1）

（1）下圖不是平衡二元樹，因為它不是二叉排序樹違反第 1 條件

（2）下圖不是平衡二元樹，因為有節點子樹高度差大於 1 違法第 2 條件（5的左子樹為0，右子樹為2）

（3）下圖是平衡二元樹，因為符合 1、2 條件

相關概念

平衡因子 BF

• 定義：左子樹和右子樹高度差
• 計算：左子樹高度 - 右子樹高度的值
• 別名：簡稱 BF（Balance Factor）
• 一般來說 BF 的絕對值大於 1，,平衡樹二元樹就失衡，需要旋轉糾正

最小不平衡子樹

• 距離插入節點最近的，並且 BF 的絕對值大於 1 的節點為根節點的子樹。

• 旋轉糾正只需要糾正最小不平衡子樹即可

• 例子如下圖所示：
  

旋轉方式

2 種旋轉方式:

左旋 :

• 舊根節點為新根節點的左子樹
• 新根節點的左子樹（如果存在）為舊根節點的右子樹

右旋：

• 舊根節點為新根節點的右子樹
• 新根節點的右子樹（如果存在）為舊根節點的左子樹

4 種旋轉糾正型別：

• 左左型：插入左孩子的左子樹，右旋
• 右右型：插入右孩子的右子樹，左旋
• 左右型：插入左孩子的右子樹，先左旋，再右旋
• 右左型：插入右孩子的左子樹，先右旋，再左旋
  

左左型：

第三個節點（1）插入的時候，BF(3) = 2，BF(2) = 1，右旋，根節點順時針旋轉

右右型：

第三個節點（3）插入的時候，BF(1)=-2 BF(2)=-1，RR 型失衡，左旋，根節點逆時針旋轉

左右型：

第三個節點（3）插入的 時候，BF(3)=2 BF(1)=-1 LR 型失衡，先 左旋 再 右旋


右左型：

第三個節點（1）插入的 時候，BF(1)=-2 BF(3)=1 RL 型失衡，先 右旋 再 左旋

範例

（1）、依次插入 3、2、1 插入第三個點 1 的時候 BF(3)=2 BF(2)=1，LL 型失衡，對最小不平衡樹 {3,2,1}進行 右旋

• 舊根節點（節點 3）為新根節點（節點 2）的右子樹
• 新根節點（節點 2）的右子樹（這裡沒有右子樹）為舊根節點的左子樹
  

（2）依次插入 4 ，5 插入 5 點的時候 BF(3) = -2 BF(4)=-1，RR 型失衡，對最小不平衡樹 {3,4,5} 進行左旋

• 舊根節點（節點 3）為新根節點（節點 4）的左子樹
• 新根節點（節點 4）的左子樹（這裡沒有左子樹）為舊根節點的右子樹
  

（3）插入 4 ，5 插入 5 點的時候 BF(2)=-2 BF(4)=-1 ，RR 型失衡 對最小不平衡樹{1,2,4}進行左旋

• 舊根節點（節點 2）為新根節點（節點 4）的左子樹
  
• 新根節點（節點 4）的 左子樹（節點 3）為舊根節點的右子樹
  

（4）插入 7 節點的時候 BF(5)=-2, BF(6)=-1 ，RR 型失衡，對最小不平衡樹 進行左旋

• 舊根節點（節點 5）為新根節點（節點 6）的左子樹
• 新根節點的左子樹（這裡沒有）為舊根節點的右子樹
  

（5）依次插入 10 ，9 。插入 9 點的時候 BF(10) = 1，BF(7) = -2，RL 型失衡，對先右旋再左旋，右子樹先右旋

• 舊根節點（節點 10）為新根節點（節點 9）的右子樹
• 新根節點（節點 9）的右子樹（這裡沒有右子樹）為舊根節點的左子樹
  
  最小不平衡子樹再左旋：
• 舊根節點（節點 7）為新根節點（節點 9）的左子樹
• 新根節點（節點 9）的左子樹（這裡沒有左子樹）為舊根節點的右子樹
  

程式碼實現

• 節點類

public class Node {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    //獲取當前節點高度
    public int height() {
        return Math.max(left == null ? 0 : left.height(), right == null ? 0 : right.height()) + 1;
    }

    //獲取左子樹高度
    public int leftHeight() {
        if (left == null) {
            return 0;
        }
        return left.height();
    }

    //獲取右子樹高度
    public int rightHeight() {
        if (right == null) {
            return 0;
        }
        return right.height();
    }


    //向子樹中新增節點
    public void add(Node node) {
        if (node == null) {
            return;
        }
        /*判斷傳入的節點的值比當前紫薯的根節點的值大還是小*/
        //新增的節點比當前節點更小(傳給左節點）
        if (node.value < this.value) {
            //如果左節點為空
            if (this.left == null) {
                this.left = node;

            }
            //如果不為空
            else {
                this.left.add(node);
            }

        }
        //新增的節點比當前節點更大(傳給右節點）
        else {
            if (this.right == null) {
                this.right = node;
            } else {
                this.right.add(node);
            }
        }
        //查詢是否平衡
        //右旋轉
        if (leftHeight() - rightHeight() >= 2) {
            //雙旋轉，當左子樹左邊高度小於左子樹右邊高度時
            if (left != null && left.leftHeight() < left.rightHeight()) {
                //左子樹先進行左旋轉
                left.leftRotate();
                //整體進行右旋轉
                rightRotate();
            }
            //單旋轉
            else {
                rightRotate();
            }
        }
        //左旋轉
        if (leftHeight() - rightHeight() <= -2) {
            //雙旋轉
            if (right != null && right.rightHeight() < right.leftHeight()) {
                right.rightRotate();
                leftRotate();
            }
            //單旋轉
            else {
                leftRotate();
            }
        }
    }

    //右旋轉
    private void rightRotate() {
        //建立一個新的節點，值等於當前節點的值
        Node newRight = new Node(value);
        //把新節點的右子樹設定為當前節點的右子樹
        newRight.right = right;
        //把新節點的左子樹設定為當前節點的左子樹的右子樹
        newRight.left = left.right;
        //把當前節點的值換位左子節點的值
        value = left.value;
        //把當前節點的左子樹設定為左子樹的左子樹
        left = left.left;
        //把當前節點設定為新節點
        right = newRight;
    }

    //左旋轉
    private void leftRotate() {
        //建立一個新的節點，值等於當前節點的值
        Node newLeft = new Node(value);
        //把新節點的左子樹設定為當前節點的左子樹
        newLeft.left = left;
        //把新節點的右子樹設定為當前節點的右子樹的左子樹
        newLeft.right = right.left;
        //把當前節點的值換位右子節點的值
        value = right.value;
        //把當前節點的右子樹設定為右子樹的右子樹
        right = right.right;
        //把當前節點設定為新節點
        left = newLeft;
    }

    //中序遍歷二叉排序樹，結果剛好是從小到大
    public void middleShow(Node node) {
        if (node == null) {
            return;
        }
        middleShow(node.left);
        System.out.print(node.value + " ");
        middleShow(node.right);
    }

    //查詢節點
    public Node search(int value) {
        if (this.value == value) {
            return this;
        } else if (value < this.value) {
            if (left == null) {
                return null;
            }
            return left.search(value);
        } else {
            if (right == null) {
                return null;
            }
            return right.search(value);
        }
    }

    //查詢父節點
    public Node searchParent(int value) {
        if ((this.left != null && this.left.value == value) || (this.right != null && this.right.value == value)) {
            return this;
        } else {
            if (this.value > value && this.left != null) {
                return this.left.searchParent(value);
            } else if (this.value < value && this.right != null) {
                return this.right.searchParent(value);
            }
            return null;
        }
    }}

• 測試類

public class Demo {
    public static void main(String[] args) {
        int[] arr = {1,2,3,4,5,6};
        //建立一顆二叉排序樹
        BinarySortTree bst = new BinarySortTree();
        //迴圈新增
        for (int i : arr) {
            bst.add(new Node(i));
        }
        //檢視高度
        System.out.println(bst.root.height()); //3
        //檢視節點值
        System.out.println(bst.root.value); //根節點為4
        System.out.println(bst.root.left.value); //左子節點為2
        System.out.println(bst.root.right.value); //右子節點為5
    }}

第8章 赫夫曼樹

8.1 赫夫曼樹概述

HuffmanTree因為翻譯不同所以有其他的名字：赫夫曼樹、霍夫曼樹、哈夫曼樹

赫夫曼樹又稱最優二元樹，是一種帶權路徑長度最短的二元樹。所謂樹的帶權路徑長度，就是樹中所有的葉結點的權值乘上其到根結點的路徑長度（若根結點為0層，葉結點到根結點的路徑長度為葉結點的層數）。樹的路徑長度是從樹根到每一結點的路徑長度之和，記為WPL=（W1L1+W2L2+W3L3+…+WnLn），N個權值Wi（i=1,2,…n）構成一棵有N個葉結點的二元樹，相應的葉結點的路徑長度為Li（i=1,2,…n）。可以證明赫夫曼樹的WPL是最小的。

8.2 赫夫曼樹定義

路徑： 路徑是指從一個節點到另一個節點的分支序列。

路徑長度： 指從一個節點到另一個結點所經過的分支數目。 如下圖：從根節點到a的分支數目為2

樹的路徑長度： 樹中所有結點的路徑長度之和為樹的路徑長度PL。 如下圖：PL為10

節點的權： 給樹的每個結點賦予一個具有某種實際意義的實數，我們稱該實數為這個結點的權。如下圖：7、5、2、4

帶權路徑長度： 從樹根到某一結點的路徑長度與該節點的權的乘積，叫做該結點的帶權路徑長度。如下圖：A的帶權路徑長度為2*7=14

樹的帶權路徑長度（WPL）： 樹的帶權路徑長度為樹中所有葉子節點的帶權路徑長度之和

最優二元樹：權值最大的節點離跟節點越近的二元樹，所得WPL值最小，就是最優二元樹。如下圖：（b）

• （a）WPL=9*2+4*2+5*2+2*2=40
• （b）WPL=9*1+5*2+4*3+2*3=37
• （c） WPL=4*1+2*2+5*3+9*3=50

8.3 構造赫夫曼樹步驟

對於陣列{5,29,7,8,14,23,3,11}，我們把它構造成赫夫曼樹

第一步：使用陣列中所有元素建立若干個二元樹，這些值作為節點的權值（只有一個節點）。

第二步：將這些節點按照權值的大小進行排序。

第三步：取出權值最小的兩個節點，並建立一個新的節點作為這兩個節點的父節點，這個父節點的權值為兩個子節點的權值之和。將這兩個節點分別賦給父節點的左右節點

第四步：刪除這兩個節點，將父節點新增進集合裡

第五步：重複第二步到第四步，直到集合中只剩一個元素，結束迴圈

8.4 程式碼實現

• 節點類

//介面實現排序功能public class Node implements Comparable<Node> {
    int value;
    Node left;
    Node right;

    public Node(int value) {
        this.value = value;
    }

    @Override
    public int compareTo(Node o) {
        return -(this.value - o.value); //集合倒敘，從大到小
    }

    @Override
    public String toString() {
        return "Node value=" + value ;
    }}

• 測試類

import java.util.ArrayList;import java.util.Collections;import java.util.List;public class Demo {
    public static void main(String[] args) {
        int[] arr = {5, 29, 7, 8, 14, 23, 3, 11};
        Node node = createHuffmanTree(arr);
        System.out.println(node); //Node value=100
    }

    //建立赫夫曼樹
    public static Node createHuffmanTree(int[] arr) {
        //使用陣列中所有元素建立若干個二元樹（只有一個節點）
        List<Node> nodes = new ArrayList<>();
        for (int value : arr) {
            nodes.add(new Node(value));
        }

        //迴圈處理
        while (nodes.size() > 1) {
            //排序
            Collections.sort(nodes);
            //取出最小的兩個二元樹（集合為倒敘，從大到小）
            Node left = nodes.get(nodes.size() - 1); //權值最小
            Node right = nodes.get(nodes.size() - 2); //權值次小
            //建立一個新的二元樹
            Node parent = new Node(left.value + right.value);
            //刪除原來的兩個節點
            nodes.remove(left);
            nodes.remove(right);
            //新的二元樹放入原來的二元樹集合中
            nodes.add(parent);
            //列印結果
            System.out.println(nodes);
        }
        return nodes.get(0);
    }}

• 迴圈次數結果

[Node value=29, Node value=23, Node value=14, Node value=11, Node value=8, Node value=7, Node value=8][Node value=29, Node value=23, Node value=14, Node value=11, Node value=8, Node value=15][Node value=29, Node value=23, Node value=15, Node value=14, Node value=19][Node value=29, Node value=23, Node value=19, Node value=29][Node value=29, Node value=29, Node value=42][Node value=42, Node value=58][Node value=100]Node value=100Process finished with exit code 0

第9章 多路查詢樹（2-3樹、2-3-4樹、B樹、B+樹）

9.1 為什麼使用多路查詢樹

二元樹存在的問題

二元樹需要載入到記憶體的，如果二元樹的節點少，沒有什麼問題，但是如果二元樹的節點很多(比如1億)， 就存在如下問題:

• 問題1：在構建二元樹時，需要多次進行I/O操作(海量資料存在資料庫或檔案中)，節點海量，構建二元樹時，速度有影響.

• 問題2：節點海量，也會造成二元樹的高度很大，會降低操作速度.
  

解決上述問題 —> 多叉樹

多路查詢樹

• 1、在二元樹中，每個節點有資料項，最多有兩個子節點。如果允許每個節點可以有更多的資料項和更多的子節點，就是多叉樹（multiway tree）
• 2、後面我們講解的"2-3樹"，"2-3-4樹"就是多叉樹，多叉樹通過重新組織節點，減少樹的高度，能對二元樹進行優化。
• 3、舉例說明(下面2-3樹就是一顆多叉樹)
  

9.2 2-3樹

2-3樹定義

• 所有葉子節點都要在同一層
• 二節點要麼有兩個子節點，要麼沒有節點
• 三節點要麼沒有節點，要麼有三個子節點
• 不能出現節點不滿的情況
  

2-3樹插入的操作

插入原理：

對於2-3樹的插入來說，與平衡二元樹相同，插入操作一定是發生在葉子節點上，並且節點的插入和刪除都有可能導致不平衡的情況發生，在插入和刪除節點時也是需要動態維持平衡的，但維持平衡的策略和AVL樹是不一樣的。

AVL樹向下新增節點之後通過旋轉來恢復平衡，而2-3樹是通過節點向上分裂來維持平衡的，也就是說2-3樹插入元素的過程中層級是向上增加的，因此不會導致葉子節點不在同一層級的現象發生，也就不需要旋轉了。

三種插入情況：

1）對於空樹，插入一個2節點即可；

2）插入節點到一個2節點的葉子上。由於本身就只有一個元素，所以只需要將其升級為3節點即可（如：插入3）。

3）插入節點到一個3節點的葉子上。因為3節點本身最大容量，因此需要拆分，且將樹中兩元素或者插入元素的三者中選擇其一向上移動一層。

分為三種情況：

• 升級父節點（插入5）
  
• 升級根節點（插入11）
  
• 增加樹高度（插入2，從下往上拆）
  

2-3樹刪除的操作

刪除原理：2-3樹的刪除也分為三種情況，與插入相反。

三種刪除情況：

1）所刪元素位於一個3節點的葉子節點上，直接刪除，不會影響樹結構（如：刪除9）

2）所刪元素位於一個2節點上，直接刪除，破壞樹結構

分為四種情況：

• 此節點雙親也是2節點，且擁有一個3節點的右孩子（如：刪除1）
  

• 此節點的雙親是2節點，它右孩子也是2節點（如：刪除4）
  

• 此節點的雙親是3節點（如：刪除10）
  

• 當前樹是一個滿二元樹，降低樹高（如：刪除8）
  

3）所刪元素位於非葉子的分支節點。此時按樹中序遍歷得到此元素的前驅或後續元素，補位

兩種情況：

• 分支節點是2節點（如：刪除4）
  
• 分支節點是3節點（如：刪除12）
  

9.3 2-3-4樹

2-3-4樹是2-3樹的擴充套件，包括了 4 節點的使用，一個 4 節點包含小中大三個元素和四個孩子（或沒有孩子）

2-3-4樹的插入操作

1）如果待插入的節點不是 4 節點，則直接插入即可

2）如果待插入的節點是 4 節點，則先把新節點臨時插入進去變成 5 節點，然後對 5 節點進行向上分裂、合併，5 節點分裂成兩個 2 節點（5 節點最小的元素、5 節點第二個元素）、1個 3 節點（5 節點後兩個元素），然後將分裂之後的第2個 2 節點向上合併到父節點中，然後把父節點作為插入元素之後的當前節點，重複（1）、（2）步驟，直到滿足2-3-4樹的定義性質

2-3-4樹的刪除操作

刪除順序使1,6,3,4,5,2,9

9.4 B樹

B樹（BTree）是一種平衡的多路查詢樹，2-3樹和2-3-4樹都是B樹的特例。

我們把結點最大的孩子樹目稱為B樹的階，因此，2-3樹是3階B樹，2-3-4樹是4階B樹

如下圖，比如說要查詢7，首先從外存讀取得到根節點3,5,8三個元素，發現7不在，但是5、8之間，因此就通過A2再讀取外存的2,6,7節點找到結束。

B樹的資料結構為內外存的資料互動準備的。當要處理的資料很大時，無法一次全部裝入記憶體。這時對B樹調整，使得B樹的階數與硬碟儲存的頁面大小相匹配。比如說一棵B樹的階為1001（即1個節點包含1000個關鍵字），高度為2（從0開始），它可以儲存超過10億個關鍵字（1001x1001x1000+1001x1000+1000）,只要讓根節點持久的保留在記憶體中，那麼在這顆樹上，尋找某一個關鍵字至多需要兩次硬碟的讀取即可。

對於n個關鍵字的m階B樹，最壞情況查詢次數計算
第一層至少1個節點，第二層至少2個節點，由於除根節點外每個分支節點至少有⌈m/2⌉棵子樹，則第三層至少有2x⌈m/2⌉個節點。。。這樣第k+1層至少有2x(⌈m/2⌉)^(k-1),實際上，k+1層的節點就是葉子節點。若m階B樹有n個關鍵字，那麼當你找到葉子節點，其實也就等於查詢不成功的節點為n+1，因此
n+1>=2x(⌈m/2⌉)^(k-1),即

在含有n個關鍵字的B樹上查詢時，從根節點到關鍵位元組點的路徑上涉及的節點數不超多

9.5 B+樹

B+樹可以說是B樹的升級版，相對於B樹來說B+樹更充分的利用了節點的空間，讓查詢速度更加穩定，其速度完全接近於二分法查詢。大部分檔案系統和資料均採用B+樹來實現索引結構。
 
下圖B樹，我們要遍歷它，假設每個節點都屬於硬碟的不同頁面，我們為了中序遍歷所有的元素，頁面2-頁面1-頁面3-頁面1-頁面4-頁面1-頁面5，頁面1遍歷了3次，而且我們每經過節點遍歷時，都會對節點中的元素進行一次遍歷

B+樹是應檔案系統所需而出的一種B樹的變形樹，在B樹中，每一個元素樹中只出現一次，而B+樹中，出現在分支節點中的元素會被當做他們在該分支節點位置的中序後繼者（葉子節點）中再次列出。另外，每一個葉子節點都會儲存一個指向後一葉子節點的指標。
下圖就是B+樹，灰色關鍵字，在根節點出現，在葉子節點中再次列出

一棵m階的B+樹和m階的B樹的差異在於：

• 有n棵子樹的非葉節點中包含有n個關鍵字（B樹中是n-1個關鍵字），但是每個關鍵字不儲存資料，只用來儲存葉子節點相同關鍵字的索引，所有資料都儲存在葉子節點。（此處，對於非葉節點的m顆子樹和n個關鍵字的關係，mysql的索引結構似乎是m=n+1，而不是上面的m=n）
• 所有的非葉節點元素都同時存在於子節點，在子節點元素中是最大（或最小）元素。
• 所有的葉子節點包含全部關鍵字的資訊，及指向含這些關鍵字所指向的具體磁碟記錄的指標data，並且每一個葉子節點帶有指向下一個相鄰的葉節點指標，形成連結串列

9.6 總結

• B樹的非葉節點會儲存關鍵字及其對應的資料地址，B+樹的非葉節點只存關鍵字索引，不會存具體的資料地址，因此B+樹的一個節點相比B樹能儲存更多的索引元素，一次性讀入記憶體的需要查詢的關鍵字也就越多，B+樹的高度更小，相對IO讀寫次數就降低了。

• B樹的查詢效率並不穩定，最好的情況只查詢一次（根節點），最壞情況是查詢到葉子節點，而B+樹由於非葉節點不存資料地址，而只是葉子節點中關鍵字的索引。所有查詢都要查詢到葉子節點才算命中，查詢效率比較穩定。這對於sql語句的優化是非常有幫助的。

• B+樹所有葉子節點形成有序連結串列，只需要去遍歷葉子節點就可以實現整棵樹的遍歷。方便資料的範圍查詢，而B樹不支援這樣的操作或者說效率太低。

• 現代資料庫和檔案系統的索引表大部分是使用B+樹來實現的，但並不是全部

第10章 圖結構

10.1 圖的基本概念

圖（Graph）是一種複雜的非線性結構，在圖結構中，每個元素都可以有零個或多個前驅，也可以有零個或多個後繼，也就是說，元素之間的關係是任意的。

常用術語：

圖的結構很簡單，就是由頂點 V 集和邊 E 集構成，因此圖可以表示成 G = (V,E)

無向圖：

若頂點 Vi 到 Vj 之間的邊沒有方向，則稱這條邊為無向邊 (Edge) ，用無序偶對 (Vi，Vj) 來表示。如果圖中任意兩個頂點之間的邊都是無向邊，則稱該圖為無向圖 (Undirected graphs)。

如：下圖就是一個無向圖，由於是無方向的，連線頂點 A 與 D 的邊，可以表示無序佇列（A，D），也可以寫成 （D，A）,但不能重複。頂點集合 V = {A,B,C,D}；邊集合 E = {(A,B),(A,D),(A,C)(B,C),(C,D),}

有向圖：

用有序偶<Vi，Vj>來表示，Vi 稱為弧尾 (Tail) ， Vj稱為弧頭 (Head)。 如果圖中任意兩個頂點之間的邊都是有向邊，則稱該圖為有向圖 (Directed grahs)。

如：下圖就是一個有向圖。連線頂點 A 到 D 的有向邊就是弧，A是弧尾，D 是弧頭， <A, D>表示弧， 注意不能寫成<D,A>。其中頂點集合 V = { A,B,C,D}； 弧集合 E = {<A,D>,<B,A>,<B,C>,<C,A>}

注意：無向邊用小括號 「()」 表示，而有向邊則是用尖括號"<>"表示

有權圖：

有些圖的邊或弧具有與它相關的數位，這種與圖的邊或弧相關的數叫做權 (Weight) 。這些權可以表示從一個頂點到另一個頂點的距離或耗費。這種帶權的圖通常稱為網 (Network)。

如下圖

10.2 圖的儲存結構及實現

圖結構的常見的兩個儲存方式： 鄰接矩陣 、鄰接表

鄰接矩陣

圖中的 0 表示該頂點無法通向另一個頂點，相反 1 就表示該頂點能通向另一個頂點

先來看第一行，該行對應的是頂點A，那我們就拿頂點A與其它點一一對應，發現頂點A除了不能通向頂點D和自身，可以通向其它任何一個的頂點

因為該圖為無向圖，因此頂點A如果能通向另一個頂點，那麼這個頂點也一定能通向頂點A，所以這個頂點對應頂點A的也應該是 1

雖然我們確實用鄰接矩陣表示了圖結構，但是它有一個致命的缺點，那就是矩陣中存在著大量的 0，這在程式中會佔據大量的記憶體。此時我們思考一下，0 就是表示沒有，沒有為什麼還要寫，所以我們來看一下第二種表示圖結構的方法，它就很好的解決了鄰接矩陣的缺陷

程式碼實現：

• 頂點類

public class Vertex {

    private String value;

    public Vertex(String value) {
        this.value = value;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value;
    }}

• 圖類

public class Graph {

    private Vertex[] vertex; //頂點陣列
    private int currentSize; //預設頂點位置
    public int[][] adjMat; //鄰接表

    public Graph(int size) {
        vertex = new Vertex[size];
        adjMat = new int[size][size];
    }

    //向圖中加入頂點
    public void addVertex(Vertex v) {
        vertex[currentSize++] = v;
    }

    //新增邊
    public void addEdge(String v1, String v2) {
        //找出兩個點的下標
        int index1 = 0;
        for (int i = 0; i < vertex.length; i++) {
            if (vertex[i].getValue().equals(v1)) {
                index1 = i;
                break;
            }
        }
        int index2 = 0;
        for (int i = 0; i < vertex.length; i++) {
            if (vertex[i].getValue().equals(v2)) {
                index2 = i;
                break;
            }
        }
        //表示兩個點互通
        adjMat[index1][index2] = 1;
        adjMat[index2][index1] = 1;
    }}

• 測試類

public class Demo {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("A");
        Vertex v2 = new Vertex("B");
        Vertex v3 = new Vertex("C");
        Vertex v4 = new Vertex("D");
        Vertex v5 = new Vertex("E");
        Graph g = new Graph(5);
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);
        g.addVertex(v5);

        //增加邊
        g.addEdge("A", "B");
        g.addEdge("A", "C");
        g.addEdge("A", "E");
        g.addEdge("C", "E");
        g.addEdge("C", "D");

        for (int[] a : g.adjMat) {
            System.out.println(Arrays.toString(a));
        }
    }}

• 結果值

[0, 1, 1, 0, 1][1, 0, 0, 0, 0][1, 0, 0, 1, 1][0, 0, 1, 0, 0][1, 0, 1, 0, 0]

鄰接表

鄰接表 是由每個頂點以及它的相鄰頂點組成的

如上圖：圖中最左側紅色的表示各個頂點，它們對應的那一行儲存著與它相關聯的頂點

• 頂點A 與 頂點B 、頂點C 、頂點E 相關聯
• 頂點B 與 頂點A 相關聯
• 頂點C 與 頂點A 、頂點D 、頂點E 相關聯
• 頂點D 與 頂點C 相關聯
• 頂點E 與 頂點A 、頂點C 相關聯

10.3 圖的遍歷方式及實現

從圖中某一頂點出發訪遍圖中其餘頂點，且使每一個頂點僅被存取一次，這一過程就叫做圖的遍歷

在圖結構中，存在著兩種遍歷搜尋的方式，分別是 廣度優先搜尋 和 深度優先搜尋

廣度優先搜尋

廣度優先遍歷（BFS）：類似於圖的層次遍歷，它的基本思想是：首先存取起始頂點v，然後選取v的所有鄰接點進行存取，再依次對v的鄰接點相鄰接的所有點進行存取，以此類推，直到所有頂點都被存取過為止

BFS和樹的層次遍歷一樣，採取佇列實現，這裡新增一個標記陣列，用來標記遍歷過的頂點

執行步驟：

• 1、先把 A 壓入佇列，然後做出隊操作，A 出隊
• 2、把 A 直接相關的頂點 ，B、F 做入隊操作
• 3、B 做出隊操作，B 相關的點 C、I、G 做入隊操作
• 4、F 做出隊操作，F 相關的點 E 做入隊操作
• 5、C 做出隊操作，C 相關的點 D 做入隊操作
• 6、I 做出隊操作（I 相關的點B、C、D 都已經做過入隊操作了，不能重複入隊）
• 7、G 做出隊操作，G 相關的點 H 做入隊操作
• 8、E 做出隊操作…
• 9、D 做出隊操作…
• 10、H 做出隊操作，沒有元素了

程式碼實現：

深度優先搜尋

深度優先遍歷（DFS）：從一個頂點開始，沿著一條路徑一直搜尋，直到到達該路徑的最後一個結點，然後回退到之前經過但未搜尋過的路徑繼續搜尋，直到所有路徑和結點都被搜尋完畢

DFS與二元樹的先序遍歷類似，可以採用遞迴或者棧的方式實現

執行步驟：

• 1、從 1 出發，路徑為：1 -> 2 -> 3 -> 6 -> 9 -> 8 -> 5 -> 4
• 2、當搜尋到 4 時，相鄰沒有發現未被存取的點，此時我們要往後倒退，找尋別的沒搜尋過的路徑
• 3、退回到 5 ，相鄰沒有發現未被存取的點，繼續後退
• 4、退回到 8 ，相鄰發現未被存取的點 7，路徑為：8 -> 7
• 5、當搜尋到 7 ，相鄰沒有發現未被存取的點，，此時我們要往後倒退…
• 6、退回路徑7 -> 8 -> 9 -> 6 -> 3 -> 2 -> 1，流程結束

程式碼實現：

• 棧類

public class MyStack {

    //棧的底層使用陣列來儲存資料
    //private int[] elements;
    int[] elements; //測試時使用

    public MyStack() {
        elements = new int[0];
    }

    //新增元素
    public void push(int element) {
        //建立一個新的陣列
        int[] newArr = new int[elements.length + 1];
        //把原陣列中的元素複製到新陣列中
        for (int i = 0; i < elements.length; i++) {
            newArr[i] = elements[i];
        }
        //把新增的元素放入新陣列中
        newArr[elements.length] = element;
        //使用新陣列替換舊陣列
        elements = newArr;
    }

    //取出棧頂元素
    public int pop() {
        //當棧中沒有元素
        if (is_empty()) {
            throw new RuntimeException("棧空");
        }
        //取出陣列的最後一個元素
        int element = elements[elements.length - 1];
        //建立一個新陣列
        int[] newArr = new int[elements.length - 1];
        //原陣列中除了最後一個元素其他元素放入新陣列
        for (int i = 0; i < elements.length - 1; i++) {
            newArr[i] = elements[i];
        }
        elements = newArr;
        return element;
    }

    //檢視棧頂元素
    public int peek() {
        return elements[elements.length - 1];
    }

    //判斷棧是否為空
    public boolean is_empty() {
        return elements.length == 0;
    }

    //檢視棧的元素個數
    public int size() {
        return elements.length;
    }}

• 頂點類

public class Vertex {

    private String value;
    public boolean visited; //存取狀態

    public Vertex(String value) {
        super();
        this.value = value;
    }

    public String getValue() {
        return value;
    }

    public void setValue(String value) {
        this.value = value;
    }

    @Override
    public String toString() {
        return value;
    }}

• 圖類

import mystack.MyStack;public class Graph {

    private Vertex[] vertex; //頂點陣列
    private int currentSize; //預設頂點位置
    public int[][] adjMat; //鄰接表
    private MyStack stack = new MyStack(); //棧
    private int currentIndex; //當前遍歷的下標

    public Graph(int size) {
        vertex = new Vertex[size];
        adjMat = new int[size][size];
    }

    //向圖中加入頂點
    public void addVertex(Vertex v) {
        vertex[currentSize++] = v;
    }

    //新增邊
    public void addEdge(String v1, String v2) {
        //找出兩個點的下標
        int index1 = 0;
        for (int i = 0; i < vertex.length; i++) {
            if (vertex[i].getValue().equals(v1)) {
                index1 = i;
                break;
            }
        }
        int index2 = 0;
        for (int i = 0; i < vertex.length; i++) {
            if (vertex[i].getValue().equals(v2)) {
                index2 = i;
                break;
            }
        }
        //表示兩個點互通
        adjMat[index1][index2] = 1;
        adjMat[index2][index1] = 1;
    }

    //深度優先搜尋
    public void dfs() {
        //把第0個頂點標記為已存取狀態
        vertex[0].visited = true;
        //把第0個的下標放入棧中
        stack.push(0);
        //列印頂點值
        System.out.println(vertex[0].getValue());
        //遍歷
        out:
        while (!stack.is_empty()) {
            for (int i = currentIndex + 1; i < vertex.length; i++) {
                //如果和下一個遍歷的元素是通的
                if (adjMat[currentIndex][i] == 1 && vertex[i].visited == false) {
                    //把下一個元素壓入棧中
                    stack.push(i);
                    vertex[i].visited = true;
                    System.out.println(vertex[i].getValue());
                    continue out;
                }
            }
            //彈出棧頂元素（往後退）
            stack.pop();
            //修改當前位置為棧頂元素的位置
            if (!stack.is_empty()) {
                currentIndex = stack.peek();
            }
        }
    }}

• 測試類

import java.util.Arrays;public class Demo {
    public static void main(String[] args) {
        Vertex v1 = new Vertex("A");
        Vertex v2 = new Vertex("B");
        Vertex v3 = new Vertex("C");
        Vertex v4 = new Vertex("D");
        Vertex v5 = new Vertex("E");
        Graph g = new Graph(5);
        g.addVertex(v1);
        g.addVertex(v2);
        g.addVertex(v3);
        g.addVertex(v4);
        g.addVertex(v5);

        //增加邊
        g.addEdge("A", "B");
        g.addEdge("A", "C");
        g.addEdge("A", "E");
        g.addEdge("C", "E");
        g.addEdge("C", "D");

        for (int[] a : g.adjMat) {
            System.out.println(Arrays.toString(a));
        }

        //深度優先遍歷
        g.dfs();//        A//        B//        C//        E//        D
    }}

第11章 氣泡排序（含改進版）

11.1 氣泡排序概念

氣泡排序（Bubble Sort）是一種簡單的排序演演算法。它重複地遍歷要排序的數列，一次比較兩個元素，如果他們的順序錯誤就把他們交換過來。遍歷數列的工作是重複地進行直到沒有再需要交換，也就是說該數列已經排序完成。這個演演算法的名字由來是因為越小的元素會經由交換慢慢「浮」到數列的頂端。

執行流程：

• 比較相鄰的元素。如果第一個比第二個大（升序），就交換他們兩個。
• 對每一對相鄰元素作同樣的工作，從開始第一對到結尾的最後一對。這步做完後，最後的元素會是最大的數。
• 針對所有的元素重複以上的步驟，除了最後一個。
• 持續每次對越來越少的元素重複上面的步驟，直到沒有任何一對數位需要比較。

動圖實現：

靜圖詳解：

交換過程圖示(第一次)：
那麼我們需要進行n-1次冒泡過程，每次對應的比較次數如下圖所示：

11.2 程式碼實現

import java.util.Arrays;public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        bubbleSort(arr);//        [4, 5, 3, 2, 1, 6]//        [4, 3, 2, 1, 5, 6]//        [3, 2, 1, 4, 5, 6]//        [2, 1, 3, 4, 5, 6]//        [1, 2, 3, 4, 5, 6]
    }

    //氣泡排序，共需要比較length-1輪
    public static void bubbleSort(int[] arr) {
        //控制一共比較多少輪
        for (int i = 0; i < arr.length - 1; i++) {
            //控制比較次數
            for (int j = 0; j < arr.length - 1 - i; j++) {
                if (arr[j] > arr[j + 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j + 1];
                    arr[j + 1] = temp;
                }
            }
            //列印每次排序後的結果
            System.out.println(Arrays.toString(arr)); 
        }
    }}

11.3 時間複雜度

• 最優時間複雜度：O(n) （表示遍歷一次發現沒有任何可以交換的元素，排序結束。）
• 最壞時間複雜度：O(n^2)
• 穩定性：穩定

排序分析：待排陣列中一共有6個數，第一輪排序時進行了5次比較，第二輪排序時進行了4比較，依次類推，最後一輪進行了1次比較。

陣列元素總數為N時，則一共需要的比較次數為：(N-1)+ (N-2)+ (N-3)+ ...1=N*(N-1)/2

演演算法約做了N^2/2次比較。因為只有在前面的元素比後面的元素大時才交換資料，所以交換的次數少於比較的次數。如果資料是隨機的，大概有一半資料需要交換，則交換的次數為N^2/4（不過在最壞情況下，即初始資料逆序時，每次比較都需要交換）。

交換和比較的操作次數都與 N^2 成正比，由於在大O表示法中，常數忽略不計，氣泡排序的時間複雜度為O(N^2)。

O(N2)的時間複雜度是一個比較糟糕的結果，尤其在資料量很大的情況下。所以氣泡排序通常不會用於實際應用。

11.4 程式碼改進

傳統的冒泡演演算法每次排序只確定了最大值，我們可以在每次迴圈之中進行正反兩次冒泡，分別找到最大值和最小值，如此可使排序的輪數減少一半

import java.util.Arrays;public class BubbleSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        bubbleSort(arr);//        [1, 4, 5, 3, 2, 6]//        [1, 2, 4, 3, 5, 6]//        [1, 2, 3, 4, 5, 6]
    }

    //氣泡排序改進
    public static void bubbleSort(int[] arr) {
        int left = 0;
        int right = arr.length - 1;
        while (left < right) {
            //正向冒泡，確定最大值
            for (int i = left; i < right; ++i) {
                //如果前一位大於後一位，交換位置
                if (arr[i] > arr[i + 1]) {
                    int temp = arr[i];
                    arr[i] = arr[i + 1];
                    arr[i + 1] = temp;
                }
            }
            --right;

            //反向冒泡，確定最小值
            for (int j = right; j > left; --j) {
                //如果前一位大於後一位，交換位置
                if (arr[j] < arr[j - 1]) {
                    int temp = arr[j];
                    arr[j] = arr[j - 1];
                    arr[j - 1] = temp;
                }
            }
            ++left;
            
            System.out.println(Arrays.toString(arr));
        }
    }}

第12章 選擇排序（含改進版）

12.1 選擇排序概念

選擇排序（Selection sort）是一種簡單直觀的排序演演算法。它的工作原理如下。首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然後，再從剩餘未排序元素中繼續尋找最小（大）元素，然後放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。

選擇排序的主要優點與資料移動有關。如果某個元素位於正確的最終位置上，則它不會被移動。選擇排序每次交換一對元素，它們當中至少有一個將被移到其最終位置上，因此對n個元素的表進行排序總共進行至多n-1次交換。在所有的完全依靠交換去移動元素的排序方法中，選擇排序屬於非常好的一種

動圖展示：

動圖1：

動圖2：

12.2 程式碼實現

import java.util.Arrays;public class seletsort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        selectSort(arr);//        [1, 5, 6, 3, 2, 4]//        [1, 2, 6, 3, 5, 4]//        [1, 2, 3, 6, 5, 4]//        [1, 2, 3, 4, 5, 6]//        [1, 2, 3, 4, 5, 6]//        [1, 2, 3, 4, 5, 6]
    }

    //選擇排序
    public static void selectSort(int[] arr) {
        //遍歷所有的數
        for (int i = 0; i < arr.length; i++) {
            int minIndex = i;
            //把當前遍歷的數和後面所有的數依次進行比較，並記錄最小的數的下標
            for (int j = i + 1; j < arr.length; j++) {
                //如果後面比較的數比記錄的最小的數小
                if (arr[minIndex] > arr[j]) {
                    //記錄最小的那個數的下標
                    minIndex = j;
                }
            }
            //如果發現了更小的元素，與第一個元素交換位置（第一個不是最小的元素）
            if (i != minIndex) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;
            }
            //列印每次排序後的結果
            System.out.println(Arrays.toString(arr));
        }
    }}

12.3 時間複雜度

• 最優時間複雜度：O(n^2)
• 最壞時間複雜度：O(n^2)
• 穩定性：不穩定（考慮升序每次選擇最大的情況）

選擇排序與氣泡排序一樣，需要進行N*(N-1)/2次比較，但是隻需要N次交換，當N很大時，交換次數的時間影響力更大，所以選擇排序的時間複雜度為O(N^2)。

雖然選擇排序與氣泡排序在時間複雜度屬於同一量級，但是毫無疑問選擇排序的效率更高，因為它的交換操作次數更少，而且在交換操作比比較操作的時間級大得多時，選擇排序的速度是相當快的。

12.4 程式碼改進

傳統的選擇排序每次只確定最小值，根據改進冒泡演演算法的經驗，我們可以對排序演演算法進行如下改進：每趟排序確定兩個最值——最大值與最小值，這樣就可以將排序趟數縮減一半

改進後程式碼如下：

import java.util.Arrays;public class seletsort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        selectSort(arr);//        [1, 5, 4, 3, 2, 6]//        [1, 2, 4, 3, 5, 6]//        [1, 2, 3, 4, 5, 6]

    }

    //選擇排序改進
    public static void selectSort(int[] arr) {
        int minIndex; // 儲存最小元素的小標
        int maxIndex; // 儲存最大元素的小標

        for (int i = 0; i < arr.length / 2; i++) {
            minIndex = i;
            maxIndex = i;
            //每完成一輪排序，就確定了兩個最值，下一輪排序時比較範圍減少兩個元素
            for (int j = i + 1; j <= arr.length - 1 - i; j++) {
                //如果待排陣列中的某個元素比當前元素小，minIndex指向該元素的下標
                if (arr[j] < arr[minIndex]) {
                    minIndex = j;
                    continue;
                }
                //如果待排陣列中的某個元素比當前元素大，maxIndex指向該元素的下標
                else if (arr[j] > arr[maxIndex]) {
                    maxIndex = j;
                }
            }

            //如果發現了更小的元素，與第一個元素交換位置（第一個不是最小的元素）
            if (i != minIndex) {
                int temp = arr[i];
                arr[i] = arr[minIndex];
                arr[minIndex] = temp;

                // 原來的第一個元素已經與下標為minIndex的元素交換了位置
                // 所以現在arr[minIndex]存放的才是之前第一個元素中的資料
                // 如果之前maxIndex指向的是第一個元素，那麼需要將maxIndex重新指向arr[minIndex]
                if (maxIndex == i) {
                    maxIndex = minIndex;
                }
            }

            // 如果發現了更大的元素，與最後一個元素交換位置
            if (arr.length - 1 - i != maxIndex) {
                int temp = arr[arr.length - 1 - i];
                arr[arr.length - 1 - i] = arr[maxIndex];
                arr[maxIndex] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }}

第13章 插入排序（含改進版）

13.1 插入排序概念

插入排序（Insertion Sort）是一種簡單直觀的排序演演算法。它的工作原理是通過構建有序序列，對於未排序資料，在已排序序列中從後向前掃描，找到相應位置並插入。插入排序在實現上，在從後向前掃描過程中，需要反覆把已排序元素逐步向後挪位，為最新元素提供插入空間

動圖展示：

13.2 程式碼實現

import java.util.Arrays;public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        insertSort(arr);//        [4, 5, 6, 3, 2, 1]//        [4, 5, 6, 3, 2, 1]//        [3, 4, 5, 6, 2, 1]//        [2, 3, 4, 5, 6, 1]//        [1, 2, 3, 4, 5, 6]
    }

    //插入排序
    public static void insertSort(int[] arr) {
        //遍歷所有的數位，從第二個開始和前一個比較
        for (int i = 1; i < arr.length; i++) {
            //如果當前數位比前一個數位小
            if (arr[i] < arr[i - 1]) {
                //把當前遍歷的數位存起來
                int temp = arr[i];
                //遍歷當前數位前面的數位
                int j;
                for (j = i - 1; j >= 0 && temp < arr[j]; j--) {
                    //把前一個數賦給後一個數
                    arr[j + 1] = arr[j];
                }
                //把臨時變數（外層for迴圈的當前元素）賦給不滿足條件的後一個元素
                arr[j + 1] = temp;
            }
            //列印每次排序後的結果
            System.out.println(Arrays.toString(arr));
        }
    }}

13.3 時間複雜度

• 最優時間複雜度：O(n) （升序排列，序列已經處於升序狀態）
• 最壞時間複雜度：O(n^2)
• 穩定性：穩定

在第一趟排序中，插入排序最多比較一次，第二趟最多比較兩次，依次類推，最後一趟最多比較N-1次。因此有：1+2+3+...+N-1 = N*N(N-1)/2

因為在每趟排序發現插入點之前，平均來說，只有全體資料項的一半進行比較，我們除以2得到：N*N(N-1)/4

複製的次數大致等於比較的次數，然而，一次複製與一次比較的時間消耗不同，所以相對於亂資料，這個演演算法比氣泡排序快一倍，比選擇排序略快。

與氣泡排序、選擇排序一樣，插入排序的時間複雜度仍然為O(N^2)，這三者被稱為簡單排序或者基本排序，三者都是穩定的排序演演算法。

如果待排序陣列基本有序時，插入排序的效率會更高

13.4 程式碼改進

在插入某個元素之前需要先確定該元素在有序陣列中的位置，上例的做法是對有序陣列中的元素逐個掃描，當資料量比較大的時候，這是一個很耗時間的過程，可以採用二分查詢法改進，這種排序也被稱為二分插入排序

import java.util.Arrays;public class InsertSort {
    public static void main(String[] args) {
        int[] arr = {4, 5, 6, 3, 2, 1};
        insertSort(arr);//        [4, 5, 6, 3, 2, 1]//        [4, 5, 6, 3, 2, 1]//        [3, 4, 5, 6, 2, 1]//        [2, 3, 4, 5, 6, 1]//        [1, 2, 3, 4, 5, 6]
    }

    //二分插入排序
    public static void insertSort(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            //如果新記錄小於有序序列的最大元素，則用二分法找出新紀錄在有序序列中的位置
            if (arr[i] < arr[i - 1]) {
                int temp = arr[i]; //定義temp儲存所要插入的數
                int left = 0; //最左邊的數，從str[0]開始
                int right = i - 1; //最右邊位，所要插入那個數的前一位

                while (left <= right) {
                    int middle = (left + right) / 2;   //mid中間位
                    //如果值比中間值大,讓left右移到中間下標+1
                    if (arr[middle] < temp) {
                        left = middle + 1;
                    }
                    //如果值比中間值小，讓right左移到中間下標-1
                    else {
                        right = middle - 1;
                    }
                }
                //以左下標為標準，在左位置前插入該資料，左及左後邊全部後移
                for (int j = i; j > left; j--) {
                    arr[j] = arr[j - 1];
                }
                arr[left] = temp;
            }
            System.out.println(Arrays.toString(arr));
        }
    }}

第14章 歸併排序

14.1 歸併排序概念

歸併排序（Merge Sort）是採用分治法的一個非常典型的應用。歸併排序的思想就是先遞迴分解陣列，再合併陣列。

將陣列分解最小之後，然後合併兩個有序陣列，基本思路是比較兩個陣列的最前面的數，誰小就先取誰，取了後相應的指標就往後移一位。然後再比較，直至一個陣列為空，最後把另一個陣列的剩餘部分複製過來即可。

動圖展示：

• 動圖1

• 動圖2

14.2 程式碼實現

import java.util.Arrays;public class MergeSort {
    public static void main(String[] args) {
        int[] arr = {6, 5, 3, 1, 8, 7, 2, 4};
        mergeSort(arr, 0, arr.length - 1);//        [5, 6, 3, 1, 8, 7, 2, 4]//        [5, 6, 1, 3, 8, 7, 2, 4]//        [1, 3, 5, 6, 8, 7, 2, 4]//        [1, 3, 5, 6, 7, 8, 2, 4]//        [1, 3, 5, 6, 7, 8, 2, 4]//        [1, 3, 5, 6, 2, 4, 7, 8]//        [1, 2, 3, 4, 5, 6, 7, 8]
    }

    //歸併排序
    public static void mergeSort(int[] arr, int low, int high) {
        int middle = (high + low) / 2;
        //遞迴結束
        if (low < high) {
            //處理左邊
            mergeSort(arr, low, middle);
            //處理右邊
            mergeSort(arr, middle + 1, high);
            //歸併
            merge(arr, low, middle, high);
        }
    }

    //歸併操作
    //low:開始位置，middle：分割位置，high：結束位置
    public static void merge(int[] arr, int low, int middle, int high) {
        //用於儲存歸併後的臨時陣列
        int[] temp = new int[high - low + 1];
        //記錄第一個陣列中需要遍歷的下標
        int i = low;
        //記錄第二個陣列中需要遍歷的下標
        int j = middle + 1;
        //用於記錄在臨時陣列中存放的下標
        int index = 0;
        //遍歷兩個陣列取出小的數位，放入臨時陣列中
        while (i <= middle && j <= high) {
            //第一個陣列的資料更小
            if (arr[i] <= arr[j]) {
                //把小的陣列放入臨時陣列中
                temp[index] = arr[i];
                //讓下標向後移一位
                i++;
            } else {
                temp[index] = arr[j];
                j++;
            }
            //每存入一個數位後，臨時陣列下標後移
            index++;
        }

        //上面的迴圈退出後，把剩餘的元素依次填入到temp中,以下兩個while只有一個會執行
        //前面一個陣列有多餘資料
        while (i <= middle) {
            temp[index] = arr[i];
            i++;
            index++;
        }
        //後面一個陣列有多餘資料
        while (j <= high) {
            temp[index] = arr[j];
            j++;
            index++;
        }
        //把臨時陣列中的資料重新存入原陣列
        for (int k = 0; k < temp.length; k++) {
            arr[k + low] = temp[k];
        }

        //列印每次排序後的結果
        System.out.println(Arrays.toString(arr));
    }}

14.3 時間複雜度

最優時間複雜度：O(nlogn)

最壞時間複雜度：O(nlogn)

穩定性：穩定

第15章 快速排序

15.1 快速排序概念

快速排序（Quick Sort），又稱劃分交換排序（partition-exchange sort），通過一趟排序將要排序的資料分割成獨立的兩部分，其中一部分的所有資料都比另外一部分的所有資料都要小，然後再按此方法對這兩部分資料分別進行快速排序，整個排序過程可以遞迴進行，以此達到整個資料變成有序序列。

排序步驟：

• 1、 從數列中挑出一個元素，稱為"基準"（pivot），通常選擇第一個元素
• 2、重新排序數列，所有元素比基準值小的擺放在基準前面，所有元素比基準值大的擺在基準的後面（相同的數可以到任一邊）。在這個分割區結束之後，該基準就處於數列的中間位置。這個稱為分割區（partition）操作。
• 3、遞迴地（recursive）把小於基準值元素的子數列和大於基準值元素的子數列排序。

遞迴的最底部情形，是數列的大小是零或一，也就是永遠都已經被排序好了。雖然一直遞迴下去，但是這個演演算法總會結束，因為在每次的迭代（iteration）中，它至少會把一個元素擺到它最後的位置去。

動圖展示：

• 動圖1

• 動圖2：

靜圖分析：

15.2 程式碼實現

import java.util.Arrays;public class QuickSort {
    public static void main(String[] args) {
        int[] arr = {30, 40, 60, 10, 20, 50};
        quickSort(arr, 0, arr.length - 1);//        [20, 10, 30, 60, 40, 50]//        [10, 20, 30, 60, 40, 50]//        [10, 20, 30, 60, 40, 50]//        [10, 20, 30, 50, 40, 60]//        [10, 20, 30, 40, 50, 60]//        [10, 20, 30, 40, 50, 60]
    }

    //快速排序
    public static void quickSort(int[] arr, int start, int end) {
        //遞迴結束的標記
        if (start < end) {
            //把陣列中第0個數位作為標準數
            int stard = arr[start];
            //記錄需要排序的下標
            int low = start;
            int high = end;
            //迴圈找比標準數大的數和標準數小的數
            while (low < high) {
                //如果右邊數位比標準數大，下標向前移
                while (low < high && arr[high] >= stard) {
                    high--;
                }
                //右邊數位比標準數小，使用右邊的數替換左邊的數
                arr[low] = arr[high];
                //如果左邊數位比標準數小
                while (low < high && arr[low] <= stard) {
                    low++;
                }
                //左邊數位比標準數大，使用左邊的數替換右邊的數
                arr[high] = arr[low];
            }
            //把標準數賦給低所在的位置的元素
            arr[low] = stard;
            //列印每次排序後的結果
            System.out.println(Arrays.toString(arr));

            //遞迴處理所有標準數左邊的數位（含標準數）
            quickSort(arr, start, low);
            //遞迴處理所有標準數右邊的數位
            quickSort(arr, low + 1, end);
        }
    }}

15.3 時間複雜度

• 最優時間複雜度：O(nlogn)
• 最壞時間複雜度：O(n^2)
• 穩定性：不穩定

從一開始快速排序平均需要花費O(n log n)時間的描述並不明顯。但是不難觀察到的是分割區運算，陣列的元素都會在每次迴圈中走訪過一次，使用O(n)的時間。在使用結合（concatenation）的版本中，這項運算也是O(n)。

在最好的情況，每次我們執行一次分割區，我們會把一個數列分為兩個幾近相等的片段。這個意思就是每次遞迴呼叫處理一半大小的數列。因此，在到達大小為一的數列前，我們只要作log n次巢狀的呼叫。這個意思就是呼叫樹的深度是O(log n)。但是在同一層次結構的兩個程式呼叫中，不會處理到原來數列的相同部分；因此，程式呼叫的每一層次結構總共全部僅需要O(n)的時間（每個呼叫有某些共同的額外耗費，但是因為在每一層次結構僅僅只有O(n)個呼叫，這些被歸納在O(n)係數中）。結果是這個演演算法僅需使用O(n log n)時間。

第16章 希爾排序

16.1 希爾排序概念

希爾排序（Shell Sort）是插入排序的一種。也稱縮小增量排序，是直接插入排序演演算法的一種更高效的改進版本。希爾排序是非穩定排序演演算法。該方法因DL．Shell於1959年提出而得名。 希爾排序是把記錄按下標的一定增量分組，對每組使用直接插入排序演演算法排序；隨著增量逐漸減少，每組包含的關鍵詞越來越多，當增量減至1時，整個檔案恰被分成一組，演演算法便終止

動圖展示：

靜圖分析：

16.2 程式碼實現

import java.util.Arrays;public class ShellSort {
    public static void main(String[] args) {
        int[] arr = {8, 9, 1, 7, 2, 3, 5, 4, 6, 0};
        shellSort(arr);//        [3, 5, 1, 6, 0, 8, 9, 4, 7, 2]//        [0, 2, 1, 4, 3, 5, 7, 6, 9, 8]//        [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
    }

    //希爾排序
    public static void shellSort(int[] arr) {
        //遍歷所有的步長
        for (int gap = arr.length / 2; gap > 0; gap = gap / 2) {
            //遍歷所有的元素
            for (int i = gap; i < arr.length; i++) {
                //遍歷本組中所有元素
                for (int j = i - gap; j >= 0; j -= gap) {
                    //如果當前元素大於加上步長後的那個元素
                    if (arr[j] > arr[j + gap]) {
                        int temp = arr[j];
                        arr[j] = arr[j + gap];
                        arr[j + gap] = temp;
                    }
                }
            }
            //列印每次排序後的結果
            System.out.println(Arrays.toString(arr));
        }
    }}

16.3 時間複雜度

• 最優時間複雜度：根據步長序列的不同而不同
• 最壞時間複雜度：O(n^2)
• 穩定性：不穩定

希爾排序不像其他時間複雜度為O(N log2N)的排序演演算法那麼快，但是比選擇排序和插入排序這種時間複雜度為O(N2)的排序演演算法還是要快得多，而且非常容易實現。它在最壞情況下的執行效率和在平均情況下的執行效率相比不會降低多少，而快速排序除非採取特殊措施，否則在最壞情況下的執行效率變得非常差。

迄今為止，還無法從理論上精準地分析希爾排序的效率，有各種各樣基於試驗的評估，估計它的時間級介於O(N^3/2)與 O(N^7/6)之間。我們可以認為希爾排序的平均時間複雜度為o(n^1.3)。

第17章 堆排序

17.1 堆排序概述

堆排序（Heap Sort）是指利用堆這種資料結構所設計的一種排序演演算法。堆積是一個近似完全二元樹的結構，每個結點的值都大於或等於其左右孩子結點的值，稱為大頂堆；或者每個結點的值都小於或等於其左右孩子結點的值，稱為小頂堆。如下圖：

同時，我們對堆中的結點按層進行編號，將這種邏輯結構對映到陣列中就是下面這個樣子
該陣列從邏輯上講就是一個堆結構，我們用簡單的公式來描述一下堆的定義就是：

• 大頂堆：arr[i] >= arr[2i+1] && arr[i] >= arr[2i+2]

• 小頂堆：arr[i] <= arr[2i+1] && arr[i] <= arr[2i+2]

步驟一 構造初始堆。將給定無序序列構造成一個大頂堆（一般升序採用大頂堆，降序採用小頂堆)

1）假設給定無序序列結構如下

2）此時我們從最後一個非葉子結點開始（葉結點自然不用調整，第一個非葉子結點 arr.length/2-1=5/2-1=1，也就是下面的6結點），從左至右，從下至上進行調整

3）找到第二個非葉節點4，由於[4,9,8]中9元素最大，4和9交換
4）這時，交換導致了子根[4,5,6]結構混亂，繼續調整，[4,5,6]中6最大，交換4和6。
此時，我們就將一個無需序列構造成了一個大頂堆

步驟二 將堆頂元素與末尾元素進行交換，使末尾元素最大。然後繼續調整堆，再將堆頂元素與末尾元素交換，得到第二大元素。如此反覆進行交換、重建、交換

1）將堆頂元素9和末尾元素4進行交換，9就不用繼續排序了

2）重新調整結構，使其繼續構建大頂堆（9除外）

3）再將堆頂元素8與末尾元素5進行交換，得到第二大元素8.

步驟三 後續過程，繼續進行調整，交換，如此反覆進行，最終使得整個序列有序

排序思路：

• 將無需序列構建成一個堆，根據升序降序需求選擇大頂堆或小頂堆;

• 將堆頂元素與末尾元素交換，將最大元素"沉"到陣列末端;

• 重新調整結構，使其滿足堆定義，然後繼續交換堆頂元素與當前末尾元素，反覆執行調整+交換步驟，直到整個序列有序

動圖展示：

17.2 程式碼實現

import java.util.Arrays;public class HeapSort {
    public static void main(String[] args) {
        int[] arr = {4, 6, 8, 5, 9};
        heapSort(arr);//        [4, 6, 8, 5, 9]//        [4, 9, 8, 5, 6]//        [4, 9, 8, 5, 6]//        [9, 6, 8, 5, 4]//        [9, 6, 8, 5, 4]//        [9, 6, 8, 5, 4]//        [8, 6, 4, 5, 9]//        [8, 6, 4, 5, 9]//        [6, 5, 4, 8, 9]//        [6, 5, 4, 8, 9]//        [5, 4, 6, 8, 9]//        [5, 4, 6, 8, 9]//        [4, 5, 6, 8, 9]
    }

    //堆排序
    public static void heapSort(int[] arr) {
        //開始位置是最後一個非葉子節點（最後一個節點的父節點）
        int start = (arr.length - 1) / 2;
        //迴圈調整為大頂堆
        for (int i = start; i >= 0; i--) {
            maxHeap(arr, arr.length, i);
        }
        //先把陣列中第0個和堆中最後一個交換位置
        for (int i = arr.length - 1; i > 0; i--) {
            int temp = arr[0];
            arr[0] = arr[i];
            arr[i] = temp;
            //再把前面的處理為大頂堆
            maxHeap(arr, i, 0);
        }
    }

    //陣列轉大頂堆,size:調整多少（從最後一個向前減），index:調整哪一個（最後一個非葉子節點）
    public static void maxHeap(int[] arr, int size, int index) {
        //左子節點
        int leftNode = 2 * index + 1;
        //右子節點
        int rightNode = 2 * index + 2;
        //先設當前為最大節點
        int max = index;
        //和兩個子節點分別對比，找出最大的節點
        if (leftNode < size && arr[leftNode] > arr[max]) {
            max = leftNode;
        }
        if (rightNode < size && arr[rightNode] > arr[max]) {
            max = rightNode;
        }

        //交換位置
        if (max != index) {
            int temp = arr[index];
            arr[index] = arr[max];
            arr[max] = temp;
            //交換位置後，可能會破壞之前排好的堆，所以之間排好的堆需要重新調整
            maxHeap(arr, size, max);
        }
        //列印每次排序後的結果
        System.out.println(Arrays.toString(arr));
    }}

17.3 時間複雜度

• 最優時間複雜度：o(nlogn)
• 最壞時間複雜度：o(nlogn)
• 穩定性：不穩定

它的執行時間主要是消耗在初始構建堆和在重建堆時的反覆篩選上。

在構建堆的過程中，因為我們是完全二元樹從最下層最右邊的非終端結點開始構建，將它與其孩子進行比較和若有必要的互換，對於每個非終端結點來說，其實最多進行兩次比較和互換操作，因此整個構建堆的時間複雜度為O(n)。

在正式排序時，第i次取堆頂記錄重建堆需要用O(logi)的時間（完全二元樹的某個結點到根結點的距離為log2i＋1），並且需要取n-1次堆頂記錄，因此，重建堆的時間複雜度為O(nlogn)。

所以總體來說，堆排序的時間複雜度為O(nlogn)。由於堆排序對原始記錄的排序狀態並不敏感，因此它無論是最好、最壞和平均時間複雜度均為O(nlogn)。這在效能上顯然要遠遠好過於冒泡、簡單選擇、直接插入的O(n2)的時間複雜度了。

空間複雜度上，它只有一個用來交換的暫存單元，也非常的不錯。不過由於記錄的比較與交換是跳躍式進行，因此堆排序是一種不穩定的排序方法。

第18章 計數排序

18.1 計數排序概念

計數排序（Counting Sort）不是基於比較的排序演演算法，其核心在於將輸入的資料值轉化為鍵儲存在額外開闢的陣列空間中。 作為一種線性時間複雜度的排序，計數排序要求輸入的資料必須是有確定範圍的整數。

排序步驟：

• 找出待排序的陣列中最大和最小的元素；
• 統計陣列中每個值為i的元素出現的次數，存入陣列C的第i項；
• 對所有的計數累加（從C中的第一個元素開始，每一項和前一項相加）；
• 反向填充目標陣列：將每個元素i放在新陣列的第C(i)項，每放一個元素就將C(i)減去1

動圖展示：

18.2 程式碼實現

import java.util.Arrays;public class CountingSort {
    public static void main(String[] args) {
        //測試
        int[] arr = {1, 4, 6, 7, 5, 4, 3, 2, 1, 4, 5, 10, 9, 10, 3};
        sortCount(arr);
        System.out.println(Arrays.toString(arr));//        [1, 1, 2, 3, 3, 4, 4, 4, 5, 5, 6, 7, 9, 10, 10]
    }

    //計數排序
    public static void sortCount(int[] arr) {
        //一：求取最大值和最小值，計算中間陣列的長度：
        int max = arr[0];
        int min = arr[0];
        int len = arr.length;
        for (int i : arr) {
            if (i > max) {
                max = i;
            }
            if (i < min) {
                min = i;
            }
        }
        //二、有了最大值和最小值能夠確定中間陣列的長度（中間陣列是用來記錄原始資料中每個值出現的頻率）
        int[] temp = new int[max - min + 1];
        //三.迴圈遍歷舊陣列計數排序: 就是統計原始陣列值出現的頻率到中間陣列temp中
        for (int i = 0; i < len; i++) {
            temp[arr[i] - min] += 1;
        }
        //四、遍歷輸出
        //先回圈每一個元素  在計數排序器的下標中
        for (int i = 0, index = 0; i < temp.length; i++) {
            int item = temp[i];
            迴圈出現的次數
            while (item-- != 0) {
                //以為原來減少了min現在加上min，值就變成了原來的值
                arr[index++] = i + min;
            }
        }
    }}

18.3 時間複雜度

• 最優時間複雜度：o(n+k)
• 最壞時間複雜度：o(n+k)
• 穩定性：不穩定

計數排序是一個穩定的排序演演算法。當輸入的元素是 n 個 0到 k 之間的整數時，時間複雜度是O(n+k)，空間複雜度也是O(n+k)，其排序速度快於任何比較排序演演算法。當k不是很大並且序列比較集中時，計數排序是一個很有效的排序演演算法

第19章 桶排序

19.1 桶排序概念

桶排序 （Bucket sort）或所謂的箱排序，是一個排序演演算法，工作的原理是將陣列分到有限數量的桶裡。每個桶再個別排序（有可能再使用別的排序演演算法或是以遞迴方式繼續使用桶排序進行排序），最後依次把各個桶中的記錄列出來記得到有序序列。桶排序是鴿巢排序的一種歸納結果。當要被排序的陣列內的數值是均勻分配的時候，桶排序使用線性時間 o(n)。但桶排序並不是比較排序，他不受到O(n log n)下限的影響。

排序步驟：

• 設定一個定量的陣列當作空桶；
• 遍歷輸入資料，並且把資料一個一個放到對應的桶裡去；
• 對每個不是空的桶進行排序；
• 從不是空的桶裡把排好序的資料拼接起來

動圖展示：

靜圖展示：

19.2 程式碼實現

package sort;import java.util.ArrayList;import java.util.Collections;public class BucketSort {

    public static void main(String[] args) {
        int[] arr = {29, 25, 3, 49, 9, 37, 21, 43};
        bucketSort(arr);
        //分桶後結果為:[[3, 9], [], [21, 25], [29], [37], [43, 49]]
    }

    public static void bucketSort(int[] arr) {
        // 大的當小的，小的當大的
        int max = Integer.MIN_VALUE;
        int min = Integer.MAX_VALUE;
        // 找出最小最大值
        for (int i=0, len=arr.length; i<len; i++) {
            max = Math.max(max, arr[i]);
            min = Math.min(min, arr[i]);
        }
        // 建立初始的桶
        int bucketNum = (max - min)/arr.length + 1;
        ArrayList<ArrayList<Integer>> bucketArr = new ArrayList<>(bucketNum);

        // 這一步是不可缺少的，上面的初始化只初始化了一維列表。二維列表需額外初始化
        for (int i=0; i<bucketNum; i++) {
            bucketArr.add(new ArrayList<>());
        }
        for (int i=0, len=arr.length; i<len; i++) {
            int num = (arr[i] - min)/arr.length;    //相同的商在同一個桶中
            bucketArr.get(num).add(arr[i]);     //根據商的不同，放入不同的桶
        }

        for (int i=0; i<bucketArr.size(); i++) {    //同一桶內，自己排序
            Collections.sort(bucketArr.get(i));
        }
        System.out.println("分桶後結果為:"+bucketArr.toString());
    }}

19.3 時間複雜度

• 最優時間複雜度：o(n)
• 最壞時間複雜度：o(n^2)
• 穩定性：穩定

對於桶排序來說，分配過程的時間是O(n)；收集過程的時間為O(k) （採用連結串列來儲存輸入的待排序記錄）。因此，桶排序的時間為O(n+k)。若桶個數m的數量級為O(n)，則桶排序的時間是線性的，最優即O(n)。

前面說的幾大排序演演算法 ，大部分時間複雜度都是O(n2)，也有部分排序演演算法時間複雜度是O(nlogn)。而桶式排序卻能實現O(n)的時間複雜度。但桶排序的缺點是：首先是空間複雜度比較高，需要的額外開銷大。排序有兩個陣列的空間開銷，一個存放待排序陣列，一個就是所謂的桶，比如待排序值是從0到m-1，那就需要m個桶，這個桶陣列就要至少m個空間。其次待排序的元素都要在一定的範圍內等等。

第20章 基數排序

20.1 基數排序概念

基數排序（Radix Sort）是按照低位先排序，然後收集；再按照高位排序，然後再收集；依次類推，直到最高位。有時候有些屬性是有優先順序順序的，先按低優先順序排序，再按高優先順序排序。最後的次序就是高優先順序高的在前，高優先順序相同的低優先順序高的在前

排序步驟：

• 取得陣列中的最大數，並取得位數；
• arr為原始陣列，從最低位開始取每個位組成radix陣列；
• 對radix進行計數排序（利用計數排序適用於小範圍數的特點）

動圖展示：

靜圖分析：

20.2 程式碼實現

import java.util.Arrays;public class RadixSort {
    public static void main(String[] args) {
        int[] arr = {4, 32, 457, 16, 28, 64};
        radixSort(arr);//        [32, 4, 64, 16, 457, 28]//        [4, 16, 28, 32, 457, 64]//        [4, 16, 28, 32, 64, 457]
    }

    //基數排序
    public static void radixSort(int[] arr) {
        // 定義臨時二維陣列表示十個桶
        int[][] temp = new int[10][arr.length];
        // 定義一個一維陣列，用於記錄在temp中相應的陣列中存放數位的數量
        int[] counts = new int[10];
        //存陣列中最大的數位
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length; i++) {
            if (arr[i] > max) {
                max = arr[i];
            }
        }
        //計算最大數位是幾位數（才能知道排序次數）
        int maxLength = (max + "").length();
        //根據最大長度的數決定比較的次數
        for (int i = 0, n = 1; i < maxLength; i++, n *= 10) {
            //把每一個數位分別計算餘數
            for (int j = 0; j < arr.length; j++) {
                //計算餘數
                int ys = arr[j] / n % 10;
                //把當前遍歷的資料放入指定的陣列中
                temp[ys][counts[ys]] = arr[j];
                //記錄數量
                counts[ys]++;
            }
            //記錄取的元素需要放的位置
            int index = 0;
            //把數位取出來
            for (int k = 0; k < counts.length; k++) {
                //記錄數量的陣列中，當前餘數記錄的數量不為0才取
                if (counts[k] != 0) {
                    //迴圈取出元素
                    for (int l = 0; l < counts[k]; l++) {
                        //取出元素
                        arr[index] = temp[k][l];
                        //記錄下一個位置
                        index++;
                    }
                    //把數量置為0
                    counts[k] = 0;
                }
            }
            //列印每次排序後的結果
            System.out.println(Arrays.toString(arr));
        }
    }}

20.3 時間複雜度

• 最優時間複雜度：O(n^k)
• 最壞時間複雜度：O(n^k)
• 穩定性：穩定

初看起來，基數排序的執行效率似乎好的讓人無法相信，所有要做的只是把原始資料項從陣列複製到連結串列，然後再複製回去。如果有10個資料項，則有20次複製，對每一位重複一次這個過程。假設對5位的數位排序，就需要20 * 5=100次複製。

*如果有100個資料項，那麼就有200 * 5=1000次複製。複製的次數與資料項的個數成正比，即O(n)。這是我們看到的效率最高的排序演演算法。

不幸的是，資料項越多，就需要更長的關鍵字，如果資料項增加10倍，那麼關鍵字必須增加一位（多一輪排序）。複製的次數和資料項的個數與關鍵字長度成正比，可以認為關鍵字長度是N的對數。因此在大多數情況下，基數排序的執行效率倒退為O(N*logN)，和快速排序差不多

推薦學習：《》

以上就是圖文詳解Java資料結構與演演算法的詳細內容，更多請關注TW511.COM其它相關文章！