PAT-A 1110 Complete Binary Tree (25 分)

PAT-A 1110 Complete Binary Tree (25 分)

给定一个树，请你判断它是否是完全二叉树。

输入格式
第一行包含整数 N，表示树的结点个数。

树的结点编号为 0∼N−1。

接下来 N 行，每行对应一个结点，并给出该结点的左右子结点的编号，如果某个子结点不存在，则用 - 代替。

输出格式
如果是完全二叉树，则输出 YES 以及最后一个结点的编号。

如果不是，则输出 NO 以及根结点的编号。

数据范围
1≤N≤20
输入样例1：
9
7 8
_ _
_ _
_ _
0 1
2 3
4 5
_ _
_ _
输出样例1：
YES 8
输入样例2：
8
_ _
4 5
0 6
_ _
2 3
_7
_ _
_ _
输出样例2：
NO 1

思路同样是邻接表模拟树结构。判断是不是完全二叉树其实就是层序遍历到一个空节点的时候，对已经入队的节点进行检查，如果有一个非空节点，则可以立刻判断此树不是完全二叉树。

#include 

using namespace std;
struct node
{
    int data;
    int l=-1,r=-1;
}a[10101];
int n;
int flag=1;
int endd;
int pre[10101];
bool check(queue q)
{
    while(!q.empty())
    {
        int now = q.front();
        q.pop();
        if(now != -1)
        return false;
    }
    return true;
}
void  judge(int id)
{
    queue q;
    q.push(id);
    while(!q.empty())
    {
        int now = q.front();
       
        q.pop();
        if(now !=-1)
        {   endd=now;
            q.push(a[now].l);
            q.push(a[now].r);
        }
        else
        if(!check(q))
        flag=0;
    }
}
int main()
{
    cin >> n;
    for(int i=0;i> s >>ss;
      
        if(s=="-")
        a[i].l = -1;
        else
        {
             a[i].l = stoi(s);
             pre[stoi(s)]=1;
        }
        
        if(ss=="-")
        a[i].r = -1;
        else
        {
             a[i].r = stoi(ss);
             pre[stoi(ss)]=1;
        }
    }
    int i;
    for( i=0;pre[i]==1;i++);
    judge(i);
    if(flag)
    {  
        cout <<"YES"<<" "<					
										


					

						
欢迎分享，转载请注明来源：内存溢出
原文地址: http://outofmemory.cn/zaji/5636377.html