是否完全二叉搜索树

题目要求如下：

7-1 是否完全二叉搜索树（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、如果一个结点左右孩子都不为空，将其左右孩子入队列；
4、如果遇到一个结点，左孩子为空，右孩子不为空，则该树一定不是完全二叉树；
5、如果遇到一个结点，左孩子不为空，右孩子为空；或者左右孩子都为空；则该节点之后 的队列中的结点都为叶子节点；该树才是完全二叉树，否则就不是完全二叉树；

简单来说就是，子节点都是要求左往右走的，当遇到一个度小于2的结点，则后面的一定要全为叶子。

代码实现(代码算法不够优化)：

#include<stdio.h>
#include<stdlib.h>

struct TNode {
    int Data;
    struct TNode *Left, *Right;
};

struct TNode *Insert(struct TNode *BST, int X)  //搜索二叉树的插入
{ 
    if(!BST) {
        BST = (struct TNode *)malloc(sizeof(struct TNode));
        BST->Data = X;
        BST->Left = BST->Right = NULL;
    }
    else {
        if(X > BST->Data) {
            BST->Left = Insert(BST->Left, X);
        }
        else if(X < BST->Data) {
            BST->Right = Insert(BST->Right, X);
        }
    }

    return BST;
}

int LevelorderTraversal(struct TNode *BT) //层序遍历 
{
    int t = 0, k = 1, flag = 1;
    /*t是队头指针，k为队尾指针，flag用于标记是否为完全二叉树，非0即真 *flag == 2为标记，如果flag==2之后的所有结点不全为叶子节点，为否*/ 
    struct TNode *s[21]; //队列大小 
    s[t] = BT; //第一个二叉树根结点入队列 
    while(t != k) { //t于k相等说明，队列为空（此非循环队列）。 
        if(!t) {
            printf("%d", s[t]->Data); //第一个打印不用空格 
        } 
        else {
            printf(" %d", s[t]->Data); //除第一个以外，其他前面加空格，这样保证了结尾不会有空格 
        }
        if(s[t]->Left && s[t]->Right) { //若左右结点都不为空 
            if(flag == 2) {  // 如果此结点已被标记，而此节点不为叶子，则不为完全二叉树 
                flag = 0; //标记为否 
            }
            //遍历继续 
            s[k++] = s[t]->Left; //左子树入队 
            if(t == k) {
                break;
            }
            s[k++] = s[t]->Right; //右子树入队 
            if(t == k) {
                break;
            }
        } 
        else if(s[t]->Left && (!s[t]->Right)){ //如果左子树不为空，右子树为空 
            if(flag == 2) { // 如果此结点已被标记，而此节点不为叶子，则不为完全二叉树 
                flag = 0; //标记为否 
            }
            //遍历继续 
            s[k++] = s[t]->Left;//左子树入队 
            if(flag != 0) { //如果此树已经确定不为完全二叉树，则不必标记 
                flag = 2; //若此树未被标记，则在此处标记，后面的节点需都为叶子才是完全二叉树，否则不是 
            }
            if(t == k) {
                break;
            }
        }
        else if(!s[t]->Left && s[t]->Right){ //左子树为空，而右子树不为空，则此树一定是非完全二叉树 
            flag = 0; //标记为否 
            s[k++] = s[t]->Right; //右子树入队 
            if(t == k) {
                break;
            }
        }
        else { //如果左右子树都为空 
            if(flag == 1) { //并且此树还认为正确的 
                flag = 2; //标记为不一定正确 
            }
        }
        t ++; //队头指针右移，用于出队 
    }

    return flag; //返回flag的值 
}

int main()
{
    int i, n, X, H;
    struct TNode *BST = NULL;
    scanf("%d", &n);
    for(i = 0; i < n; i ++) {
        scanf("%d", &X);
        BST = Insert(BST, X);
    }
    if(LevelorderTraversal(BST) != 0) { //flag的值非0即真 
        printf("\nYES\n");
    }
    else {
        printf("\nNO\n");
    }

    return 0;
}