写在前面前面的二叉树专题中我们已经完成了链式二叉树的基础结构、前中后序递归遍历、层序遍历、结点统计、树高度、递归建树、结点查找以及二叉树销毁等全套基础接口。其中之前实现的层序遍历使用的是数组模拟队列void BinaryTreeLevelOrder(BTNode* root);它可以正确完成遍历但层序遍历本质上就是非常典型的BFS广度优先搜索问题而 BFS 最天然的载体正是队列。因此本篇在原有工程基础上扩展两个新接口// 链式队列实现 BFS 层序遍历 void BinaryTreeLevelOrderBfs(BTNode* root); // 判断二叉树是否为完全二叉树 bool BinaryTreeComplete(BTNode* root);同时直接复用之前实现的链式队列模块仅将队列存储的数据类型从整数调整为BTNode*二叉树结点指针。原有全部基础接口保持不动仅新增功能。除代码实现外本篇还会推导二叉树经典性质并结合完全二叉树的约束解决两道经典结点计数选择题。一、层序遍历1.1 为什么层序遍历天然适配队列以一棵满二叉树为例A / \ B C / \ / \ D E F G层序遍历要求的访问顺序为A B C D E F G。和前/中/后序遍历「沿着一条路径往深处钻」的逻辑不同层序遍历的核心是先处理完整的一层再由当前层的结点带出下一层。例如第1层A A处理完成 → 把B、C加入待处理序列 第2层B C B处理完成 → 加入D、E C处理完成 → 加入F、G 第3层D E F G执行过程天然满足「先加入的结点先处理」的FIFO先进先出规则而这正是队列的核心特性。1.2 BFS层序遍历的完整执行流程仍以上述满二叉树为例完整走一遍BFS流程A / \ B C / \ / \ D E F G初始状态根结点A入队队列[ A ]第一步处理结点 A队头A出队打印值再将 A 的左孩子B、右孩子C依次入队。输出A 队列[ B C ]第二步处理结点 B队头B出队打印值再将 B 的左孩子D、右孩子E依次入队。输出A B 队列[ C D E ]第三步处理结点 C队头C出队打印值再将 C 的左孩子F、右孩子G依次入队。输出A B C 队列[ D E F G ]第四步处理叶子结点D、E、F、G 依次出队打印均无孩子队列为空时遍历结束。最终输出A B C D E F GBFS核心框架根入队 → 队列非空则循环 → 取队头访问 → 左孩子入队 → 右孩子入队。1.3 复用已有的链式队列模块本次没有重新实现队列而是直接复用之前写好的链式Queue模块——数据结构的学习本就是前后复用、层层递进的。队列主体逻辑完全不用改仅需修改存储的数据类型原队列存整数typedef int QDataType;BFS需要存结点地址改为typedef BTNode* QDataType;压入队列的是BTNode*QueueFront()返回的也是BTNode当前Queue.h就是通过包含BinaryTree.h把QDataType重定义为了BTNode*而队列结点、front、rear、size等结构保持原来的链式队列设计。因此原来的接口全部可以直接使用void QueueInit(Queue* q); void QueuePush(Queue* q, QDataType data); void QueuePop(Queue* q); QDataType QueueFront(Queue* q); int QueueEmpty(Queue* q); void QueueDestroy(Queue* q);1.4 链式队列版 BFS 层序遍历完整实现代码// 层序遍历链式队列实现 BFS void BinaryTreeLevelOrderBfs(BTNode* root) { Queue q; QueueInit(q); // 根结点非空则入队 if (root ! NULL) { QueuePush(q, root); } while (!QueueEmpty(q)) { // 取出队头结点并出队 BTNode* front QueueFront(q); QueuePop(q); // 访问当前结点 printf(%c , front-data); // 左孩子非空则入队 if (front-left ! NULL) { QueuePush(q, front-left); } // 右孩子非空则入队 if (front-right ! NULL) { QueuePush(q, front-right); } } // 遍历结束销毁队列释放内存 QueueDestroy(q); }1.4.1 关键点1队列存储的是结点指针队列里保存的是BTNode*而非结点值BTDataType。原因很简单后续不仅要访问front-data还要通过front-left、front-right找到子结点只存值会丢失树的结构关系。1.4.2 关键点2上层结点自然带出下层当前结点出队时if (front-left ! NULL) { QueuePush(q, front-left); } if (front-right ! NULL) { QueuePush(q, front-right); }它会自然地把下一层结点补到队尾于是当前层正在不断从队头出去下一层正在不断从队尾进来最终就形成了一层一层向下扩展的遍历效果。1.5 数组模拟队列 vs 链式队列BFS上一篇其实已经实现过void BinaryTreeLevelOrder(BTNode* root);它先统计二叉树结点总数再动态申请一个BTNode**数组通过front rear两个下标模拟队列当前原实现仍然保留在工程中。两种实现本质都是BFS思想仅底层队列载体不同对比如下实现函数底层实现特点BinaryTreeLevelOrder动态数组 front/rear下标模拟内存连续需提前统计结点总数BinaryTreeLevelOrderBfs复用链式Queue模块逻辑解耦专注BFS流程无需管理下标学习BFS思想时更推荐直接复用队列模块代码语义更清晰。二、拓展如何判断完全二叉树2.1 完全二叉树定义高度为h的二叉树前h-1层全部排满最后一层结点从左到右连续排列中间不能出现空缺。例如A 是完全二叉树 / \ B C / \ / D E FA 不是完全二叉树 / \ B C \ / E F第二个例子中最后一层先出现空位、后又出现结点不符合「从左到右连续」的要求。2.2 完全二叉树判断的核心思路普通BFS只把非空孩子入队但判断完全二叉树时空位置本身就是判断依据。所以这一次QueuePush(q, front-left); QueuePush(q, front-right);无论左右孩子是否为空全部入队保留完整的位置信息。例如A / \ B C / \ / D E F按照包含空结点的层序顺序会逐渐出现A B C D E F N N N N N N N一旦第一次遇到N那么按照完全二叉树的特点后面应该全部都是 N。只要后面再次出现非空结点就说明已经有空位如果后面却还有有效结点不符合“最后一层从左向右连续”的要求。所以判断规则为第一次遇到空结点后后续所有位置必须全部为空如果再出现非空结点则一定不是完全二叉树。2.3 两种理解视角视角1两阶段法第一阶段不断出队非空结点直到第一次遇到NULL第二阶段继续检查队列剩余元素必须全部为NULL否则判定失败。视角2单循环标记法通过一个布尔变量meetNull记录是否已经遇到空结点遍历过程中实时判断代码更紧凑。本文采用这种实现。2.4 完整实现代码bool BinaryTreeComplete(BTNode* root) { Queue q; QueueInit(q); if (root ! NULL) { QueuePush(q, root); } bool meetNull false; // 标记是否已经遇到空结点 while (!QueueEmpty(q)) { BTNode* front QueueFront(q); QueuePop(q); if (front NULL) { // 遇到空位置标记后续必须全为空 meetNull true; } else { // 前面已经出现空位现在又有有效结点 → 不合法 if (meetNull) { QueueDestroy(q); return false; } // 无论是否为空左右孩子全部入队 QueuePush(q, front-left); QueuePush(q, front-right); } } QueueDestroy(q); return true; }和普通BFS的核心区别场景入队规则关注点普通层序遍历非空孩子才入队有哪些有效结点完全二叉树判断空/非空孩子都入队有效结点之间有没有非法空位2.5 典型场景验证2.5.1 场景1标准完全二叉树A / \ B C / \ / D E F含空位的层序序列A B C D E F N N N N N N N首次遇到N后后续全为空 → 返回true。2.5.2 场景2左空右非空A / \ B C \ E含空位的层序序列A B C N E ...先遇到N后又出现E → 返回false。2.5.3 场景3中间出现空缺A / \ B C / \ D G含空位的层序序列A B C D N N G空位后又出现G → 返回false。2.6 部分问题及其处理与测试2.6.1 空树的边界处理当root NULL时不会向队列插入任何元素循环直接跳过最终返回true。空树在定义上通常视为完全二叉树符合常规约定。2.6.2 测试代码的顺序修正本次在测试代码中新增了BFS和完全性判断这里有一个极易踩的坑所有遍历、查询、判断操作必须全部放在销毁树之前执行。正确顺序创建树 ↓ 前/中/后序遍历 ↓ 结点统计、查找 ↓ BFS层序遍历 ↓ 完全二叉树判断 ↓ 销毁树一旦先执行BinaryTreeDestory(root)结点内存已释放再访问就是非法的野指针操作。2.6.3 数组前序建树的同步测试对BinaryTreeCreate构建的第二棵树也同步补充了BFS遍历和完全性判断测试完成后再销毁保证流程完整。2.6.4 为什么队列模块几乎无需修改因为之前实现链式队列时已经做了标准的接口封装入队、出队、取队头、判空、销毁。底层链表逻辑和上层业务解耦。BFS场景下我们只修改了QDataType的类型定义队列的FIFO特性、接口逻辑完全不变。这正是数据结构封装的意义底层实现一旦稳定后续仅需调整数据类型即可在新场景中复用。三、经典性质(N_0 N_2 1)规定(N_0)度为0的结点数叶子结点(N_1)度为1的结点数(N_2)度为2的结点数对于任意一棵非空二叉树恒有 [ \boxed{N_0 N_2 1} ] 即叶子结点永远比度为2的结点多1个。3. 两种证明方法3.1.1 证明方法一边数推导法整棵二叉树总共有个结点。树有一个非常基本的性质如果一棵树有 N 个结点那么一定有 N - 1 条边。所以二叉树总边数 N-1 。另一方面也可以根据每个结点有几个孩子统计边数。度为 0 的结点贡献 0 条向下边度为 1 的结点贡献 1 条度为 2 的结点贡献 2 条。所以又因为代入两边消去最终证明完成。3.1.2 证明方法二归纳法结点增量视角例如A / B增加A / \ B C变化是A度 1 → 度 2因此新结点 C成为叶子因此。两边同时加 1仍然不变。因此不管二叉树怎样一步步生长始终成立。因此无论二叉树如何生长恒成立。3.2 完全二叉树的附加约束对于完全二叉树由于最后一层结点从左到右连续排列度为1的结点最多只能有1个且只能是「有左孩子、无右孩子」。即结合和可推导出这是解决完全二叉树计数题的核心公式。3.3 两个例题3.3.1 例题12n个结点的完全二叉树题目具有 (2n) 个结点的完全二叉树叶子结点个数为 A. n B. n1 C. n-1 D. n/2已知总节点数 N 2n偶数代入公式左边为偶数又为偶数因此必须为偶数。结合得。代入计算再由得。答案A3.3.2 例题2767个结点的完全二叉树题目具有767个结点的完全二叉树叶子结点个数为多少总节点数767为奇数代入公式由于为奇数因此。计算得所以又因此767 个结点的完全二叉树有 384 个叶子结点。答案3843.4 规律总结完全二叉树叶子结点数可以总结为即叶子结点数等于总结点数的一半向上取整。总结点数为偶数N_11叶子数 N_0 n总结点数为奇数N_10叶子数 N_0 n1当然更推荐先理解和。四、本次工程文件变更汇总文件变更内容Queue.h重定义QDataType为BTNode*使队列支持存储二叉树结点指针BinaryTree.h新增BinaryTreeLevelOrderBfs、BinaryTreeComplete函数声明BinaryTree.c新增链式队列BFS层序遍历、完全二叉树判断两个接口实现BinaryTree_Test.c补充两棵测试树的BFS与完全性测试修正执行顺序所有访问操作先于销毁代码仓库本篇是在已有工程上增量新增功能原有代码全部保留无需删除旧文件、旧接口读者可以直接复用整套工程。修改Queue.h把队列元素类型改为typedef BTNode* QDataType;Queue.c不用改动原有队列接口全部继续可用队列现在可以存放二叉树结点指针。将本篇新增的两个函数声明复制到BinaryTree.h把BinaryTreeLevelOrderBfs、BinaryTreeComplete两份实现追加到BinaryTree.c文件末尾。在BinaryTree_Test.c中在二叉树销毁之前调用新增接口做测试销毁后的空指针不可再传入函数。编译运行即可同时保留旧版数组模拟层序遍历方便读者对比两种 BFS 实现输出结果。提示新增接口完全独立不影响之前写的二叉树遍历、统计、查找、建树、销毁等所有旧功能旧测试代码可以原样运行。同时配套掌握二叉树性质N_0N_21用于快速求解完全二叉树结点计算题。数据结构/BinaryTree_FullVersion · Luminous/Code_2026 - 码云 - 开源中国写在最后今天新增的代码量不多但把之前学过的数据结构真正串了起来链表实现队列队列服务于二叉树BFSBFS稍加改造又能解决完全二叉树判断问题。数据结构从来不是孤立的知识点而是层层复用、彼此支撑的体系。从「写代码实现接口」到「研究结构本身的性质」也是数据结构学习的进阶路径。本篇核心要点回顾层序遍历 BFS 队列BFS队列中存储的是BTNode*结点指针而非单纯的值判断完全二叉树时NULL也要入队空位置本身就是判断依据首次遇到空位置后再出现非空结点 → 一定不是完全二叉树任意非空二叉树完全二叉树附加约束。理解这些核心逻辑后绝大多数完全二叉树的判断、计数题都可以从定义直接推导无需死记硬背。