PTA 7

PTA 7

将一系列给定数字顺序插入一个初始为空的二叉搜索树（定义为左子树键值大，右子树键值小），你需要判断最后的树是否一棵完全二叉树，并且给出其层序遍历的结果。

输入格式：

输入第一行给出一个不超过20的正整数N；第二行给出N个互不相同的正整数，其间以空格分隔。

输出格式：

将输入的N个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果，数字间以1个空格分隔，行的首尾不得有多余空格。第二行输出YES，如果该树是完全二叉树；否则输出NO。

输入样例1：

19
238 45 42 24 58 30 67 12 51

输出样例1：

138 45 24 58 42 30 12 67 51
2YES

输入样例2：

18
238 24 12 45 58 67 42 51

输出样例2：

138 45 24 58 42 12 67 51
2NO

满二叉树：假设这个二叉树有n层，那么每一层的节点数都达到最大的二叉树。
完全二叉树：把最后一层去掉就是满二叉树，同时最后一层：我们假设最后一层里面如果是满的话是有n个节点，我们从左往右标号1-n,那么最后一层如果想要有节点的话，一定要按照标号顺序建立，不能隔过一个或多个标号去建立其他的节点。

所以我们分析一下完全二叉树的特点：我们按照层次顺序遍历这颗树的过程中，对于任意一节点x
1 》如果x 有右子树，但是却没有左子树，这肯定不是完全二叉树
2 》如果x 有左子树，但是却没有右子树，那么剩余的所有节点一定要为叶子节点
3 》如果 x 左右子树都没有，那么剩余的所有节点也要为叶子节点

判断是否是完全二叉树很简单查看是否连续即可用数组建树方便很多

1#include<bits/stdc++.h>
2using namespace std;
3//input by bxd
4#define rep(i,a,b) for(int i=(a);i<=(b);i++)
5#define repp(i,a,b) for(int i=(a);i>=(b);i--)
6#define RI(n) scanf("%d",&(n))
7#define RII(n,m) scanf("%d%d",&n,&m)
8#define RIII(n,m,k) scanf("%d%d%d",&n,&m,&k)
9#define RS(s) scanf("%s",s);
10#define LL long long
11#define pb push_back
12#define fi first
13#define REP(i,N)  for(int i=0;i<(N);i++)
14#define CLR(A,v)  memset(A,v,sizeof A)
15///////////////////////////////////
16#define inf 0x3f3f3f3f
17#define N 1000
18int a[N];
19int n;
20
21void build()
22{
23    CLR(a,-1);
24    rep(i,1,n)
25    {
26        int x;
27        RI(x);
28        int id=1;
29        while(1)
30        {
31            if(a[id]==-1)
32            {
33                a[id]=x;break;
34            }
35            else if(x>a[id])
36            {
37                id<<=1;
38            }
39            else
40            id=id*2+1;
41        }
42    }
43}
44bool check()
45{
46    int cnt=0;
47    int flag=1;
48    rep(i,1,N)
49    {
50        if(cnt==n)break;
51        if(a[i]!=-1)
52        {
53            cnt++;
54            cout<<a[i];
55            cout<<(cnt==n?'\n':' ');
56        }
57        else//如果中断了说明不是完全二叉树
58            flag=0;
59    }
60    return flag;
61}
62int main()
63{
64   RI(n);
65   build();
66   if(check())
67   printf("YES");
68   else printf("NO");
69    return 0;
70}

View Code

评论区

加载中...