当前位置：首页 > news >正文

L3-010 是否完全二叉搜索树 - 题解与完整代码

news 2026/5/12 19:18:40

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++ 完整代码实现

#include<bits/stdc++.h>#defineintlonglong#defineendl"\n"#definelcp<<1// 左孩子编号#definerc(p<<1)+1// 右孩子编号usingnamespacestd;inttr[1010];// 用数组模拟二叉树，最大节点数和深度不会导致下标很大时适当放大即可// 插入节点建立二叉树voidbd(intp,intx){if(tr[p]==0){tr[p]=x;return;}// 左子树大于根节点if(x>tr[p]){bd(lc,x);}// 右子树小于等于根节点else{bd(rc,x);}}signedmain(){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);intn;cin>>n;for(inti=1;i<=n;i++){intx;cin>>x;bd(1,x);// 从根节点依次插入}boolfl=0;intmx=0;// 记录存在的最大索引// 遍历整个数组来输出层序遍历结果并找最大索引for(inti=1;i<=1000;i++){if(tr[i]){if(fl)cout<<" ";fl=1;cout<<tr[i];mx=i;}}cout<<"\n";// 判断是否为完全二叉分类树if(mx==n)cout<<"YES";elsecout<<"NO";return0;}