二叉樹、排序算法與結構圖

二叉樹、排序算法與數據庫

二叉樹

二叉樹的性質

節點數與深度的關系：深度為 $k$ 的二叉樹，最多有 $2^k - 1$ 個節點。例如，深度為 $3$ 的二叉樹，最多有 $2^3 - 1 = 7$ 個節點。
葉子節點與度為2節點的關系：對于任意一棵二叉樹，如果其葉子節點數為 $n_0$ ，度為 $2$ 的節點數為 $n_2$ ，則 $n_0 = n_2 + 1$

      根節點/    \左子樹   右子樹/  \    /  \
節點 節點 節點 節點

二叉樹的存儲結構

順序存儲結構：對于完全二叉樹，可以使用數組來存儲節點。將根節點存儲在數組的第一個位置，然后按照從上到下、從左到右的順序依次存儲其他節點。這樣可以通過節點的下標來快速訪問其左右子節點。例如，對于節點 $i$ ，其左子節點的下標為 $2 i + 1$ ，右子節點的下標為 $2 i + 2$ 。
鏈式存儲結構：通常使用鏈表來表示二叉樹的節點。每個節點包含三個部分：數據域、左指針域和右指針域。左指針域指向該節點的左子節點，右指針域指向該節點的右子節點。這種存儲結構可以方便地進行節點的插入和刪除操作。

二叉樹的遍歷方式

前序遍歷：先訪問根節點，然后遞歸地遍歷左子樹，最后遞歸地遍歷右子樹。例如，對于二叉樹 $A (B (D, E), C (F))$
前序遍歷的結果為 $A B D ECF$
中序遍歷：先遞歸地遍歷左子樹，然后訪問根節點，最后遞歸地遍歷右子樹。對于上述二叉樹，中序遍歷的結果為 $D BE A CF$
后序遍歷：先遞歸地遍歷左子樹，然后遞歸地遍歷右子樹，最后訪問根節點。對于上述二叉樹，后序遍歷的結果為 $D EBFC A$
層序遍歷：按照從上到下、從左到右的順序依次訪問二叉樹的每一層節點。對于上述二叉樹，層序遍歷的結果為 $A BC D EF$

$\text{題目}$
設二叉樹的中序序列為 $BC D A$ ,后序序列為 $D CB A$ ,則前序序列為： $\textbf{（\qquad）}$

$\text{解析}$
首先，根據后序可以得到根節點：A
其次，根據中序可以得到左子樹和右子樹：BCD 空
然后再根據后序確定左子樹的結構:根節點為：B,D在左，C在右或者D在上，C在下。
再看，中序發現C跑中間去了，所以是第二種情況

因此，答案為： $A BC D$

排序算法

排序算法是計算機科學中用于將一組數據按照特定順序（如升序或降序）排列的算法。

冒泡排序（Bubble Sort）：
- 基本思想：重復地走訪要排序的數列，一次比較兩個數據元素，如果順序不對則進行交換，并一直重復這樣的走訪操作，直到沒有要交換的數據元素為止。
- 示例代碼（Python）：

def bubble_sort(arr):n = len(arr)for i in range(n):for j in range(0, n - i - 1):if arr[j] > arr[j + 1]:arr[j], arr[j + 1] = arr[j + 1], arr[j]return arr

時間復雜度：平均和最壞情況下為 $O(n^2)$ ，最好情況（數組已經有序）下為 $O (n)$ 。
空間復雜度： $O (1)$ ，因為只需要幾個額外的變量來進行交換操作，不隨數據規模增長。
穩定性：穩定，相同元素的相對順序在排序前后不會改變。

選擇排序（Selection Sort）：
- 基本思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再從剩余未排序元素中繼續尋找最小（大）元素，然后放到已排序序列的末尾。以此類推，直到所有元素均排序完畢。
- 示例代碼（Python）：

def selection_sort(arr):n = len(arr)for i in range(n):min_index = ifor j in range(i + 1, n):if arr[j] < arr[min_index]:min_index = jarr[i], arr[min_index] = arr[min_index], arr[i]return arr

時間復雜度：平均和最壞情況下為 $O(n^2)$ ，最好情況也是 $O(n^2)$ ，因為每次都要遍歷剩余未排序元素找最小（大）值。
空間復雜度： $O (1)$ 。
穩定性：不穩定，例如序列 [5, 5, 3]，在排序過程中，兩個 5 的相對順序可能會改變。

插入排序（Insertion Sort）：
- 基本思想：將一個數據插入到已經排好序的數組中的適當位置，從而得到一個新的、個數加一的有序數組。初始時把第一個元素看作已排序序列，然后依次將后面的元素插入到合適位置。
- 示例代碼（Python）：

def insertion_sort(arr):for i in range(1, len(arr)):key = arr[i]j = i - 1while j >= 0 and arr[j] > key:arr[j + 1] = arr[j]j = j - 1arr[j + 1] = keyreturn arr

時間復雜度：平均和最壞情況下為 $O(n^2)$ ，最好情況（數組已經有序）下為 $O (n)$ 。
空間復雜度： $O (1)$ 。
穩定性：穩定，在插入過程中，相同元素的相對順序不會改變。

快速排序（Quick Sort）：
- 基本思想：通過一趟排序將待排記錄分割成獨立的兩部分，其中一部分記錄的關鍵字均比另一部分的關鍵字小，則可分別對這兩部分記錄繼續進行排序，以達到整個序列有序。
- 示例代碼（Python）：

def quick_sort(arr):if len(arr) <= 1:return arrpivot = arr[len(arr) // 2]left = [x for x in arr if x < pivot]middle = [x for x in arr if x == pivot]right = [x for x in arr if x > pivot]return quick_sort(left) + middle + quick_sort(right)

時間復雜度：平均情況下為 $\log n)$ ，最壞情況（如數組已經有序且每次選擇的基準值都不合適）下為 $O(n^2)$ 。
空間復雜度：平均情況下為 $O(\log n)$ ，最壞情況（遞歸深度達到 $n$ 層)下為 $O (n)$ 。
穩定性：不穩定，因為在劃分過程中，相同元素的相對順序可能會改變。

歸并排序（Merge Sort）：
- 基本思想：采用分治法，將一個序列分成兩個長度相等的子序列，分別對這兩個子序列進行排序，然后將排好序的子序列合并成一個最終的有序序列。
- 示例代碼（Python）：

def merge_sort(arr):if len(arr) <= 1:return arrmid = len(arr) // 2left_half = merge_sort(arr[:mid])right_half = merge_sort(arr[mid:])return merge(left_half, right_half)def merge(left, right):result = []i = j = 0while i < len(left) and j < len(right):if left[i] < right[j]:result.append(left[i])i += 1else:result.append(right[j])j += 1result.extend(left[i:])result.extend(right[j:])return result

時間復雜度：平均、最壞和最好情況下均為 $\log n)$ ，因為每次都是將序列分成兩部分，共分 $\log n$ 層，每層合并操作的時間復雜度為 $O (n)$ 。
空間復雜度： $O (n)$ ，因為在合并過程中需要額外的空間來存儲臨時序列。
穩定性：穩定，在合并過程中，相同元素的相對順序不會改變。

堆排序（Heap Sort）：
- 基本思想：利用堆這種數據結構所設計的一種排序算法。堆是一個近似完全二叉樹的結構，并同時滿足堆積的性質：即子節點的鍵值或索引總是小于（或者大于）它的父節點。先將待排序序列構建成一個大頂堆（或小頂堆），此時，整個序列的最大值（或最小值）就是堆頂的根節點。將其與末尾元素進行交換，此時末尾就為最大值（或最小值）。然后將剩余 $n ? 1$ 個元素重新構造成一個堆，這樣會得到 $n$ 個元素的次大值（或次小值）。如此反復執行，便能得到一個有序序列。
- 示例代碼（Python）：

def heapify(arr, n, i):largest = il = 2 * i + 1r = 2 * i + 2if l < n and arr[i] < arr[l]:largest = lif r < n and arr[largest] < arr[r]:largest = rif largest != i:arr[i], arr[largest] = arr[largest], arr[i]heapify(arr, n, largest)def heap_sort(arr):n = len(arr)for i in range(n // 2 - 1, -1, -1):heapify(arr, n, i)for i in range(n - 1, 0, -1):arr[i], arr[0] = arr[0], arr[i]heapify(arr, i, 0)return arr

時間復雜度：平均和最壞情況下為 $\log n)$ ，因為構建堆的時間復雜度為 $O (n)$ ，調整堆的時間復雜度為 $O(\log n)$ ，共進行 $n ? 1$ 次調整。
空間復雜度： $O (1)$ ，只需要一些常數級別的額外空間。
穩定性：不穩定，在調整堆的過程中，相同元素的相對順序可能會改變。

排序算法	平均時間復雜度	最壞時間復雜度	最好時間復雜度	空間復雜度	穩定性	基本思想
冒泡排序	$O(n^2)$	$O(n^2)$	$O (n)$	$O (1)$	穩定	重復走訪數列，比較相鄰元素，若順序不對則交換，直到沒有元素需要交換
選擇排序	$O(n^2)$	$O(n^2)$	$O(n^2)$	$O (1)$	不穩定	從未排序序列中找最小（大）元素，放到已排序序列末尾，重復此過程
插入排序	$O(n^2)$	$O(n^2)$	$O (n)$	$O (1)$	穩定	將數據插入到已排序數組的合適位置，初始把第一個元素看作已排序序列
快速排序	$\log n)$	$O(n^2)$	$\log n)$	平均 $O(\log n)$ ，最壞 $O (n)$	不穩定	選擇基準值，將序列分成兩部分，分別對兩部分遞歸排序
歸并排序	$\log n)$	$\log n)$	$\log n)$	$O (n)$	穩定	采用分治法，將序列分成子序列排序后合并成最終有序序列
堆排序	$\log n)$	$\log n)$	$\log n)$	$O (1)$	不穩定	先構建堆，將堆頂元素與末尾元素交換，調整堆，重復此過程

以下是幾種常見排序算法對長度為(n)的數組排序最多需要的步驟公式：

排序算法	最多步驟公式
冒泡排序	$\frac{n(n - 1)}{2}$
選擇排序	$\frac{n(n - 1)}{2}+n - 1$
插入排序	$n (n ? 1)$
快速排序	$1)\div2$ （最壞情況）
歸并排序	$n\log_2n$
堆排序	$n\log_2n + n$