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

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

二叉树

二叉树的性质

• 节点数与深度的关系：深度为$k$的二叉树，最多有$2^k-1$个节点。例如，深度为$3$的二叉树，最多有$2^3-1=7$个节点。
• 叶子节点与度为2节点的关系：对于任意一棵二叉树，如果其叶子节点数为$n_0$，度为$2$的节点数为$n_2$，则$$n_0=n_2+1$$

      根节点
     /    \
  左子树   右子树
  /  \    /  \
节点 节点 节点 节点

二叉树的存储结构

• 顺序存储结构：对于完全二叉树，可以使用数组来存储节点。将根节点存储在数组的第一个位置，然后按照从上到下、从左到右的顺序依次存储其他节点。这样可以通过节点的下标来快速访问其左右子节点。例如，对于节点$i$，其左子节点的下标为$2i+1$，右子节点的下标为$2i+2$。
• 链式存储结构：通常使用链表来表示二叉树的节点。每个节点包含三个部分：数据域、左指针域和右指针域。左指针域指向该节点的左子节点，右指针域指向该节点的右子节点。这种存储结构可以方便地进行节点的插入和删除操作。

二叉树的遍历方式

• 前序遍历：先访问根节点，然后递归地遍历左子树，最后递归地遍历右子树。例如，对于二叉树$$A(B(D,E),C(F))$$
  前序遍历的结果为$$ABDECF$$
• 中序遍历：先递归地遍历左子树，然后访问根节点，最后递归地遍历右子树。对于上述二叉树，中序遍历的结果为$$DBEACF$$
• 后序遍历：先递归地遍历左子树，然后递归地遍历右子树，最后访问根节点。对于上述二叉树，后序遍历的结果为$$DEBFCA$$
• 层序遍历：按照从上到下、从左到右的顺序依次访问二叉树的每一层节点。对于上述二叉树，层序遍历的结果为$$ABCDEF$$

$$\text{题目}$$
设二叉树的中序序列为$BCDA$,后序序列为$DCBA$,则前序序列为：$\text{（）}$

$$\text{解析}$$
首先，根据后序可以得到根节点：A
其次，根据中序可以得到左子树和右子树：BCD 空
然后再根据后序确定左子树的结构:根节点为：B,D在左，C在右或者D在上，C在下。
再看，中序发现C跑中间去了，所以是第二种情况

因此，答案为：$ABCD$

排序算法

排序算法是计算机科学中用于将一组数据按照特定顺序（如升序或降序）排列的算法。

1. 冒泡排序（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)$，因为只需要几个额外的变量来进行交换操作，不随数据规模增长。
• 稳定性：稳定，相同元素的相对顺序在排序前后不会改变。

2. 选择排序（Selection Sort）：
   • 基本思想：首先在未排序序列中找到最小（大）元素，存放到排序序列的起始位置，然后，再从剩余未排序元素中继续寻找最小（大）元素，然后放到已排序序列的末尾。以此类推，直到所有元素均排序完毕。
   • 示例代码（Python）：

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

• 时间复杂度：平均和最坏情况下为 $O(n^2)$，最好情况也是 $O(n^2)$，因为每次都要遍历剩余未排序元素找最小（大）值。
• 空间复杂度：$O(1)$。
• 稳定性：不稳定，例如序列 [5, 5, 3]，在排序过程中，两个 5 的相对顺序可能会改变。

3. 插入排序（Insertion Sort）：
   • 基本思想：将一个数据插入到已经排好序的数组中的适当位置，从而得到一个新的、个数加一的有序数组。初始时把第一个元素看作已排序序列，然后依次将后面的元素插入到合适位置。
   • 示例代码（Python）：

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

• 时间复杂度：平均和最坏情况下为 $O(n^2)$，最好情况（数组已经有序）下为 $O(n)$。
• 空间复杂度：$O(1)$。
• 稳定性：稳定，在插入过程中，相同元素的相对顺序不会改变。

4. 快速排序（Quick Sort）：
   • 基本思想：通过一趟排序将待排记录分割成独立的两部分，其中一部分记录的关键字均比另一部分的关键字小，则可分别对这两部分记录继续进行排序，以达到整个序列有序。
   • 示例代码（Python）：

def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    pivot = 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)

• 时间复杂度：平均情况下为 $O(n\log n)$，最坏情况（如数组已经有序且每次选择的基准值都不合适）下为 $O(n^2)$。
• 空间复杂度：平均情况下为 $O(\log n)$，最坏情况（递归深度达到 $n$ 层)下为$O(n)$。
• 稳定性：不稳定，因为在划分过程中，相同元素的相对顺序可能会改变。

5. 归并排序（Merge Sort）：
   • 基本思想：采用分治法，将一个序列分成两个长度相等的子序列，分别对这两个子序列进行排序，然后将排好序的子序列合并成一个最终的有序序列。
   • 示例代码（Python）：

def merge_sort(arr):
    if len(arr) <= 1:
        return arr
    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])
    return merge(left_half, right_half)

def merge(left, right):
    result = []
    i = j = 0
    while i < len(left) and j < len(right):
        if left[i] < right[j]:
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
    result.extend(left[i:])
    result.extend(right[j:])
    return result

• 时间复杂度：平均、最坏和最好情况下均为 $O(n\log n)$，因为每次都是将序列分成两部分，共分 $\log n$ 层，每层合并操作的时间复杂度为 $O(n)$。
• 空间复杂度：$O(n)$，因为在合并过程中需要额外的空间来存储临时序列。
• 稳定性：稳定，在合并过程中，相同元素的相对顺序不会改变。

6. 堆排序（Heap Sort）：
   • 基本思想：利用堆这种数据结构所设计的一种排序算法。堆是一个近似完全二叉树的结构，并同时满足堆积的性质：即子节点的键值或索引总是小于（或者大于）它的父节点。先将待排序序列构建成一个大顶堆（或小顶堆），此时，整个序列的最大值（或最小值）就是堆顶的根节点。将其与末尾元素进行交换，此时末尾就为最大值（或最小值）。然后将剩余 $n-1$ 个元素重新构造成一个堆，这样会得到 $n$个元素的次大值（或次小值）。如此反复执行，便能得到一个有序序列。
   • 示例代码（Python）：

def heapify(arr, n, i):
    largest = i
    l = 2 * i + 1
    r = 2 * i + 2

    if l < n and arr[i] < arr[l]:
        largest = l

    if r < n and arr[largest] < arr[r]:
        largest = r

    if 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

• 时间复杂度：平均和最坏情况下为 $O(n\log n)$，因为构建堆的时间复杂度为 $O(n)$，调整堆的时间复杂度为 $O(\log n)$，共进行 $n-1$ 次调整。
• 空间复杂度：$O(1)$，只需要一些常数级别的额外空间。
• 稳定性：不稳定，在调整堆的过程中，相同元素的相对顺序可能会改变。

排序算法	平均时间复杂度	最坏时间复杂度	最好时间复杂度	空间复杂度	稳定性	基本思想
冒泡排序	$O(n^2)$	$O(n^2)$	$O(n)$	$O(1)$	稳定	重复走访数列，比较相邻元素，若顺序不对则交换，直到没有元素需要交换
选择排序	相关文章 二叉树、排序算法与结构图 二叉树相关算法实现：判断子树与单值二叉树- 一、判断一棵树是否为另一棵树的子树   排序算法中各种与初始序列无关 算法与数据结构之树与二叉树 PTA数据结构与算法题目集(中文) 7-37 模拟EXCEL排序 (25 分) 数据结构与算法之排序算法-(计数,桶,基数排序)-三、基数排序 数据结构与算法——排序 数据结构与算法之PHP排序算法（插入排序） 常用排序与查找算法大全 Python 排序与查找算法 上一篇：uniapp下拉框组件 下一篇：关于uniapp 小程序的下拉框搜索选择 推荐文章 SpringBoot集成CAS客户端 Java工具--滑块验证码生成 Springboot+poi上传并处理百万级数据EXCEL Restful API实践（三）RestTemplate使用详解 【代码随想录训练营】【Day01】第一章｜数组｜数组理论基础｜704.二分查找｜27.移除元素 二叉树的递归遍历和非递归遍历（附详细例子） DAY4| 24. 两两交换链表中的节点、19.删除链表的倒数第N个节点、面试题 02.07. 链表相交、142.环形链表II 安卓手机上通过Termux运行Linux系统 代码随想录算法训练营第一天| 704. 二分查找、27. 移除元素 Python 爬虫案例 相关下载 堆排序/二叉树排序/关键路径/Dijkstra算法下载 排序算法与回溯算法下载 C# 二叉树算法排序下载 二叉树排序算法及demo下载 选择与排序算法下载 最新编程技术文章 网站地图 Copyright © 2021-2022 www.miaokee.com 秒客网 备案号：粤ICP备2021167564号 免责声明：本站文章多为用户分享,部分搜集自互联网,如有侵权请联系站长,我们将在72小时内删除。 