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

题解：建立好二叉搜索树以后的难点应该就是判断是否是完全二叉树了。完全二叉树的定义是：深度为n的二叉树，其全部深度n-1的节点为满，而深度为n的节点只能聚集在左侧。那么我们可以层次遍历找到第一个NULL节点，记录遍历的节点个数，如果其个数为n的话说明为完全二叉树，否则不是。下面引用一下百度定义：

完全二叉树是效率很高的数据结构，完全二叉树是由满二叉树而引出来的。对于深度为K的，有n个结点的二叉树，当且仅当其每一个结点都与深度为K的满二叉树中编号从1至n的结点一一对应时称之为完全二叉树。

#include<bits/stdc++.h>
using namespace std;
struct node
{
    node *l,*r;
    int data;
};
int n;
node *Insert(node *root,int x)
{
    if(root==NULL)
    {
        root=new node;
        root->data=x;
        root->l=root->r=NULL;
        return root;
    }
    else
    {
        if(x<root->data)
            root->r=Insert(root->r,x);
        else if(x>root->data)
            root->l=Insert(root->l,x);
    }
    return root;
}
void layershow(node *root)
{
    queue<node*>que;
    if(root)
    {
        cout<<root->data;
        que.push(root);
    }
    while(!que.empty())
    {
        node *root=que.front();
        que.pop();
        if(root->l)
        {
            cout<<" "<<root->l->data;
            que.push(root->l);
        }
        if(root->r)
        {
            cout<<" "<<root->r->data;
            que.push(root->r);
        }
    }
}
int check(node *root)
{
    queue<node*>que;
    que.push(root);
    int num=0;
    while((root=que.front())!=NULL)
    {
        que.push(root->l);
        que.push(root->r);
        que.pop();
        num++;
    }
    if(num==n)
        return 1;
    return 0;
}
int main()
{
    cin>>n;
    node *root=NULL;
    for(int i=1;i<=n;i++)
    {
        int x;
        cin>>x;
        root=Insert(root,x);
    }
    layershow(root);
    cout<<endl;
    int x=check(root);
    if(x)
        cout<<"YES"<<endl;
    else
        cout<<"NO"<<endl;
    return 0;
}