1. 先聊聊2026年3月六级这道题到底在考什么CCF-GESP的六级放在整个等级体系里看属于进阶分水岭。三级考数组和字符串四级考函数和排序五级开始接触数据结构到了六级树、图、贪心、DP 这些正统算法基础正式登场。所以历年六级的 T2第二道编程题一直有个特点不考偏题怪题但会把经典数据结构藏在生活化的场景里看你能不能把模型抽出来。这次 2026 年 3 月的 T2 落在完全二叉树上其实并不意外。完全二叉树是连接线性结构数组和树形结构二叉链表的一座桥也是在等级考试里“纸上谈兵”最容易翻车的知识点——因为它有一大堆优美的数学性质但只要你公式记错一个下标整道题全军覆没。简单说这道题给了一个完全二叉树的框架让你去计算、判断、或者遍历输出某些节点。它考察的不只是你会不会写递归而是你懂不懂完全二叉树“用数组存树”背后的编号规律以及能不能把这个规律迁移到具体问题上。对于准备六级的学生来说这种题型恰恰是最该拿满分的地方因为模型固定、套路清晰不像 T3 那样需要现场想状态转移。这篇文章我就以这道 T2 为中心把完全二叉树在 C 里常用的性质、代码模板、以及考场上的坑一次性讲透。不管你是正在备考六级还是在带学生刷 GESP下面的内容都能直接用。2. 完全二叉树的核心性质先把这些公式刻在脑子里2.1 完全二叉树和满二叉树到底差在哪很多人考场上出错第一步就错在概念混淆。满二叉树Perfect Binary Tree是每一层都塞满节点总共 2^k - 1 个节点而完全二叉树Complete Binary Tree只要求最后一层可以不满但最后一层的节点必须从左到右连续排列不能出现“左边空着右边有节点”的情况。举个例子高度为 3 的满二叉树一定有 7 个节点但完全二叉树高度为 3 时节点数可以是 4 到 7 之间的任意值。只要按层序遍历编号时节点编号是 1 到 n 连续排下来的它就是完全二叉树。这个“层序编号连续”就是它最核心的特征后面所有性质都从这里推导。在 GESP 六级这个难度题目一般不会直接问你定义而是把定义包装成判断条件或者计算条件。比如给你一个数组让你判断它能不能构成完全二叉树或者给你 n 个节点让你求树高。这时候脑子里必须快速反应出下面几个公式。2.2 必须背下来的四个关键公式假设我们用数组从下标 1 开始存完全二叉树的节点根节点是 tree[1]那么对于任意下标 i 的节点有以下性质左孩子下标2 * i右孩子下标2 * i 1父节点下标i / 2整数除法最后一个非叶子节点的下标n / 2n 为节点总数这四个公式是整个完全二叉树操作的基石。判断一个节点是不是叶子节点就看 2 * i 是否大于 n判断它有没有右孩子就看 2 * i 1 是否小于等于 n求树高可以直接用 log2(n) 向下取整再加 1或者用 while 循环除以 2 数次数。注意如果数组从下标 0 开始存那么左孩子是 2i1右孩子是 2i2父节点是 (i-1)/2。考场上我强烈建议统一用从 1 开始的下标因为公式更对称integer division 不用纠结负数问题而且很多教材和题解默认就是 1-based。树高的计算也有两种方式我分别说一下。// 方法一直接用数学库 #include cmath int height (int)floor(log2(n)) 1; // 方法二循环求更稳不会因为浮点精度翻车 int h 0; int temp n; while (temp 0) { h; temp / 2; }第一种写法简洁但浮点数在 n 接近 2 的整数次幂时偶尔会有精度问题比如 log2(8) 在某些环境下返回 2.9999999。竞赛场景里我更推荐第二种稳如老狗。2.3 用生活类比帮助记忆完全二叉树的数组存储你可以想象成电影院座位的编号规则从入口开始左边第一排第一个座位是 1 号然后从左到右、从前到后依次编号。如果你知道某个座位的编号是 i那它正下方偏左的那个座位就是 2i正下方偏右就是 2i1。这种“连续编号”的方式保证了你不需要存左右孩子指针光靠数学运算就能在树上游走。这也是为什么堆排序、优先队列都爱用完全二叉树结构——因为省空间、寻址快、代码短。理解了这层关系你在 GESP 考场上的实现思路会清晰非常多。3. 模拟真题一个典型的六级 T2 长什么样3.1 题目模型还原虽然具体真题的完整表述我没有拿到但根据 GESP 历年六级 T2 的出题规律完全二叉树这个考点跑不出下面几种模型模型 A给你一个层序遍历数组判断它是不是合法的完全二叉树模型 B给你节点总数 n求完全二叉树的树高、叶子节点数、某一层的节点数模型 C对完全二叉树做某种遍历前序/中序/后序/层序要求按指定格式输出模型 D在完全二叉树上做路径查找比如找两个节点的最近公共祖先LCA其中模型 A 和模型 B 出现频率最高而且经常结合起来考先判断再计算。我下面就以“模型 A 模型 B 组合”为例子完整走一遍解题流程这个流程可以直接套用到考场上。3.2 手把手推导用数组判断是否是完全二叉树题目大致可以还原为输入一个长度为 n 的数组表示按层序遍历顺序给出的二叉树节点空节点用 -1 表示请判断这棵树是否为一棵完全二叉树。这个题的判断逻辑其实很简单完全二叉树按层序遍历时空节点之后不应该再出现非空节点。换句话说一旦遇到空节点后面的所有节点都必须是空的。为什么因为完全二叉树最后一层的节点从左到右是连续的前面的层是全满的。所以层序遍历过程中非空节点一定是连续出现在前面后面全是空节点。这个性质非常好用。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint tree(n 1); // 1-based index for (int i 1; i n; i) { cin tree[i]; } bool isComplete true; bool hasEmpty false; // 是否已经遇到过空节点 for (int i 1; i n; i) { if (tree[i] -1) { hasEmpty true; } else { if (hasEmpty) { isComplete false; break; } } } if (isComplete) { cout YES endl; } else { cout NO endl; } return 0; }这个代码看起来简单但它抓住了完全二叉树在层序遍历上的本质特征。注意这里用的是 1-based 数组下标所以 vector 开 n1读入时从 1 开始。如果你从 0 开始读判断逻辑不变但边界要多想一步。3.3 进阶判断完还能干什么如果题目要求进一步输出树高、叶子节点数、最后一层节点数可以在上面的基础上继续扩展。仍然以 1-based 数组为例n 个节点// 树高 int height 0; int temp n; while (temp 0) { height; temp / 2; } // 叶子节点数 // 思路叶子节点就是没有左孩子的节点即 2*i n int leafCount 0; for (int i 1; i n; i) { if (2 * i n) leafCount; } // 最后一层节点数 // 思路最后一层节点 总节点数 - 上面所有层的节点数 // 上面所有层的节点数 2^(height-1) - 1 int lastLevelCount n - ((1 (height - 1)) - 1);这些计算在考场上都是送分操作前提是你对公式足够熟。叶子节点数还有另一个推导方式最后一个非叶子节点下标是 n/2所以叶子节点数就是 n - n/2。比如 n6n/23从下标 4、5、6 开始都是叶子所以叶子数是 3。你对比一下上面的循环会发现结果完全一致但后者一行就搞定。我个人的习惯是能用公式推导的别用循环。考场上的每一分钟都很贵而且循环写多了容易在边界出 bug。平时练习时多训练“从公式到代码”的直觉考试时才能快起来。3.4 层序遍历输出的完整模板如果题目要求按某种顺序输出节点值核心就是利用父子下标关系做递归或队列遍历。下面给一个最常用的层序遍历模板用队列实现时间复杂度 O(n)空间复杂度 O(n)。#include bits/stdc.h using namespace std; const int MAXN 100005; int tree[MAXN]; void levelOrder(int n) { queueint q; q.push(1); // 根节点下标 while (!q.empty()) { int idx q.front(); q.pop(); cout tree[idx] ; if (2 * idx n) q.push(2 * idx); // 左孩子 if (2 * idx 1 n) q.push(2 * idx 1); // 右孩子 } } int main() { int n; cin n; for (int i 1; i n; i) cin tree[i]; levelOrder(n); return 0; }这里有个细节值得注意入队时不需要判断节点值是否为空因为数组下标能落在 [1, n] 范围内就说明这个位置一定有节点。层序遍历顺序天然就是数组下标从小到大的顺序所以用队列是杀鸡用牛刀——直接 for 循环输出 tree[1] 到 tree[n] 效果一样。但这题的进阶版本可能要求前序/中序/后序输出那递归就是你躲不掉的了。3.5 递归遍历的三种写法前序/中序/后序以数组存储的完全二叉树递归遍历同样是靠下标关系游走。下面给出前序遍历模板中序和后序只是调整输出语句的位置。void preorder(int idx, int n) { if (idx n) return; cout tree[idx] ; // 前序先访问根 preorder(2 * idx, n); // 再左子树 preorder(2 * idx 1, n); // 最后右子树 }如果把输出语句放在两行递归调用中间就是中序遍历放在两个递归调用之后就是后序遍历。这里我要提醒一个六级考生最容易犯的错一定不要忘了递归出口 if (idx n) return;。数组存储的树没有指针判断“这个节点是否存在”的方式就是检查下标是否越界。丢了这一行程序直接数组越界轻则乱码重则 RE。4. 考场上最容易踩的五个坑我帮你一个个排掉4.1 数组越界的隐藏触发点完全二叉树的数组存储理论上节点数最多到 2^k - 1 个但题目给的 n 再大也得给数组开够。有些同学为了省空间开 vector tree(n5)结果递归时 2idx1 会不会超过这个 n5完全可能。因为你的 idx 会走到最后一个非叶子节点它的右孩子下标可能是 2(n/2)1这个值在 n 不大时没问题但如果 n 是 2 的幂减 1那最后一个非叶子节点的右孩子正好是 n没问题但如果是其他情况比如 n6最后一个非叶子节点是下标 3它的右孩子是 7而 7 6这个位置根本不存在。所以数组大小必须开成最大节点数的两倍以上如果题目明确说 n ≤ 10^5那就开 2*n5 甚至更大别卡着边界开。我见过太多考生因为这种低级错误在 T2 上丢掉 AC非常可惜。4.2 下标从 0 还是从 1必须从头到尾统一这是完全二叉树题目的第一大坑。题目如果是给数组大概率是从 1 开始输入因为层序遍历编号天然从 1 开始但有的题目为了迷惑你会从 0 开始给输入。如果你用 1-based 的公式去做 0-based 的输入所有下标全部错位后面全盘皆输。我的习惯是读入之前先看题目样例。如果样例里根节点对应的值是数组第一个值那就直接把所有下标减 1然后统一用 0-based 公式左孩子 2i1右孩子 2i2父节点 (i-1)/2。一旦选定所有函数、循环、递归都要用同一套公式中途混用必炸。4.3 用 cin 读大数据导致超时GESP 六级的 T2节点数 n 经常会到 10^5 甚至 10^6 级别。这时候如果你用 cin tree[i] 一个个读不开任何优化大概率超时。这不是算法问题是 IO 问题。解决办法有两个二选一即可// 解决办法1关同步最省事 ios::sync_with_stdio(false); cin.tie(0); // 解决办法2直接上 scanf for (int i 1; i n; i) { scanf(%d, tree[i]); }如果你用的是 cin记得把这两行加在 main 函数开头。如果你追求极致性能直接按 scanf 处理。刷题量上来之后你会发现这种 IO 优化是刻在肌肉记忆里的。4.4 递归层数过深导致栈溢出完全二叉树的树高是 O(log n)理论上递归是安全的。但如果你写的递归不是按完全二叉树的层序方向走而是走了某种链状的路径比如查找某个节点的父节点一直往上循环那最坏情况下会退化成 O(n) 的递归深度。比如 n10^5递归深度 10^5在很多系统上会爆栈。应对方案如果必须递归可以考虑在 main 函数开头加一句 _GLIBCXX_MAKE_LIMITS 或者 visual studio 里用 setrlimit 之类的系统调用但考场环境通常不允许你改栈空间。更稳的做法是把递归改成循环。完全二叉树的结构很适合用循环操作因为下标关系就在那儿摆着。4.5 判断“完全”时用错特征有些同学判断完全二叉树的思路是“每一层节点数是否等于 2 的幂”但这只适用于满二叉树。完全二叉树只有最后一层可以不满而且最后一层的节点必须靠左连续。如果你用“每层满不满”来判断遇到 n4 的完全二叉树形状是根的两个孩子都在最后一层左边那个孩子也在就会被误判因为它不是每一层都满的。正确思路就是我前面讲的层序遍历遇到空节点之后后面不能再出现非空节点。这个特征既准确又容易实现。5. 备考完全二叉树建议按这个顺序刷题5.1 从 GESP 考纲出发先掌握数组建树六级的考试范围里树这个章节的要求是“掌握二叉树的存储、遍历理解完全二叉树与满二叉树的区别”。按我的经验备考顺序应该是先熟练掌握数组下标方式存储完全二叉树并背下四个核心公式用三个典型题练手层序遍历输出、判断是否是完全二叉树、求树高/叶子数/最后一层节点数再做两个拓展题用完全二叉树实现一个小根堆堆的插入和删除、求两个节点的最近公共祖先最后把递归遍历前序/中序/后序和层序遍历都写熟你需要警惕一种情况只会背代码不理解公式的推导。考场上只要题目换个马甲比如不是让你输出节点值而是让你计算某个节点的深度你就容易懵。所以平时练习时每写一个公式都要问自己一句“为什么是这个”把推导过程在草稿纸上过一遍。5.2 推荐按这个优先级刷题GESP 2023 年至 2025 年的历年真题这是最贴近考纲的练习材料优先刷洛谷 P4913 【深基16.例3】二叉树深度适合入门热身洛谷 P1364 医院设置稍微绕一点锻炼建树能力AcWing 846 树的重心虽然不是完全二叉树但能练树的 DFS 基本功力扣 222 完全二叉树的节点个数这题虽然是 LeetCode 风格但思路对 GESP 很有帮助力扣 958 二叉树的完全性检验直接对应判断完全二叉树刷题口诀先模拟再变形先看题解再独立写写完后把核心公式抄到错题本上考前半小时翻一遍。我见过不少学生刷题时喜欢直接看题解看完觉得自己会了一考就废。正确做法是拿到题先自己画图把样例推一遍然后动手写卡住了再看题解看完把代码关掉重新写一遍。这个过程很痛苦但效果立竿见影。6. 5 分钟默写模板考场直接起飞6.1 核心代码速查表下面是完全二叉树最常用的代码片段剪贴到你的“考前模板”里考前默写两遍考场直接套用。// 树高 int getHeight(int n) { int h 0; while (n 0) { n / 2; h; } return h; } // 叶子节点数1-based int getLeafCount(int n) { return n - n / 2; } // 判断是否是完全二叉树层序遍历 空标记 bool isComplete(vectorint tree, int n) { bool hasEmpty false; for (int i 1; i n; i) { if (tree[i] -1) hasEmpty true; else if (hasEmpty) return false; } return true; } // 前序遍历数组存储1-based void preorder(int idx, int n, vectorint tree) { if (idx n) return; cout tree[idx] ; preorder(idx * 2, n, tree); preorder(idx * 2 1, n, tree); } // 层序遍历队列 void levelOrder(int n, vectorint tree) { queueint q; q.push(1); while (!q.empty()) { int idx q.front(); q.pop(); cout tree[idx] ; if (idx * 2 n) q.push(idx * 2); if (idx * 2 1 n) q.push(idx * 2 1); } }这个模板大概三十行考前花 5 分钟默写一遍考场心里就有底了。6.2 考场时间分配建议GESP 六级总共两个半小时T1 一般是最基础的题建议 20 分钟内解决T2 这种套路题建议控制在 40 分钟内包括读题、写代码、测试样例剩下的时间留给 T3 和检查。如果 T2 在 30 分钟内还没头绪先跳过做 T3 的大题后面再回来补。很多学生栽在“死磕一道题”这个陷阱里T3 明明有部分分可以拿结果时间全耗在 T2 上最后两边都没做好。我的经验是T2 的完全二叉树题难度上限基本就是“判断 遍历 基础计算”不会出到建树旋转那种程度。所以只要公式背熟模板写顺拿满分是大概率事件。7. 写在最后的个人建议我这些年带过不少备考 GESP 六级的学生发现一个规律能在完全二叉树上拿满分的孩子不是智商多高而是愿意花时间把基础数据结构的基本功打牢。他们会在草稿纸上画很多棵树会手动模拟数组下标会把公式从头推导一遍——这些“笨功夫”才是考场上最可靠的东西。这道 T2 真正想考验的不只是你会不会做这一道题而是你有没有建立起“用数组思维去理解树形结构”的能力。这种能力在后面的七级、八级考试里还会反复出现尤其是堆、线段树、树状数组这些进阶数据结构全都要用到完全二叉树的数组存储思想。如果你现在做题还有些吃力别着急。把本文的公式抄在纸上把模板默写两遍再找两三道真题练手一两个星期内会有明显提升。祝你在 2026 年 3 月的考场上稳稳拿下这道 T2。
GESP六级完全二叉树：数组存储公式与代码模板全解析
1. 先聊聊2026年3月六级这道题到底在考什么CCF-GESP的六级放在整个等级体系里看属于进阶分水岭。三级考数组和字符串四级考函数和排序五级开始接触数据结构到了六级树、图、贪心、DP 这些正统算法基础正式登场。所以历年六级的 T2第二道编程题一直有个特点不考偏题怪题但会把经典数据结构藏在生活化的场景里看你能不能把模型抽出来。这次 2026 年 3 月的 T2 落在完全二叉树上其实并不意外。完全二叉树是连接线性结构数组和树形结构二叉链表的一座桥也是在等级考试里“纸上谈兵”最容易翻车的知识点——因为它有一大堆优美的数学性质但只要你公式记错一个下标整道题全军覆没。简单说这道题给了一个完全二叉树的框架让你去计算、判断、或者遍历输出某些节点。它考察的不只是你会不会写递归而是你懂不懂完全二叉树“用数组存树”背后的编号规律以及能不能把这个规律迁移到具体问题上。对于准备六级的学生来说这种题型恰恰是最该拿满分的地方因为模型固定、套路清晰不像 T3 那样需要现场想状态转移。这篇文章我就以这道 T2 为中心把完全二叉树在 C 里常用的性质、代码模板、以及考场上的坑一次性讲透。不管你是正在备考六级还是在带学生刷 GESP下面的内容都能直接用。2. 完全二叉树的核心性质先把这些公式刻在脑子里2.1 完全二叉树和满二叉树到底差在哪很多人考场上出错第一步就错在概念混淆。满二叉树Perfect Binary Tree是每一层都塞满节点总共 2^k - 1 个节点而完全二叉树Complete Binary Tree只要求最后一层可以不满但最后一层的节点必须从左到右连续排列不能出现“左边空着右边有节点”的情况。举个例子高度为 3 的满二叉树一定有 7 个节点但完全二叉树高度为 3 时节点数可以是 4 到 7 之间的任意值。只要按层序遍历编号时节点编号是 1 到 n 连续排下来的它就是完全二叉树。这个“层序编号连续”就是它最核心的特征后面所有性质都从这里推导。在 GESP 六级这个难度题目一般不会直接问你定义而是把定义包装成判断条件或者计算条件。比如给你一个数组让你判断它能不能构成完全二叉树或者给你 n 个节点让你求树高。这时候脑子里必须快速反应出下面几个公式。2.2 必须背下来的四个关键公式假设我们用数组从下标 1 开始存完全二叉树的节点根节点是 tree[1]那么对于任意下标 i 的节点有以下性质左孩子下标2 * i右孩子下标2 * i 1父节点下标i / 2整数除法最后一个非叶子节点的下标n / 2n 为节点总数这四个公式是整个完全二叉树操作的基石。判断一个节点是不是叶子节点就看 2 * i 是否大于 n判断它有没有右孩子就看 2 * i 1 是否小于等于 n求树高可以直接用 log2(n) 向下取整再加 1或者用 while 循环除以 2 数次数。注意如果数组从下标 0 开始存那么左孩子是 2i1右孩子是 2i2父节点是 (i-1)/2。考场上我强烈建议统一用从 1 开始的下标因为公式更对称integer division 不用纠结负数问题而且很多教材和题解默认就是 1-based。树高的计算也有两种方式我分别说一下。// 方法一直接用数学库 #include cmath int height (int)floor(log2(n)) 1; // 方法二循环求更稳不会因为浮点精度翻车 int h 0; int temp n; while (temp 0) { h; temp / 2; }第一种写法简洁但浮点数在 n 接近 2 的整数次幂时偶尔会有精度问题比如 log2(8) 在某些环境下返回 2.9999999。竞赛场景里我更推荐第二种稳如老狗。2.3 用生活类比帮助记忆完全二叉树的数组存储你可以想象成电影院座位的编号规则从入口开始左边第一排第一个座位是 1 号然后从左到右、从前到后依次编号。如果你知道某个座位的编号是 i那它正下方偏左的那个座位就是 2i正下方偏右就是 2i1。这种“连续编号”的方式保证了你不需要存左右孩子指针光靠数学运算就能在树上游走。这也是为什么堆排序、优先队列都爱用完全二叉树结构——因为省空间、寻址快、代码短。理解了这层关系你在 GESP 考场上的实现思路会清晰非常多。3. 模拟真题一个典型的六级 T2 长什么样3.1 题目模型还原虽然具体真题的完整表述我没有拿到但根据 GESP 历年六级 T2 的出题规律完全二叉树这个考点跑不出下面几种模型模型 A给你一个层序遍历数组判断它是不是合法的完全二叉树模型 B给你节点总数 n求完全二叉树的树高、叶子节点数、某一层的节点数模型 C对完全二叉树做某种遍历前序/中序/后序/层序要求按指定格式输出模型 D在完全二叉树上做路径查找比如找两个节点的最近公共祖先LCA其中模型 A 和模型 B 出现频率最高而且经常结合起来考先判断再计算。我下面就以“模型 A 模型 B 组合”为例子完整走一遍解题流程这个流程可以直接套用到考场上。3.2 手把手推导用数组判断是否是完全二叉树题目大致可以还原为输入一个长度为 n 的数组表示按层序遍历顺序给出的二叉树节点空节点用 -1 表示请判断这棵树是否为一棵完全二叉树。这个题的判断逻辑其实很简单完全二叉树按层序遍历时空节点之后不应该再出现非空节点。换句话说一旦遇到空节点后面的所有节点都必须是空的。为什么因为完全二叉树最后一层的节点从左到右是连续的前面的层是全满的。所以层序遍历过程中非空节点一定是连续出现在前面后面全是空节点。这个性质非常好用。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorint tree(n 1); // 1-based index for (int i 1; i n; i) { cin tree[i]; } bool isComplete true; bool hasEmpty false; // 是否已经遇到过空节点 for (int i 1; i n; i) { if (tree[i] -1) { hasEmpty true; } else { if (hasEmpty) { isComplete false; break; } } } if (isComplete) { cout YES endl; } else { cout NO endl; } return 0; }这个代码看起来简单但它抓住了完全二叉树在层序遍历上的本质特征。注意这里用的是 1-based 数组下标所以 vector 开 n1读入时从 1 开始。如果你从 0 开始读判断逻辑不变但边界要多想一步。3.3 进阶判断完还能干什么如果题目要求进一步输出树高、叶子节点数、最后一层节点数可以在上面的基础上继续扩展。仍然以 1-based 数组为例n 个节点// 树高 int height 0; int temp n; while (temp 0) { height; temp / 2; } // 叶子节点数 // 思路叶子节点就是没有左孩子的节点即 2*i n int leafCount 0; for (int i 1; i n; i) { if (2 * i n) leafCount; } // 最后一层节点数 // 思路最后一层节点 总节点数 - 上面所有层的节点数 // 上面所有层的节点数 2^(height-1) - 1 int lastLevelCount n - ((1 (height - 1)) - 1);这些计算在考场上都是送分操作前提是你对公式足够熟。叶子节点数还有另一个推导方式最后一个非叶子节点下标是 n/2所以叶子节点数就是 n - n/2。比如 n6n/23从下标 4、5、6 开始都是叶子所以叶子数是 3。你对比一下上面的循环会发现结果完全一致但后者一行就搞定。我个人的习惯是能用公式推导的别用循环。考场上的每一分钟都很贵而且循环写多了容易在边界出 bug。平时练习时多训练“从公式到代码”的直觉考试时才能快起来。3.4 层序遍历输出的完整模板如果题目要求按某种顺序输出节点值核心就是利用父子下标关系做递归或队列遍历。下面给一个最常用的层序遍历模板用队列实现时间复杂度 O(n)空间复杂度 O(n)。#include bits/stdc.h using namespace std; const int MAXN 100005; int tree[MAXN]; void levelOrder(int n) { queueint q; q.push(1); // 根节点下标 while (!q.empty()) { int idx q.front(); q.pop(); cout tree[idx] ; if (2 * idx n) q.push(2 * idx); // 左孩子 if (2 * idx 1 n) q.push(2 * idx 1); // 右孩子 } } int main() { int n; cin n; for (int i 1; i n; i) cin tree[i]; levelOrder(n); return 0; }这里有个细节值得注意入队时不需要判断节点值是否为空因为数组下标能落在 [1, n] 范围内就说明这个位置一定有节点。层序遍历顺序天然就是数组下标从小到大的顺序所以用队列是杀鸡用牛刀——直接 for 循环输出 tree[1] 到 tree[n] 效果一样。但这题的进阶版本可能要求前序/中序/后序输出那递归就是你躲不掉的了。3.5 递归遍历的三种写法前序/中序/后序以数组存储的完全二叉树递归遍历同样是靠下标关系游走。下面给出前序遍历模板中序和后序只是调整输出语句的位置。void preorder(int idx, int n) { if (idx n) return; cout tree[idx] ; // 前序先访问根 preorder(2 * idx, n); // 再左子树 preorder(2 * idx 1, n); // 最后右子树 }如果把输出语句放在两行递归调用中间就是中序遍历放在两个递归调用之后就是后序遍历。这里我要提醒一个六级考生最容易犯的错一定不要忘了递归出口 if (idx n) return;。数组存储的树没有指针判断“这个节点是否存在”的方式就是检查下标是否越界。丢了这一行程序直接数组越界轻则乱码重则 RE。4. 考场上最容易踩的五个坑我帮你一个个排掉4.1 数组越界的隐藏触发点完全二叉树的数组存储理论上节点数最多到 2^k - 1 个但题目给的 n 再大也得给数组开够。有些同学为了省空间开 vector tree(n5)结果递归时 2idx1 会不会超过这个 n5完全可能。因为你的 idx 会走到最后一个非叶子节点它的右孩子下标可能是 2(n/2)1这个值在 n 不大时没问题但如果 n 是 2 的幂减 1那最后一个非叶子节点的右孩子正好是 n没问题但如果是其他情况比如 n6最后一个非叶子节点是下标 3它的右孩子是 7而 7 6这个位置根本不存在。所以数组大小必须开成最大节点数的两倍以上如果题目明确说 n ≤ 10^5那就开 2*n5 甚至更大别卡着边界开。我见过太多考生因为这种低级错误在 T2 上丢掉 AC非常可惜。4.2 下标从 0 还是从 1必须从头到尾统一这是完全二叉树题目的第一大坑。题目如果是给数组大概率是从 1 开始输入因为层序遍历编号天然从 1 开始但有的题目为了迷惑你会从 0 开始给输入。如果你用 1-based 的公式去做 0-based 的输入所有下标全部错位后面全盘皆输。我的习惯是读入之前先看题目样例。如果样例里根节点对应的值是数组第一个值那就直接把所有下标减 1然后统一用 0-based 公式左孩子 2i1右孩子 2i2父节点 (i-1)/2。一旦选定所有函数、循环、递归都要用同一套公式中途混用必炸。4.3 用 cin 读大数据导致超时GESP 六级的 T2节点数 n 经常会到 10^5 甚至 10^6 级别。这时候如果你用 cin tree[i] 一个个读不开任何优化大概率超时。这不是算法问题是 IO 问题。解决办法有两个二选一即可// 解决办法1关同步最省事 ios::sync_with_stdio(false); cin.tie(0); // 解决办法2直接上 scanf for (int i 1; i n; i) { scanf(%d, tree[i]); }如果你用的是 cin记得把这两行加在 main 函数开头。如果你追求极致性能直接按 scanf 处理。刷题量上来之后你会发现这种 IO 优化是刻在肌肉记忆里的。4.4 递归层数过深导致栈溢出完全二叉树的树高是 O(log n)理论上递归是安全的。但如果你写的递归不是按完全二叉树的层序方向走而是走了某种链状的路径比如查找某个节点的父节点一直往上循环那最坏情况下会退化成 O(n) 的递归深度。比如 n10^5递归深度 10^5在很多系统上会爆栈。应对方案如果必须递归可以考虑在 main 函数开头加一句 _GLIBCXX_MAKE_LIMITS 或者 visual studio 里用 setrlimit 之类的系统调用但考场环境通常不允许你改栈空间。更稳的做法是把递归改成循环。完全二叉树的结构很适合用循环操作因为下标关系就在那儿摆着。4.5 判断“完全”时用错特征有些同学判断完全二叉树的思路是“每一层节点数是否等于 2 的幂”但这只适用于满二叉树。完全二叉树只有最后一层可以不满而且最后一层的节点必须靠左连续。如果你用“每层满不满”来判断遇到 n4 的完全二叉树形状是根的两个孩子都在最后一层左边那个孩子也在就会被误判因为它不是每一层都满的。正确思路就是我前面讲的层序遍历遇到空节点之后后面不能再出现非空节点。这个特征既准确又容易实现。5. 备考完全二叉树建议按这个顺序刷题5.1 从 GESP 考纲出发先掌握数组建树六级的考试范围里树这个章节的要求是“掌握二叉树的存储、遍历理解完全二叉树与满二叉树的区别”。按我的经验备考顺序应该是先熟练掌握数组下标方式存储完全二叉树并背下四个核心公式用三个典型题练手层序遍历输出、判断是否是完全二叉树、求树高/叶子数/最后一层节点数再做两个拓展题用完全二叉树实现一个小根堆堆的插入和删除、求两个节点的最近公共祖先最后把递归遍历前序/中序/后序和层序遍历都写熟你需要警惕一种情况只会背代码不理解公式的推导。考场上只要题目换个马甲比如不是让你输出节点值而是让你计算某个节点的深度你就容易懵。所以平时练习时每写一个公式都要问自己一句“为什么是这个”把推导过程在草稿纸上过一遍。5.2 推荐按这个优先级刷题GESP 2023 年至 2025 年的历年真题这是最贴近考纲的练习材料优先刷洛谷 P4913 【深基16.例3】二叉树深度适合入门热身洛谷 P1364 医院设置稍微绕一点锻炼建树能力AcWing 846 树的重心虽然不是完全二叉树但能练树的 DFS 基本功力扣 222 完全二叉树的节点个数这题虽然是 LeetCode 风格但思路对 GESP 很有帮助力扣 958 二叉树的完全性检验直接对应判断完全二叉树刷题口诀先模拟再变形先看题解再独立写写完后把核心公式抄到错题本上考前半小时翻一遍。我见过不少学生刷题时喜欢直接看题解看完觉得自己会了一考就废。正确做法是拿到题先自己画图把样例推一遍然后动手写卡住了再看题解看完把代码关掉重新写一遍。这个过程很痛苦但效果立竿见影。6. 5 分钟默写模板考场直接起飞6.1 核心代码速查表下面是完全二叉树最常用的代码片段剪贴到你的“考前模板”里考前默写两遍考场直接套用。// 树高 int getHeight(int n) { int h 0; while (n 0) { n / 2; h; } return h; } // 叶子节点数1-based int getLeafCount(int n) { return n - n / 2; } // 判断是否是完全二叉树层序遍历 空标记 bool isComplete(vectorint tree, int n) { bool hasEmpty false; for (int i 1; i n; i) { if (tree[i] -1) hasEmpty true; else if (hasEmpty) return false; } return true; } // 前序遍历数组存储1-based void preorder(int idx, int n, vectorint tree) { if (idx n) return; cout tree[idx] ; preorder(idx * 2, n, tree); preorder(idx * 2 1, n, tree); } // 层序遍历队列 void levelOrder(int n, vectorint tree) { queueint q; q.push(1); while (!q.empty()) { int idx q.front(); q.pop(); cout tree[idx] ; if (idx * 2 n) q.push(idx * 2); if (idx * 2 1 n) q.push(idx * 2 1); } }这个模板大概三十行考前花 5 分钟默写一遍考场心里就有底了。6.2 考场时间分配建议GESP 六级总共两个半小时T1 一般是最基础的题建议 20 分钟内解决T2 这种套路题建议控制在 40 分钟内包括读题、写代码、测试样例剩下的时间留给 T3 和检查。如果 T2 在 30 分钟内还没头绪先跳过做 T3 的大题后面再回来补。很多学生栽在“死磕一道题”这个陷阱里T3 明明有部分分可以拿结果时间全耗在 T2 上最后两边都没做好。我的经验是T2 的完全二叉树题难度上限基本就是“判断 遍历 基础计算”不会出到建树旋转那种程度。所以只要公式背熟模板写顺拿满分是大概率事件。7. 写在最后的个人建议我这些年带过不少备考 GESP 六级的学生发现一个规律能在完全二叉树上拿满分的孩子不是智商多高而是愿意花时间把基础数据结构的基本功打牢。他们会在草稿纸上画很多棵树会手动模拟数组下标会把公式从头推导一遍——这些“笨功夫”才是考场上最可靠的东西。这道 T2 真正想考验的不只是你会不会做这一道题而是你有没有建立起“用数组思维去理解树形结构”的能力。这种能力在后面的七级、八级考试里还会反复出现尤其是堆、线段树、树状数组这些进阶数据结构全都要用到完全二叉树的数组存储思想。如果你现在做题还有些吃力别着急。把本文的公式抄在纸上把模板默写两遍再找两三道真题练手一两个星期内会有明显提升。祝你在 2026 年 3 月的考场上稳稳拿下这道 T2。
