二叉树、排序算法与结构图

二叉树、排序算法与数据库

二叉树

二叉树的性质

节点数与深度的关系：深度为 $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$