大一下复习

数据结构期末复习

二叉树的遍历

牢记递归思想。

// 中序遍历
void mFind(Node* root) {
    if (root == nullptr) {
        return;
    }
    // 先递归遍历左子树
    mFind(root->lc);
    // 访问当前结点
    cout << root->data << " ";
    // 再递归遍历右子树
    mFind(root->rc);
}

树和森林的转换

参考视频

树转森林：删除树的根节点，根节点的子树即为森林。
森林转树：将森林的第一棵树作为树的根节点，其他树作为根节点的子树依次连接起来。

哈夫曼树（Huffman Tree）

带权路径长度：带权路径长度 = SUM（长度*权值）

选择权值最小的两个节点作为左右子树。
合并这两个节点并更新权值，重复以上步骤，直到只剩一个根节点。

图

入度和出度：在有向图中，如果一个人可以向多个人说话（即有多个人可以听他说话），那么他的“出度”就是他说话对象的数量。相对的，“入度”就是有多少人可以向他说话。

深度优先搜索：D(Depth)FS（类似树的先序遍历）

// DFS 深度优先搜索
// 从节点u开始进行深度优先搜索
void DFS(int u) {
  // 输出当前访问的节点u
  cout << u << " ";
  // 标记节点u为已访问
  vis[u] = 1;
  // 遍历节点u的邻接表 递归访问所有未被访问的相邻节点
  for (int i = head[u]; i != -1; i = edg[i].next) {
      int v = edg[i].to;
      if (!vis[v]) {
          DFS(v);
      }
  }
}

广度优先搜索：B(Breadth)FS（类似树的层序遍历）
拓扑排序：每次选入度为0的点，然后删除这个点和它的出边

最小生成树（Minimum Spanning Tree）

参考视频

Prim算法：从任一节点开始，每次选择权值最小的边连接一个新节点，直到所有节点都连接。
Kruskal算法：将所有边按权值从小到大排序，依次选择不形成环的最小权值边，直到所有节点都连接。

最短路径（Shortest Path）

Dijkstra算法：用于单源最短路径，适合边权为非负的图，从起点开始逐步扩展最短路径，直到所有节点都找到最短路径。
Floyd-Warshall算法：用于任意两点间最短路径，逐步优化所有点对的路径。

二叉排序树（Binary Search Tree, BST）

BST是一种特殊的二叉树，左子树所有节点的值都小于根节点的值，右子树所有节点的值都大于根节点的值。

平衡二叉树、二叉排序树：任意节点左右子树的深度差≤1
二叉排序树的调整：参考视频（调整LL,LR,RL,RR）

B树和B+树

B树：一种自平衡的多路查找树，节点可以有多个子节点，用于数据库和文件系统。
B+树：B树的变种，所有叶子节点构成一个有序链表，更适合范围查询。

散列表（Hash Table）

散列表是一种数据结构，通过哈希函数将键映射到表中的位置进行存储，实现快速查找、插入和删除。

排序算法

插入排序（Insertion Sort）：通过构建有序序列，对未排序数据，在已排序序列中从后向前扫描，找到相应位置并插入。
下面这些都不稳定
希尔排序（Shell Sort）：插入排序的一种改进，分组进行插入排序，逐步减少分组数量，最终整体插入排序。

快速排序（Quick Sort）：通过分区将数组分成两部分，递归对两部分排序。

// 交换两个元素的值(略)
void swap(int &a, int &b);
// 分区函数
int partition(vector<int> &arr, int low, int high) {
  int pivot = arr[high];  // 选择最后一个元素作为枢轴
  int i = low - 1;        // 指向较小元素的索引
  for (int j = low; j < high; ++j) {
      if (arr[j] < pivot) {  // 如果当前元素小于枢轴
          ++i;
          swap(arr[i], arr[j]);  // 交换arr[i]和arr[j]
      }
  }
  swap(arr[i + 1], arr[high]);  // 将枢轴放在正确的位置
  return i + 1;                 // 返回枢轴的索引
}
// 快速排序函数
void quickSort(vector<int> &arr, int low, int high) {
  if (low < high) {
      int pi = partition(arr, low, high);  // 获取分区索引
      quickSort(arr, low, pi - 1);  // 递归排序左子数组
      quickSort(arr, pi + 1, high); // 递归排序右子数组
  }
}