完全二叉搜索树的判断“编程题”

7-2是否完全二叉搜索树（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

#include
#include

const int MAXN = 1<<21;
int ORGT[MAXN];
int x, N, MAXNDEEP;

void Insert(int *TREE, int val, int cur) {
    MAXNDEEP = cur > MAXNDEEP ? cur : MAXNDEEP;
    if(TREE[cur] == -1) {
        TREE[cur] = val;
    } else if(TREE[cur] < val) {
        Insert(TREE, val,2*cur);
    } else if(TREE[cur] > val) {
        Insert(TREE, val,2*cur+1);
    }
}

int main() {

    MAXNDEEP = 0;
    memset(ORGT, -1, sizeof(ORGT));

    scanf("%d", &N);
    for(int i = 0; i < N; ++i) {
        scanf("%d", &x);
        Insert(ORGT, x, 1);
    }

    int y = MAXNDEEP == N ? 1 : 0;
    for(int i = 1; i <= MAXNDEEP ; ++i) {
        if(ORGT[i] != -1) {
            if(i != 1) {
                printf(" ");
            }
            printf("%d", ORGT[i]);
        }
    }
    printf("\n%s\n", y ? "YES" : "NO");
    return 0;
}