C4top-是否完全二叉搜索树（层次遍历+完全判断）

水深无声 2022-09-30 09:40 125阅读 0赞

是否完全二叉搜索树

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

### 输入格式： ###

输入第一行给出一个不超过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

*  时间限制：400ms
 *  内存限制：64MB
 *  代码长度限制：16kB
 *  判题程序：系统默认
 *  作者：陈越
 *  单位：浙江大学

#### 题目判定 ####

##### 解题程序 #####

#include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<queue>
    #include<iomanip>
    #include<cstdlib>
    #include<iostream>
    #include<algorithm>
    using namespace std;
    #define MAXN 20
    #define INF 0x3f3f3f3f
    typedef struct node//二叉树搜索树
    {
        int data;
        struct node * lchild;
        struct node * rchild;
    } bstnode;
    int n,a[MAXN];
    int insertbst(bstnode * &p,int k)//插入结点
    {
        if(p==NULL)
        {
            p=(bstnode *)malloc(sizeof(bstnode));
            p->data=k;
            p->lchild=p->rchild=NULL;
            return 1;
        }
        else if(k==p->data) return 0;
        else if(k>p->data) return insertbst(p->lchild,k);//题目要求左大右小
        else return insertbst(p->rchild,k);
    }
    bstnode * creatbst(int a[],int n)//建树
    {
        bstnode * bt=NULL;
        int i=0;
        while(i<n)
        {
            insertbst(bt,a[i]);
            ++i;
        }
        return bt;
    }
    int dis[MAXN],cnt=0;//存储遍历到的元素
    void level(bstnode * b,int n)//层次遍历
    {
        bstnode *p;
        bstnode *q[n];
        int front,rear;
        front=rear=-1;
        ++rear;
        q[rear]=b;
        while(front!=rear)
        {
            front=(front+1)%n;
            p=q[front];
            dis[cnt++]=p->data;//遍历时的当前数组
            if(p->lchild!=NULL)
            {
                rear=(rear+1)%n;
                q[rear]=p->lchild;
            }
            if(p->rchild!=NULL)
            {
                rear=(rear+1)%n;
                q[rear]=p->rchild;
            }
        }
    }
    /*
    完全二叉树的定义
    前n-1层都是满的
    第n层如有空缺，则是缺在右边，即第n层的最右边的节点
    它的左边是满的，右边是空的
    */
    bool is_completeTree(bstnode * b)//判断是否完全二叉树
    {
        queue<bstnode*> q;
        if(NULL!=b)
        {
            q.push(b);
            bstnode* cur=NULL;
            bool flag=false;
            while(!q.empty())
            {
                cur=q.front();
                q.pop();
                if(cur)
                {
                    if(flag) return false;
                    q.push(cur->lchild);
                    q.push(cur->rchild);
                }
                //当前遍历到NULL结点即叶结点，那么后续如果还有非叶结点，就说明是非完全二叉树
                else flag=true;
            }
            return true;
        }
        return true;
    }
    
    
    int main()
    {
    #ifdef ONLINE_JUDGE
    #else
        freopen("G:/cbx/read.txt","r",stdin);
    //freopen("G:/cbx/out.txt","w",stdout);
    #endif
        ios::sync_with_stdio(false);
        cin.tie(0);
        cin>>n;
        for(int i=0; i<n; ++i)
            cin>>a[i];
        bstnode * b;
        b=creatbst(a,n);//建树
        level(b,n);//层次遍历
        for(int i=0; i<cnt-1; ++i)
            cout<<dis[i]<<" ";
        cout<<dis[cnt-1]<<endl;
        if(is_completeTree(b)) cout<<"YES"<<endl;//完全二叉树
        else cout<<"NO"<<endl;
        return 0;
    }