1. 最小生成树 (Minimum Spanning Tree, MST)所属结构图Graph定义在一个包含nnn个顶点的连通无向加权图中找到一棵包含所有顶点的树使得这棵树上所有边的权重之和最小。核心特点包含原图的所有顶点且恰好有n−1n-1n−1条边。图中不能有环。一个图可能有多个最小生成树当存在权重相同的边时。经典算法Prim算法、Kruskal算法。应用场景网络布线如铺设电缆、光纤、道路规划、聚类分析等旨在以最低成本连通所有节点。红色连接线组成的部分2. 平衡二叉树 / AVL树 (Balanced Binary Tree )所属结构二叉搜索树BST定义它是一棵空树或它的左右两个子树的高度差的绝对值不超过1并且左右两个子树都是一棵平衡二叉树。核心特点具备二叉搜索树的性质左子树节点 根节点 右子树节点。通过旋转操作左旋、右旋等在插入和删除节点时自动维持平衡。查找、插入、删除的时间复杂度均稳定在O(log⁡n)O(\log n)O(logn)。应用场景需要频繁进行动态查找、插入和删除操作且对查找性能要求极高的场景如数据库索引、内存中的有序字典。3. 完全二叉树 (Complete Binary Tree)所属结构二叉树定义一棵深度为kkk的二叉树除第kkk层外其它各层(1∼k−1)(1 \sim k-1)(1∼k−1)的结点数都达到最大个数且第kkk层所有的结点都连续集中在最左边。核心特点叶子结点只能出现在最下层和次下层且最下层的叶子结点集中在树的左侧。非常适合用数组顺序存储来表示父子节点之间可以通过简单的数学公式如2i,2i12i, 2i12i,2i1进行索引无需指针。应用场景它是堆Heap的底层数据结构广泛应用于优先队列、堆排序、Top-K问题等。4. 哈夫曼树 (Huffman Tree)所属结构二叉树带权路径长度最优二叉树定义给定nnn个权值作为nnn个叶子结点构造一棵二叉树若该树的带权路径长度WPL达到最小则称这棵树为哈夫曼树。核心特点权值越大的结点离根节点越近路径越短。只有叶子结点有数据没有度为1的结点严格二叉树。构造过程采用贪心策略每次选取权值最小的两个结点合并。应用场景数据压缩哈夫曼编码如ZIP、JPEG等格式的核心算法也用于最优判定树的设计。计算带权路径长度 WPL2路径长度 3 → 2×363路径长度 3 → 3×395路径长度 2 → 5×2107路径长度 1 → 7×17WPL69107325. 二叉排序树 (Binary Search Tree, BST)核心定义一棵二叉树满足以下性质若左子树不为空则左子树上所有节点的值均小于根节点的值。若右子树不为空则右子树上所有节点的值均大于根节点的值。左右子树也分别是一棵二叉排序树。核心优势中序遍历左-根-右的结果是一个递增的有序序列。查找、插入、删除的平均时间复杂度为O(log⁡n)O(\log n)O(logn)。致命缺陷退化问题BST 的结构取决于数据的插入顺序。如果插入的数据本身已经是有序的例如1, 2, 3, 4, 5BST 会退化成一条单链表。此时树的高度从log⁡n\log nlogn变成了nnn查找、插入、删除的时间复杂度会急剧恶化到O(n)O(n)O(n)完全丧失了树形结构的优势。右图是合法 BST但左右高度差极大查询效率退化到链表6. 满二叉树 (Full Binary Tree)核心定义一棵深度为kkk且有2k−12^k-12k−1个结点的二叉树。每一层的结点数都达到了最大值且所有叶子结点都在同一层。考察重点性质推导如“第iii层最多有2i−12^{i-1}2i−1个结点”。与完全二叉树的区别这是选择题最爱挖坑的地方满二叉树一定是完全二叉树但完全二叉树不一定是满二叉树。结点编号规律在顺序存储数组中结点iii的父节点、左右孩子的下标计算。7. 线索二叉树 (Threaded Binary Tree)核心定义在普通二叉树的空指针域中添加指向其前驱或后继的“线索”Thread并增加两个标志位ltag, rtag来区分指针是指向孩子还是线索。考察重点手工构造线索化给定一棵树和前/中/后序遍历序列让你画出线索化后的结构或者标出 ltag/rtag 的值。非递归遍历理解线索二叉树如何在不借助栈的情况下实现遍历。寻找前驱/后继例如“在中序线索二叉树中如何找到某结点的直接前驱”。来自王道考研的截图B站有免费的课8. 红黑树 (Red-Black Tree)核心定义一种自平衡二叉搜索树。通过节点着色红/黑和五大性质如根节点为黑、红节点的孩子必为黑、任意节点到叶子节点的黑高相同等来维持大致平衡。考察重点与 AVL 树的对比红黑树牺牲了严格的平衡换取了插入/删除时更少的旋转次数。工程应用经常作为选择题的背景知识例如 Java 的HashMapJDK 1.8、C 的std::map、Linux 内核的 CFS 调度器等底层都使用了红黑树。注考研极少要求手写红黑树的左旋/右旋代码但必须深刻理解其思想和性质。9. B树 与 B树 (B-Tree BTree)核心定义多路平衡搜索树专为磁盘等外部存储设计。B树是B树的改进版非叶子节点只存索引数据全在叶子节点且叶子节点之间有指针相连。考察重点阶数计算给定关键字个数、阶数mmm求树的高度范围或求某个节点最少/最多包含多少关键字。B树与B树的对比这是简答题和选择题的常客。B树在范围查找、顺序访问、减少磁盘I/O方面优于B树。应用场景数据库索引MySQL InnoDB 默认使用 B 树、文件系统。10. 堆 (Heap)核心定义一种特殊的完全二叉树。分为大根堆父节点≥\ge≥子节点和小根堆父节点≤\le≤子节点。考察重点建堆过程给定一个无序数组画出自底向上调整Heapify建堆的过程。插入与删除插入元素后的“上浮”操作删除堆顶元素后的“下沉”操作。堆排序结合排序算法考察建堆的时间复杂度O(n)O(n)O(n)以及堆排序的稳定性不稳定。 核心树形结构综合对比表数据结构所属类型核心定义与特点时间复杂度考研核心考点典型应用场景最小生成树无向加权图连通所有顶点且边权总和最小的树取决于算法 (Prim/Kruskal)算法思想贪心、手写代码或模拟过程网络布线、道路规划、最低成本连通二叉排序树 (BST)二叉搜索树左子树 根 右子树中序遍历有序平均O(log⁡n)O(\log n)O(logn)最坏O(n)O(n)O(n)插入/删除操作、退化问题基础动态查找、排序AVL树自平衡二叉搜索树任意节点左右子树高度差≤1\le 1≤1严格稳定O(log⁡n)O(\log n)O(logn)四种旋转操作LL/RR/LR/RL、平衡因子计算读多写少、对查询性能要求极高的场景完全二叉树普通二叉树节点从上到下、从左到右紧密排列插入/删除O(1)O(1)O(1)(数组尾部)与满二叉树的区别、数组下标计算规律堆排序、优先队列、Top-K问题哈夫曼树带权二叉树带权路径长度(WPL)最短权值大离根近构造O(nlog⁡n)O(n \log n)O(nlogn)WPL计算、构造过程、哈夫曼编码数据压缩、最优判定满二叉树普通二叉树深度为kkk结点数恰好为2k−12^k-12k−1-结点数量与层数推导、性质判断理论分析基准线索二叉树二叉搜索树(衍生)利用空指针域记录前驱/后继带标志位遍历O(n)O(n)O(n)(无需栈)手工画出前/中/后序线索化结果、找前驱后继非递归遍历、节省栈空间红黑树自平衡二叉搜索树节点着色保证最长路径不超过最短路径的两倍严格稳定O(log⁡n)O(\log n)O(logn)与AVL树的对比、五大性质、工程应用Java HashMap、C map、Linux内核B树 / B树多路平衡搜索树节点包含多个关键字专为磁盘I/O设计查找/插入/删除O(log⁡mn)O(\log_m n)O(logm​n)阶数mmm的计算、B树与B树的区别数据库索引(MySQL)、文件系统堆 (Heap)完全二叉树大根堆(父≥\ge≥子)或小根堆(父≤\le≤子)建堆O(n)O(n)O(n)增删O(log⁡n)O(\log n)O(logn)建堆过程(Heapify)、上浮/下沉操作、稳定性堆排序、优先队列、Top-K