★ FEATURED ARTICLE 1. 项目概述这道GESP六级“完全二叉树”题目到底在考什么看到“P15801 [GESP202603 六级] 完全二叉树”这个标题很多人的第一反应是“又要写指针建树了”。实际上这类题目考的根本不是让你把树建出来而是考你对完全二叉树编号规律的熟练程度。GESP六级阶段二叉树是核心考点之一而完全二叉树作为其中最有“数学规律”的一种形态几乎是必练题型。它适合正在备考六级、或者刚学完树结构想巩固基础的人来刷一刷尤其是那种“公式想一想就出来代码一写才发现全是边界坑”的题目最能拉开差距。这类题的核心价值在于让你用数组下标去理解树。节点编号从1开始父节点、左右孩子的下标都能直接算出来不需要指针不需要递归遍历甚至连建树都不需要。很多同学第一次接触这个概念时很不适应总觉得“树”就应该是带有left指针和right指针的结构体但实际做题时你会发现完全二叉树用顺序存储效率和简洁度都远高于链式存储。这篇文章我把这道题背后的考点、常数公式、完整的代码实现、常见的边界坑全部拆开讲一遍希望能帮你把“看到完全二叉树就能条件反射列出公式”这个能力练到位。1.1 考点定位不是考定义是考“编号换算”完全二叉树的定义本身很简单除了最后一层之外每一层的节点都是满的最后一层的节点从左到右连续排列中间不能有空缺。这个“连续”二字就是整道题的核心。正因为节点连续排布层序编号才能和数组下标一一对应。如果中间缺了一个节点所有编号规律立刻失效那就不叫完全二叉树了。但GESP六级不会只满足于“你知不知道定义”它更看重的是你能不能基于定义推出一系列换算关系。常见的出题角度包括已知某个节点的编号x求它的父节点编号、左孩子编号、右孩子编号已知编号x求它所在的深度层数判断某个编号对应的节点是否存在输出从根节点到x的路径上的节点序列统计某一层有多少个节点判断某个节点是不是叶子节点找出最后一个非叶子节点编号也就是建堆时调整的起点。这些操作有一个共同特点全部可以通过算术运算完成完全不需要建树。我见过很多同学一拿到题就开始写Node* root new Node(1);然后一层一层往下挂节点其实完全没必要。整个数据结构就是一张数组下标就是节点编号所有操作都在下标上完成。1.2 命题倾向模板背得再熟边界条件才是分水岭GESP六级的命题风格并不会给你一道“背诵模板”就能过的题。它经常把一个你熟悉的知识点稍微包装一下然后在数据范围和边界条件上做文章。就拿完全二叉树来说节点总数N可能很大询问次数Q也可能很大如果你的程序每次询问都要递归遍历整棵树复杂度就会爆炸但如果掌握了编号规律单次询问只需要O(log N)甚至O(1)的时间。更关键的是边界情况。比如求左孩子编号时直接写2 * x当x很大时可能溢出int判断“右孩子是否存在”时很多人下意识认为“有左孩子就一定有右孩子”这在满二叉树里成立但在完全二叉树里不成立因为最后一层可能不满倒数第二层的最后一个节点可能只有左孩子没有右孩子。这些细节比“会不会写递归建树”更能检验一个人的真实水平。2. 核心规律拆解完全二叉树为什么可以“用编号说话”要把这道题彻底吃透必须先掌握几个核心公式。它们不复杂但每个都需要知道来源而不是死记硬背。2.1 链式存储和顺序存储谁更适合完全二叉树先做一组对比。链式存储就是经典的结构体加指针每个节点保存自己的数据、左孩子指针、右孩子指针顺序存储则是用一个一维数组按层序编号数组下标就是节点编号数组元素就是节点数据。对比维度链式存储顺序存储空间开销每个节点额外存储2个指针内存浪费明显只需要一个数组几乎没有额外开销找父节点需要从根遍历或存parent指针直接除以2O(1)找孩子节点直接访问指针O(1)下标乘2或乘2加1O(1)建树复杂度需要逐层创建节点代码量大直接读入数组即可适用场景任意形态的二叉树完全二叉树、满二叉树从表格可以直观看出对于完全二叉树顺序存储是“性价比之王”。为什么非完全二叉树不适合顺序存储因为一旦中间有空缺你没法保证某个编号对应的数组位置一定存放着有效节点空间会出现大量空洞。而完全二叉树的“连续排列”性质恰好保证了编号1到N全部有效所以数组空间能完美利用。这道题既然明确说了是完全二叉树那你的思维就应该自动切到顺序存储而不是一上来就new节点。2.2 父子节点编号公式从层序排列推出来的结论假设根节点编号为1按层从左到右编号。节点k的左孩子编号为什么是2k右孩子编号为什么是2k1我建议你在理解的基础上记忆。第h层根节点所在层记为第1层最多有2^(h-1)个节点。前h层节点总数是2^h - 1。考虑一个节点k它所在层的前缀节点数量决定了它的孩子会在编号区间中落到什么位置。简单推导的方法是在一棵完全二叉树中如果一个节点在数组里的编号是k那么它前面的所有节点都先于它进入下一层而每个节点最多贡献2个孩子所以它第一个孩子的位置往前推到根就是2k。右孩子紧接着左孩子所以是2k1。这个结论我用一组小数据验证过第2层的节点编号是2和3它们的左孩子分别是4和6右孩子分别是5和7完全符合2k和2k1。父节点公式反过来就是k的一半向下取整也就是k/2或者写成k 1。这里要注意C/C的整数除法本身就是向下取整所以直接写k / 2是完全正确的。如果你从二进制角度来看规律更漂亮。把节点编号x写成二进制它的父节点就是去掉二进制最低位比如7的二进制是111右移一位变成11对应3父节点正是3。左孩子是在末尾补一个0右孩子是在末尾补一个1。进一步来说从根节点1出发到节点xx的二进制表示几乎就是整条路径的“导航”从左到右逐位读0代表去左孩子1代表去右孩子。这个视角在后面理解树状数组、倍增法时也会反复出现。2.3 深度、层数、叶子判断、某层节点数一套公式直接拿下先约定根的深度为1。那么节点x的深度就是floor(log2(x)) 1。C里可以直接用循环int depth 0; int t x; while (t 0) { depth; t 1; }这段代码的本质就是数x的二进制位数。6的二进制是1103位所以深度为3。如果你喜欢用内置函数__builtin_clz(x)可以算出前导0的个数那么深度就是31 - __builtin_clz(x) 1等价于32 - __builtin_clz(x)。这个写法更快但要注意x必须大于0。判断节点x有没有左孩子就是看2 * x是否小于等于N判断有没有右孩子就看2 * x 1是否小于等于N。如果左孩子都不存在那x一定是叶子节点。这里要特别强调完全二叉树中左孩子存在但右孩子不存在是完全合法的情况。比如N6时节点3有左孩子6但没有右孩子因为节点6就是整棵树的最后一个节点了。求第k层有多少个节点也是一道常考小题。如果k大于整棵树的最大深度直接输出0否则第k层理论上最多有2^(k-1)个节点但最后一层可能不满所以实际节点数是min(2^(k-1), N - 2^(k-1) 1)。注意这里2^(k-1)是理论上的该层起点之前的节点总数N - 2^(k-1) 1表示从该层起点开始到最后一个节点一共还剩多少节点。两层含义要搞清楚不然这个公式很容易记混。还有一个高频实用结论N / 2整数除法就是整棵完全二叉树中最后一个非叶子节点的编号。这个结论在建堆操作中极其重要因为调整堆的时候就是从最后一个非叶子节点开始往前调整。比如N7时最后一个非叶子节点是3N6时最后一个非叶子节点也是3节点4到6全是叶子。3. 实战从一个典型题目看完整解题过程规律掌握之后下一步就是把它们组合起来解决一道完整的题目。我在这里设计一个非常典型的完全二叉树综合题基本覆盖了GESP六级最常见的几个考查点。3.1 题目设定一次询问要同时完成三件事假设题目是这样的给定一棵有N个节点的完全二叉树节点按层序编号1到N。有Q次询问每次询问给一个编号x要求输出三部分信息节点x的深度根节点深度为1节点x的左孩子编号和右孩子编号如果某个孩子不存在输出-1从根节点1到节点x的完整路径按从根到x的顺序输出节点编号。这个问题的好处在于它同时考察了深度计算、孩子判断、路径回溯三个能力。而且路径回溯正好能帮你理解“父节点是编号除以2”这个公式的另一种用法从x一路除以2就能反向走到根。3.2 解题思路与复杂度分析我的思路很简单先读入N和Q然后对每次询问单独计算。计算深度时不需要从根往下找直接对x做右移操作每移一次深度加1直到x变成0。这个操作实际上就是统计x的二进制位数。计算孩子时注意两点一是要用更大的数据类型来保存2 * x防止溢出二是需要同时判断左孩子和右孩子是否存在。计算路径时可以先把路径逆序收集下来从x开始每次把当前节点存入数组然后x除以2循环直到x为0。这样得到的是从x到根的倒序路径最后把数组反转一下就能按从根到x的顺序输出。整个过程不需要递归不需要建树非常直接。复杂度方面每次询问的路径长度等于该节点深度而完全二叉树的深度是O(log N)所以单次询问时间复杂度是O(log N)。如果N是10^9log N也只有30左右速度非常快。即使Q达到10^5总操作量也只有几百万次轻松跑完。3.3 完整C实现与注释#include bits/stdc.h using namespace std; int main() { ios::sync_with_stdio(false); cin.tie(nullptr); int n, q; cin n q; while (q--) { int x; cin x; // 题目保证询问的x一定在1到N之间但写一个防御性判断没有坏处 if (x 1 || x n) { cout invalid\n; continue; } // 1. 计算深度根节点深度为1等价于统计x的二进制位数 int depth 0; int t x; while (t 0) { depth; t 1; } cout depth depth \n; // 2. 计算左右孩子编号用long long防止2*x溢出 long long left 2LL * x; long long right left 1; cout left (left n ? to_string(left) : -1) right (right n ? to_string(right) : -1) \n; // 3. 收集从x到根的路径再反转成从根到x vectorint path; for (int cur x; cur 0; cur 1) { path.push_back(cur); } reverse(path.begin(), path.end()); cout path; for (size_t i 0; i path.size(); i) { if (i) cout ; cout path[i]; } cout \n; } return 0; }这段代码里的几个细节值得再展开一下。首先是2LL * x这个写法比2 * x更安全。因为2默认是int类型两个int相乘在int范围内计算如果x接近10^9级别结果可能超过int上限出现未定义行为。写成2LL就把第一个操作数变成了long long整个表达式自动提升为long long安全得多。我在实际排查类似题目时见过不只一个同学在这里被坑。其次是路径收集时用的循环条件cur 0。因为根节点编号为1循环内先push当前节点再右移所以当cur从x一路变成1后下一次右移变成0循环结束。这样路径数组里天然包含了根节点1不需要额外补。如果你不喜欢用vector也可以先计算路径长度其实就是深度depth倒着填数组。不过vector加reverse已经足够清晰性能在竞赛环境下也完全够用。4. 常见问题与调试技巧这些坑我替你们踩过任何题目思路对了只是第一步边界条件和细节实现才是真正消耗时间的地方。这里我整理出几个高频问题每一个都是真实比赛中容易翻车的点。4.1 孩子编号越界先判断再访问还是直接算完再判断这是最常错的一个点。有些同学会这样写if (x * 2 n) cout x * 2; else cout -1;看起来没问题但x * 2很可能在计算时就溢出了。比如x是2,000,000,000那么x*2已经超过int的表示范围变成一个负数再拿去和n比较结果完全不可预测。我建议在思维上建立两个习惯。第一涉及“某个数的两倍”时一律用long long或先转换为long long再计算。第二也可以利用等价的比较式x n / 2来判断左孩子是否存在这样完全避开了乘法溢出风险。对于右孩子等价判断是x (n - 1) / 2。两种写法都可以我在现场解题时更倾向于用long long方案因为它的含义更直观不容易把等价不等式推错。值得提醒的是有左孩子不代表有右孩子这个结论很多人会在调试时才发现。参考下面这个表当N6时节点3只有左孩子6没有右孩子这在完全二叉树中是完全正常的。N节点编号左孩子右孩子11无无32454245536无636无73674.2 深度到底从0开始还是从1开始先看样例再写代码深度这个定义在不同题目里可能不同。有的题按“边数”计算根节点深度为0有的题按“节点数”计算根节点深度为1。如果你不做任何确认就套用公式很容易整个方向都错了。在GESP这类竞赛题中最常见的说法是“根节点深度为1”但遇到题还是要先看样例。如果样例中节点1的深度是1那公式就是floor(log2(x)) 1如果根深度是0那公式就是floor(log2(x))。差的就是一个1但结果完全不同。我的习惯是读题后先用自己的公式口算一下样例如果对不上就立刻检查定义而不是等到交完代码才发现。4.3 输入输出与性能不要小看IO开销完全二叉树类题目N和Q的数据范围经常到10^5甚至10^6。如果使用cin和cout请务必加上ios::sync_with_stdio(false); cin.tie(nullptr);否则同步缓冲区带来的开销可能让你的程序在边界数据上超时。除此之外输出路径时不要在循环里反复进行字符串拼接直接先用vector收集所有节点再用空格分隔输出这个习惯能避免很多不必要的性能损耗和格式错误。4.4 自制小数据验证比盲测更靠谱的调试方法刷题过程中我特别推荐“画图验证”这种方法。每遇到一个不确定的边界就把N取几个特殊值然后手算几个节点找规律。这里列出几组我常用的关键测试数据N1整棵树只有根节点深度1无孩子路径只有1。N2节点1有左孩子2没有右孩子。N3节点1两个孩子都有节点2和3是叶子。N6注意节点3只有左孩子。N7树是最后一层也满的情况等于一棵满二叉树。N8最后一层只有1个节点节点4是最后一个非叶子节点它的左孩子是8。用这些小规模数据跑一遍你的程序任何深度计算错误、孩子判断错误、路径顺序颠倒问题都会立刻暴露。尤其是N6这一组专门用来检验你是否正确处理了“有左无右”的特殊情况。5. 经验扩展把这道题的思维方式带到后面的数据结构学习中完全二叉树的下标规律绝不只是为了应付这一道题。它是一套系统性的思维模型后续学堆、学线段树、学树状数组你会发现底层都在反复使用“数组下标模拟树结构”和“二进制位操作”这两件事。5.1 从完全二叉树到二叉堆和优先队列二叉堆的经典存储方式就是用一个数组模拟完全二叉树而且规定的正是根节点下标为1。建堆时从N/2开始向下调整这个起始位置就是上一节提到的“最后一个非叶子节点”。如果你现在就把N/2这个结论理解透将来学堆排序时会节省大量时间。优先队列的内部实现通常是二叉堆往堆里插入元素、删除堆顶元素本质上就是不断比较父节点和孩子节点的下标关系并交换数组中的元素。很多初学者觉得明白这个道理但一到代码就犯迷糊根本原因就是对下标规律不够熟。反过来如果你能把这道完全二叉树题吃透堆的插入和删除操作可以说几乎是“白给的”。5.2 从层序编号到线段树与树状数组线段树用数组模拟的并不是严格意义上的完全二叉树但它同样依赖“父节点下标是k左孩子是2k右孩子是2k1”的存储方式。这也是为什么线段树通常要开4倍数组空间因为当区间划分不平衡时部分编号会出现空洞必须预留足够的空间避免越界。理解了完全二叉树的编号规律再去看线段树的代码很多“为什么开4N”的困惑会迎刃而解。树状数组则把二进制视角发挥到了极致。它的核心操作lowbit(x)本质上就是提取x二进制的最低位的1。你看完全二叉树路径可以通过二进制逐位判断树状数组通过二进制位来划分区间两者都是同一个思想在不同场景下的应用。这种“二进制拆解”的思路在动态规划的状态压缩、倍增法求LCA等问题中也会反复出现。5.3 学习建议先手写推导再上机验证如果这篇文章读到这里你想亲手练一练我建议不要急着打开编辑器写代码。先把N1到N12的完全二叉树画在草稿纸上手动填上编号然后选择一个节点比如7自己在纸上推它的父节点、左右孩子、深度、从根到它的路径换一个节点再推一遍。等你对公式和编号规律形成肌肉记忆之后再回到代码里实现速度会快很多。做完这道题你再去做那些基于完全二叉树变形的题就会发现所谓的“新题”只是把几个基本操作重新组合了一遍。比如求某层的节点区间、判断两个节点是否是兄弟、找最近公共祖先基本都能通过下标运算解决。我个人在实际刷题中的体会是这类题的收获远不止AC本身它更像是一次“把树还原成数组、把数组还原成二进制”的思维训练这种东西在后面的算法学习中会持续复用。
阅读完成 · 觉得有帮助？
