PTA数据结构实战：层次遍历巧解二叉树叶结点输出

1. 从问题理解到解题思路第一次看到PTA上这道二叉树题目时我也被题目描述唬住了。题目要求按从上到下、从左到右的顺序输出所有叶结点这不就是典型的层次遍历BFS应用场景吗但仔细分析输入格式后我发现有几个关键点需要注意输入格式中每个结点的左右孩子是用字符-表示的这意味着我们需要处理字符到数字的转换。另外题目给出的结点编号是从0开始的连续整数这提示我们可以用静态数组来存储树结构既节省空间又方便查找。在实际解题时我总结出三个关键步骤从输入数据中找到根节点根据输入数据构建二叉树使用层次遍历找出所有叶结点这种分步解决的方法把一个大问题拆解成几个小问题每个小问题都有明确的解决思路大大降低了编码难度。这也是我在数据结构学习中总结出的重要经验——化整为零逐个击破。2. 静态数组存储与根节点查找技巧在处理树的输入数据时我发现一个很实用的技巧用标记数组找根节点。因为除了根节点外其他所有节点都会作为某个节点的孩子出现。基于这个观察我们可以创建一个长度为N的标记数组初始值全为0。具体实现时我遍历每个节点的左右孩子如果孩子存在不是-就把对应下标的标记数组位置设为1。最后标记数组中仍为0的位置就是根节点的编号。这个方法的时间复杂度是O(N)非常高效。int FindHead(ThreeArr TArr[], int n) { if (n 1) return 0; int Arr[n]; for(int i 0; i n; i) { Arr[i] 0; } for(int i 0; i n; i) { if(TArr[i].LNode ! -) { Arr[TArr[i].LNode-0] 1; } if(TArr[i].RNode ! -) { Arr[TArr[i].RNode-0] 1; } } for(int i 0; i n; i) { if(Arr[i] 0) { return i; } } return -1; // 理论上不会执行到这里 }这里有个细节需要注意字符0到9的ASCII码是连续的所以可以用child-0的方式将字符转换为数字。这个小技巧在处理字符型数字输入时非常实用。3. 递归构建二叉树找到根节点后接下来就是构建二叉树。我采用了递归方法因为递归的思路最符合树结构的本质特性。每个节点的构建过程都是相同的创建节点然后递归创建其左右子树。TreeNode *BuildTree(int head, ThreeArr TArr[]) { TreeNode *T (TreeNode *)malloc(sizeof(TreeNode)); T-val head; T-right T-left NULL; if(TArr[head].LNode ! -) T-left BuildTree(TArr[head].LNode - 0, TArr); if(TArr[head].RNode ! -) T-right BuildTree(TArr[head].RNode - 0, TArr); return T; }在实际编码时我犯过一个错误忘记处理孩子为-的情况导致程序访问非法内存。这个教训让我明白边界条件的检查在树结构操作中尤为重要。递归虽然简洁但必须确保有明确的终止条件否则很容易导致栈溢出。4. 层次遍历实现与叶结点判断题目要求按从上到下、从左到右的顺序输出叶结点这正是**层次遍历BFS**的典型应用。与深度优先搜索DFS不同BFS需要使用队列来辅助实现。我的实现思路是将根节点入队循环直到队列为空出队一个节点检查是否是叶结点左右孩子都为空将非空左右孩子入队void LevelOrder(TreeNode *T) { int flag 0; if(T) { TreeNode *queue[100]; int left 0, right 0; queue[right] T; while (left right) { TreeNode *bt queue[left]; if(bt-left NULL bt-right NULL) { if(flag 0) { printf(%d, bt-val); flag; } else { printf( %d, bt-val); } } if(bt-left) queue[right] bt-left; if(bt-right) queue[right] bt-right; } } }这里有个输出格式的小技巧使用flag变量控制空格的输出确保第一个数字前和最后一个数字后没有多余空格。这种细节处理在PTA等在线评测系统中非常重要可能决定你的代码是否能通过所有测试用例。5. 完整代码实现与测试将上述各个部分组合起来就得到了完整的解决方案。为了验证代码的正确性我用题目给出的样例进行了测试输入8 1 - - - 0 - 2 7 - - - - 5 - 4 6输出4 1 5这个结果与题目给出的样例输出一致说明我们的实现是正确的。完整的代码如下#include stdio.h #include stdlib.h typedef struct TreeNode { int val; struct TreeNode *left; struct TreeNode *right; } TreeNode; typedef struct ThreeArr { char LNode; char RNode; } ThreeArr; int FindHead(ThreeArr TArr[], int n) { if (n 1) return 0; int Arr[n]; for(int i 0; i n; i) { Arr[i] 0; } for(int i 0; i n; i) { if(TArr[i].LNode ! -) { Arr[TArr[i].LNode-0] 1; } if(TArr[i].RNode ! -) { Arr[TArr[i].RNode-0] 1; } } for(int i 0; i n; i) { if(Arr[i] 0) { return i; } } return -1; } TreeNode *BuildTree(int head, ThreeArr TArr[]) { TreeNode *T (TreeNode *)malloc(sizeof(TreeNode)); T-val head; T-right T-left NULL; if(TArr[head].LNode ! -) T-left BuildTree(TArr[head].LNode - 0, TArr); if(TArr[head].RNode ! -) T-right BuildTree(TArr[head].RNode - 0, TArr); return T; } void LevelOrder(TreeNode *T) { int flag 0; if(T) { TreeNode *queue[100]; int left 0, right 0; queue[right] T; while (left right) { TreeNode *bt queue[left]; if(bt-left NULL bt-right NULL) { if(flag 0) { printf(%d, bt-val); flag; } else { printf( %d, bt-val); } } if(bt-left) queue[right] bt-left; if(bt-right) queue[right] bt-right; } } } int main() { int n; scanf(%d, n); getchar(); ThreeArr ta[n]; for(int i 0; i n; i) { scanf(%c %c, ta[i].LNode, ta[i].RNode); getchar(); } int head FindHead(ta, n); TreeNode *Tree BuildTree(head, ta); LevelOrder(Tree); return 0; }在实际编码过程中我发现有几个常见错误需要注意忘记释放动态分配的内存虽然在这个简单程序中影响不大数组越界访问特别是在处理字符到数字转换时输入处理时忘记用getchar()吸收换行符6. 算法优化与扩展思考虽然这个解法已经能够很好地解决问题但我们还可以进一步思考可能的优化空间。例如是否可以不用构建完整的二叉树结构直接在输入数据上进行层次遍历经过分析我认为是可行的。我们可以维护一个队列存储待处理的节点编号然后直接从输入数组中查找其左右孩子。这种方法可以节省构建树结构的时间和空间但代码可读性可能会降低。另一个值得思考的问题是如果树非常大比如节点数超过10^5我们的静态数组队列可能不够用。这时应该改用动态扩容的队列或者使用链表实现的队列。在实际工程项目中我们还需要考虑更多的边界情况比如空树的处理所有节点都是叶结点的情况输入数据不合法的情况如形成环这些问题虽然在这个PTA题目中没有出现但在实际开发中都需要考虑周全。这也是算法题目和实际工程问题的一个重要区别。