7-13 是否完全二叉搜索树（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
题解：1：建树 2: 检查是否是完全二叉树
检查是否是完全二叉树是难点，要遵循以下原则
1：如果当前节点左右孩子均有，就将当前节点弹出，将左右还记节点加入
2：如果有左孩子，但是没有右孩子，或者左右孩子均没有，则这个节点以后的节点都应该是叶子节点
3：没有左孩子，但是有右孩子，不会完全二叉树
代码：
#include<cstdio>
#include<cstring>
#include<cstdlib>
#include<queue>
#include<iostream>
using namespace std;
struct node
{
int data;
struct node *left;
struct node *right;
} *tree;
struct node* Build(struct node*t,int tmp)
{
if(t == NULL)
{
struct node *tt = (struct node*)malloc(sizeof(struct node));
tt->data = tmp;
tt->left = tt->right = NULL;
t = tt;
}
else
{
if(tmp>t->data)
t->left = Build(t->left,tmp);
else
t->right = Build(t->right,tmp);
}
return t;
}
void Level(struct node* t)
{
if(t==NULL)
return ;
queue<struct node*> que;
que.push(t);
struct node *k;
int flag = 0;
while(!que.empty())
{
k = que.front();
que.pop();
if(flag == 0)
{
flag = 1;
cout << k->data;
}
else
cout << ” ” << k->data;
if(k->left)
que.push(k->left);
if(k->right)
que.push(k->right);
}
return ;
}
void Judge(struct node* tt)
{
if(tt == NULL)
{
cout << “NO” << endl;
return ;
}
int flag = 0;
queue<struct node*>que;
que.push(tt);
while(!que.empty())
{
struct node *k = que.front();
if(flag && (k->left || k->right)) //flag用来标记，上一个节点没有节点或者有右孩子没有
{ //左孩子，则这个节点以后的节点都应该是叶子节点
cout << “NO” << endl;
return ;
}
if(k->left && k->right)
{
que.pop();
que.push(k->left);
que.push(k->right);
}
else if(!k->left && k->right)
{
cout << “NO” << endl;
return ;
}
else if(k->left && !k->right) //这种情况 left必须是最后一个
{
if(k->left->left || k->left->right)
{
cout << “NO” << endl;
return ;
}
flag = 1;
que.pop();
que.push(k->left);
}
else
{
que.pop();
flag = 1;
}
}
cout << “YES” << endl;
return ;
}
int main()
{
int n,tmp;
tree = NULL;
cin >> n;
for(int i=0;i<n;i++)
{
cin >> tmp;
tree = Build(tree,tmp);
}
Level(tree);
cout << endl;
Judge(tree);
return 0;
}