天梯赛 L3-010 是否完全二叉搜索树 （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）如果结点有左孩子无右孩子，那么后面遍历的节点必须是叶子节点

        （3）如果结点是叶子节点，那么后面遍历的节点必须是叶子结点。

程序：

#include <cstdio>
#include <vector>
#include <queue>
#include <cstdlib>
using namespace std;
struct node 
{
	int data;
	struct node *left,*right;
};
void Insert(struct node* &root,int data)
{
	if(root == NULL)
	{
		root = (struct node*)malloc(sizeof(struct node));
		root->data = data;
		root->left = NULL;
		root->right = NULL;
	}
	else
	{
		if(data > root->data)
			Insert(root->left,data);
		else
			Insert(root->right,data);
	}
}
void level(struct node* root)
{
	bool fg1 = false;
	bool fg = false;
	bool flag = true;
	queue<struct node*> q;
	q.push(root);
	vector<int> v;
	while(!q.empty())
	{
		struct node* temp = q.front();
		q.pop();
		v.push_back(temp->data);
		if(temp->left)
			q.push(temp->left);
		if(temp->right)
			q.push(temp->right);
		if(temp->left == NULL && temp->right)
			flag = false;
		if(temp->left == NULL && temp->right == NULL && !fg)
		{
			fg = true;
		}
		if(temp->left && temp->right == NULL && !fg1)
		{
			fg1 = true;
			continue;
		}
		if(fg1 && temp->left)
			flag = false;
		if(fg && (temp->left || temp->right))
			flag = false;
	}
	for(int i = 0; i < v.size(); i++)
	{
		if(i == 0)
			printf("%d",v[i]);
		else
			printf(" %d",v[i]);
	}
	printf("\n");
	if(flag)
		printf("YES\n");
	else 
		printf("NO\n");
}
int main()
{
	int n;
	scanf("%d",&n);
	struct node * root = NULL;
	for(int i = 0; i < n; i++)
	{
		int data;
		scanf("%d",&data);
		Insert(root,data);
	}
	level(root);
	return 0;
}