7-8 是否完全二叉搜索树 (30 分)
将一系列给定数字顺序插入一个初始为空的二叉搜索树(定义为左子树键值大,右子树键值小),你需要判断最后的树是否一棵完全二叉树,并且给出其层序遍历的结果。
输入格式:
输入第一行给出一个不超过20的正整数N
;第二行给出N
个互不相同的正整数,其间以空格分隔。
输出格式:
将输入的N
个正整数顺序插入一个初始为空的二叉搜索树。在第一行中输出结果树的层序遍历结果,数字间以1个空格分隔,行的首尾不得有多余空格。第二行输出YES
,如果该树是完全二叉树;否则输出NO
。
输入样例1:
9 38 45 42 24 58 30 67 12 51
输出样例1:
38 45 24 58 42 30 12 67 51 YES
输入样例2:
8 38 24 12 45 58 67 42 51
输出样例2:
38 45 24 58 42 12 67 51 NO
#include<bits/stdc++.h> using namespace std; int a[5000007]; void Insert(int root,int num) { if(a[root]==-1) { a[root]= num; return ; } if(num>a[root]) { Insert(root<<1,num); } else { Insert(root*2+1,num); } } int main() { int n; cin>>n; memset(a,-1,sizeof a); for(int i=1; i<=n; i++) { int num; cin>>num; Insert(1,num); } int f =1; int top = 1; for(int i=1;i<=(1<<n);i++){ if(a[i]==-1&&i<=n)f=0; else if(a[i]!=-1){ if(top)top =0; else printf(" "); printf("%d",a[i]); } } printf("\n"); if(f)printf("YES\n"); else printf("NO\n"); }