1. 树与二叉树基础概念精讲树结构是计算机科学中最重要的非线性数据结构之一广泛应用于文件系统、数据库索引等领域。在考研数据结构中树与二叉树章节占据约15%的分值比重是必须掌握的核心内容。树的定义可以类比现实中的家族树有一个唯一的根节点祖先每个节点可以有多个子节点后代但只能有一个父节点直接上级。这种一对多的关系使得树特别适合表示层级关系。例如操作系统中的目录结构就是典型的树形应用。二叉树是每个节点最多有两个子节点的特殊树结构。与普通树不同二叉树严格区分左子树和右子树即使只有一个子节点也必须明确其左右位置。这个特性使得二叉树在算法实现上更加规范。常见易错点混淆度为m的树与m叉树前者至少有一个节点度为m后者所有节点度≤m忽略二叉树是有序树交换左右子树会得到不同的二叉树计算结点数时漏算根节点总节点数总度数1根节点没有父节点2. 二叉树核心性质与计算技巧2.1 特殊二叉树特征对比类型节点特征层序编号规则应用场景满二叉树所有非叶节点度为2叶子全在最底层i的左孩子2i右孩子2i1堆结构基础完全二叉树仅最后两层有叶子且左对齐同满二叉树优先队列实现二叉排序树左根右的有序关系无固定规则动态查找系统平衡二叉树任意节点左右子树高度差≤1通过平衡因子调整数据库索引完全二叉树的性质在考研中频繁出现当n为偶数时有1个度为1的节点且必为左孩子分支节点与叶节点的分界点是⌊n/2⌋高度为h的完全二叉树至少2^(h-1)个节点至多2^h-1个节点真题示例 已知完全二叉树第6层有8个叶子求最少节点数。 解前5层满节点31第6层8叶说明第5层有⌈8/2⌉4个非叶节点总节点3148432.2 遍历序列还原二叉树二叉树的遍历是考试重点三种遍历方式的非递归实现需要熟练掌握。更关键的是根据遍历序列还原二叉树必须包含中序序列才能唯一确定二叉树形态。解题步骤用前序/后序的第一个/最后一个元素确定根节点在中序序列中找到根的位置划分左右子树递归处理左右子树高频错题 已知前序ABDECFG中序DBEAFCG求后序。 解A为根左子树(DBE)右子树(FCG)→左子树前序BDE→B为根→D左E右→右子树前序CFG→C为根→F左G右→后序DEBFGCA3. 线索二叉树实战解析3.1 线索化原理普通二叉树存在大量空指针域n个节点有n1个空链域线索化利用这些空域存储遍历顺序中的前驱后继信息。通过增加两个标志位ltag0时lchild指向左孩子1时指向前驱rtag0时rchild指向右孩子1时指向后继中序线索化代码实现void InThread(ThreadTree p, ThreadTree pre) { if(p) { InThread(p-lchild, pre); // 递归左子树 if(!p-lchild) { // 左子树为空建立前驱线索 p-lchild pre; p-ltag 1; } if(pre !pre-rchild) { // 前驱节点右子树为空建立后继线索 pre-rchild p; pre-rtag 1; } pre p; // 更新pre指针 InThread(p-rchild, pre); // 递归右子树 } }3.2 线索二叉树的遍历线索二叉树的最大优势是可以直接找到前驱后继无需递归栈找中序后继ThreadNode *NextNode(ThreadNode *p) { if(p-rtag 1) return p-rchild; // 直接返回线索 else { p p-rchild; // 进入右子树 while(p-ltag 0) // 找最左下节点 p p-lchild; return p; } }易错警示先序线索二叉树中找前驱需要知道父节点指针普通线索无法实现后序线索二叉树中找后继同样需要父节点信息中序线索是唯一能同时方便找前驱后继的情况4. 树与森林的转换技巧4.1 存储结构对比存储方式优点缺点适用场景双亲表示法找父节点快O(1)找孩子需要遍历并查集实现孩子表示法找孩子方便找父节点困难需要频繁查询子节点孩子兄弟表示法树与二叉树转换的桥梁找父节点需额外处理森林与二叉树转换孩子兄弟表示法二叉树表示法是最重要的存储方式firstchild相当于二叉树的左孩子nextsibling相当于二叉树的右孩子这种表示法使得树和二叉树的算法可以相互转换4.2 森林与二叉树转换转换规则每棵树的根节点作为二叉树的根树中节点的第一个孩子作为二叉树的左孩子树中节点的右兄弟作为二叉树的右孩子重要性质森林的先序遍历序列 对应二叉树的先序序列森林的后序遍历序列 对应二叉树的中序序列注意不是后序5. 高频考点平衡二叉树调整平衡二叉树AVL树的调整是每年必考大题需要掌握四种旋转场景5.1 失衡类型与调整LL型在A的左孩子的左子树插入导致失衡右旋操作将B作为根A作为B的右孩子BR作为A的左孩子RR型在A的右孩子的右子树插入导致失衡左旋操作将B作为根A作为B的左孩子BL作为A的右孩子LR型在A的左孩子的右子树插入导致失衡先左旋后右旋先对C左旋变成LL型再整体右旋RL型在A的右孩子的左子树插入导致失衡先右旋后左旋先对C右旋变成RR型再整体左旋记忆口诀 LL右旋RR左旋LR先左后右RL先右后左5.2 平衡二叉树插入示例插入序列{15, 3, 7, 10, 9, 8}插入15和3后正常插入7时节点15失衡LR型先对3左旋3作为7的左孩子再对15右旋7作为根3左15右插入10后无失衡插入9时节点15失衡RL型先对10右旋10作为9的右孩子再对15左旋9作为根7左15右插入8时节点9失衡LR型先对7左旋7作为8的左孩子再对9右旋8作为根7左9右6. 哈夫曼树与编码实战哈夫曼树是带权路径长度WPL最小的二叉树用于数据压缩构建步骤将所有权值作为单独的树每次选取权值最小的两棵树合并新树权值为两者之和重复直到只剩一棵树真题技巧哈夫曼树没有度为1的节点n个叶子共有2n-1个节点权值小的节点路径更长同一组权值可能生成不同形态的哈夫曼树但WPL相同编码实现typedef struct { int weight; int parent, lch, rch; } HTNode; void CreateHuffmanTree(HTNode ht[], int n) { for(int i1; i2*n-1; i) ht[i] {0,0,0,0}; for(int i1; in; i) cin ht[i].weight; for(int in1; i2*n-1; i) { int s1, s2; Select(ht, i-1, s1, s2); // 选择两个最小权值 ht[i].weight ht[s1].weight ht[s2].weight; ht[s1].parent ht[s2].parent i; ht[i].lch s1; ht[i].rch s2; } }在最后的冲刺阶段建议每天手写一遍二叉树的非递归遍历代码并完成2-3道平衡二叉树调整的练习题。对于线索二叉树要重点理解不同遍历顺序下前驱后继的查找逻辑差异。实际编程时树的深度优先搜索与二叉树遍历有诸多相似之处这种触类旁通的能力正是考研考察的重点。