PTA L3-010 是否完全二叉搜索树 - 题解与完整代码 题目概述题目要求我们根据给定的一整型序列按照特定的规则建立一棵二叉搜索树BST并判断该树是否为完全二叉搜索树。最后需要输出这棵树的层序遍历序列以及判断结果是则输出YES否则输出NO。建树规则左子树的键值大于根结点的键值右子树的键值小于等于根结点的键值 解题思路这里提供一种非常巧妙且代码量极小的解法——利用一维数组存储二叉树。数组表示二叉树对于一棵二叉树如果将其各个节点从上至下、从左至右从1开始编号那么对于编号为p的节点其左孩子节点的编号一定是2 * p代码中表示为p 1其右孩子节点的编号一定是2 * p 1代码中表示为(p 1) 1建树过程 (bd函数)从根节点编号1开始插入。如果当前位置为空则将其置为插入的数值。如果插入的值大于当前节点值递归到左孩子p 1。否则小于等于当前节点值递归到右孩子(p 1) 1。如何输出层序遍历并判断完全二叉树层序遍历由于我们是用数组按层序的方式对树进行索引存储的因此直接从下标1开始遍历数组如果该位置有值就直接输出即可。这就是天然的层序遍历序列完全二叉树判断在一棵拥有$n$个节点的完全二叉树中节点必定会紧凑地填满数组的1到n的位置。也就是说数组中出现的最大非空下标必然刚好等于nnn。如果最大非空下标大于nnn说明中间存在空缺位置这棵树就不是完全二叉树。 C 完整代码实现#includebits/stdc.h#defineintlonglong#defineendl\n#definelcp1// 左孩子编号#definerc(p1)1// 右孩子编号usingnamespacestd;inttr[1010];// 用数组模拟二叉树最大节点数和深度不会导致下标很大时适当放大即可// 插入节点建立二叉树voidbd(intp,intx){if(tr[p]0){tr[p]x;return;}// 左子树大于根节点if(xtr[p]){bd(lc,x);}// 右子树小于等于根节点else{bd(rc,x);}}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intn;cinn;for(inti1;in;i){intx;cinx;bd(1,x);// 从根节点依次插入}boolfl0;intmx0;// 记录存在的最大索引// 遍历整个数组来输出层序遍历结果并找最大索引for(inti1;i1000;i){if(tr[i]){if(fl)cout ;fl1;couttr[i];mxi;}}cout\n;// 判断是否为完全二叉分类树if(mxn)coutYES;elsecoutNO;return0;} 总结使用数组建树完美契合了本题“层序遍历”和“完全二叉树判断”两项需求省去了传统的队列层序遍历过程使得代码极其精简。