数据结构期末复习 大一下复习数据结构期末复习二叉树的遍历牢记递归思想。// 中序遍历 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); // 递归排序右子数组 } }堆排序（Heap Sort）：利用堆这种数据结构，将数组看成完全二叉树，构建最大堆，然后依次取出堆顶元素进行排序。