7-12 是否完全二叉搜索树（梯赛）

写在最前面： 近期有点繁忙有些题目没配图，真香。

1、题目

2、图文讲解

该题我是用数组来存储的， 用数组构造二叉树。（如果大佬还有更好的方法， 请留言指导）

大家都知道完全二叉树的图是这样的下↓（本着NPNBB 没有图片别哔哔的原则， 所以T.J 给你们画了几张图 ）

在数组中表现的形式是一串连续的数

所以利用数组构建搜索树的这个特点 可以判断是否为完全二叉树。

3.代码实现：

#include <stdio.h>
#include <stdlib.h>
#include<string.h>
int t[600000];//数组模拟搜索树
int N;
void insert(int i,int num)//插入函数
{
    if(t[i] == -1)//表示为空t[] = -1 表示该节点为空
    {
        t[i] = num;
    }

    else if(num > t[i])//如果比根大 递归到左儿子
    {
        insert(2*i+1, num);
    }
    else if(num < t[i])//如果比根小 递归到右儿子
    {
        insert(2*i+2, num);
    }


}


void Creat()//创建函数
{
    int i;
    for(i = 0; i < N; i++)
    {
        int num;
        scanf("%d", &num);
        insert(0,num);
    }
}
int que[600000];//队列用于层次遍历
int head;
int tail;
void cprint()//遍历函数
{
   if(t[0] == -1) return;
   head = 0;
   tail = 0;
   que[tail++] = 0;
   int i;
   while(head!= tail)
   {
       i = que[head];
      if(-1!=t[i])
      {
          if(t[2*i+1]!= -1)
          {
              que[tail++] = 2*i+1;
          }
          if(t[2*i+2]!= -1)
          {
              que[tail++] = 2*i+2;
          }
      }
      head++;
   }
   int p;//输出
   for(i = 0;i < tail;i++)
   {
       p = que[i];
       if(i< tail-1)printf("%d ", t[p]);
       else printf("%d\n", t[p]);

   }


}

int main()
{
    memset(t, -1, sizeof(t));//初始化为-1表示都为空节点

    scanf("%d", &N);
    Creat();
    int i;
    for(i = 0;i< N;i++)//  根据完全二叉树的特点判断是否为完全二叉树
    {
        if(t[i]== -1)break;
    }

    if(i == N)
    {
        cprint();
        printf("YES\n");
    }
    else
    {
        cprint();
        printf("NO\n");
    }


    return 0;
}