文章摘要 本文系统介绍了哈夫曼树及其应用。首先定义了带权路径长度（WPL）的计算方法，通过实例比较不同二叉树的WPL值。重点阐述哈夫曼树的构造算法：每次合并权值最小的两棵树，最终生成WPL最小的最优二叉树，其具有结点总数2n-1、无度为1结点等特点。经典应用为哈夫曼编码，通过将高频字符分配短编码实现数据压缩，相比固定长度编码可显著减少传输位数。文中还通过字母频率统计案例，展示了哈夫曼编码实现59.

本文介绍了Dijkstra最短路径算法及其应用。首先指出BFS算法在求单源最短路径时的局限性，仅适用于无权图或权值相同的图。然后详细阐述了Dijkstra算法的实现思路：通过维护三个数组（标记已找到最短路径、最短路径长度、前驱顶点），逐步确定各顶点的最短路径。算法步骤包括初始化数组、选择当前最短路径顶点、更新相邻顶点信息等。最后通过具体案例演示了算法执行过程，展示了如何通过迭代更新找到从起点到各顶

摘要：本文详细介绍了中序和先序线索二叉树中查找指定节点的前驱和后继的方法。对于中序线索二叉树，当rtag=1时后继为右孩子，rtag=0时需找到右子树最左下节点；前驱同理通过ltag判断。先序线索二叉树中，后继根据左右孩子存在情况决定，前驱则需通过三叉链表或逆向遍历实现。文章提供了各场景下的算法思路和完整代码实现，包括非递归的中序/先序遍历方法。

本文介绍了最小生成树（MST）的概念及其求解方法。生成树是包含图中所有顶点的极小连通子图，边数为顶点数减1。最小生成树是权值之和最小的生成树，可能不唯一但总权值唯一。文章重点讲解了Prim算法的实现步骤：从初始顶点出发，逐步选择权值最小的边将新顶点纳入生成树，直到所有顶点都被包含。算法通过维护lowCost数组记录各顶点到生成树的最小代价，并不断更新该数组来实现最小生成树的构建。适用于带权连通无向

本文介绍了求解无权图单源最短路径的BFS算法。首先对最短路径问题进行了分类，分为单源最短路径和每对顶点间最短路径，分别对应BFS/Dijkstra和Floyd算法。重点讲解了BFS算法的实现过程：通过队列逐层遍历，记录各顶点到源点的距离和路径前驱，最终得到最短路径。相比普通BFS，增加了距离数组d和前驱数组path的记录。文章还指出广度优先生成树的层数反映了顶点到源点的最短距离。最后附上了代码实现

这篇文章是一位考研学生分享的数据结构学习笔记合集。作者提供了详细的数据结构学习资料，包括代码示例、图表解释和习题解答，全部免费开放。目前专栏主要包含数据结构内容，每隔一天更新两章，后续会逐步添加其他考研科目笔记。文章末尾附有已完成的10个数据结构章节链接，包括线性表、栈、队列、树等主题，并承诺持续更新。作者以轻松的笔调分享学习资源，同时也表达了对考研学子的祝福和共勉之意。

快速排序是一种基于交换的排序算法，通过分治策略将待排序序列划分为两部分。算法首先选取基准元素（通常为首元素），使用双指针low和high从序列两端向中间扫描，确保low指针左侧元素均小于基准，high指针右侧元素均大于等于基准。通过不断交换元素位置，最终将基准元素放置到正确位置，完成一次划分。然后递归地对左右子序列重复上述过程，直至所有元素有序。示例中展示了以49为基准的一次完整划分过程，通过双指

本文介绍了红黑树(RBT)的基本概念与应用。红黑树作为二叉排序树的改进，通过颜色约束保持近似平衡，相比AVL树大幅降低了插入删除时的调整开销。文章详细阐述了红黑树的五大特性（根黑、叶黑、不红红、黑路同），并通过实例演示了特性验证方法。此外，讲解了黑高计算、路径长度性质等核心概念，以及红黑树与平衡二叉树的适用场景对比。最后指出红黑树在查找操作上与普通BST、AVL树相同，时间复杂度为O(logn)。

平衡二叉树（AVL树）是一种特殊的二叉排序树，其任一结点的左右子树高度差不超过1。本文首先介绍了平衡二叉树的基本概念，包括平衡因子、最小不平衡子树等定义。重点分析了平衡二叉树的插入操作，当插入新结点导致不平衡时，需要通过旋转调整恢复平衡。具体以LL不平衡情况为例，详细阐述了右单旋转的操作步骤和逻辑，通过调整最小不平衡子树使树重新达到平衡状态。文章还给出了平衡二叉树的C语言结点定义，为后续代码实现提

分块查找算法是一种结合顺序查找和索引查找的搜索方法。其核心思想是将无序元素分成若干有序块，建立索引表存储各块最大值和区间范围。查找时先通过顺序或折半方式定位索引块，再在该块内进行顺序查找。算法特点包括块内无序、块间有序。查找效率分析表明，当块数为√n时，顺序查找索引表可获得最优ASL(√n+1)，而折半查找索引表则使ASL为⌈log₂(b+1)⌉+(s+1)/2。对于动态查找表，采用链式存储能有效