用c语言实现Given a binary tree, check if it is a complete binary tree or not.，并说明原理

以下是用 C 语言实现的代码：

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

/* 二叉树结点 */
struct TreeNode {
    int val;
    struct TreeNode* left;
    struct TreeNode* right;
};

/* 队列结点 */
struct QueueNode {
    struct TreeNode* data;
    struct QueueNode* next;
};

/* 队列 */
struct Queue {
    struct QueueNode* front;
    struct QueueNode* rear;
};

/* 创建队列 */
struct Queue* createQueue()
{
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->front = queue->rear = NULL;
    return queue;
}

/* 判断队列是否为空 */
bool isQueueEmpty(struct Queue* queue)
{
    return queue->front == NULL;
}

/* 入队 */
void enqueue(struct Queue* queue, struct TreeNode* data)
{
    struct QueueNode* newNode = (struct QueueNode*)malloc(sizeof(struct QueueNode));
    newNode->data = data;
    newNode->next = NULL;
    if (isQueueEmpty(queue)) {
        queue->front = queue->rear = newNode;
    }
    else {
        queue->rear->next = newNode;
        queue->rear = newNode;
    }
}

/* 出队 */
struct TreeNode* dequeue(struct Queue* queue)
{
    if (isQueueEmpty(queue)) {
        return NULL;
    }
    else {
        struct TreeNode* data = queue->front->data;
        struct QueueNode* temp = queue->front;
        queue->front = queue->front->next;
        if (queue->front == NULL) {
            queue->rear = NULL;
        }
        free(temp);
        return data;
    }
}

/* 判断是否为完全二叉树 */
bool isCompleteTree(struct TreeNode* root)
{
    if (root == NULL) {
        return true;
    }
    struct Queue* queue = createQueue();
    enqueue(queue, root);
    bool flag = false;
    while (!isQueueEmpty(queue)) {
        struct TreeNode* temp = dequeue(queue);
        if (temp->left) {
            if (flag) {
                return false;
            }
            enqueue(queue, temp->left);
        }
        else {
            flag = true;
        }
        if (temp->right) {
            if (flag) {
                return false;
            }
            enqueue(queue, temp->right);
        }
        else {
            flag = true;
        }
    }
    return true;
}

/* 创建二叉树 */
struct TreeNode* createTree()
{
    int val;
    scanf("%d", &val);
    if (val == -1) {
        return NULL;
    }
    struct TreeNode* root = (struct TreeNode*)malloc(sizeof(struct TreeNode));
    root->val = val;
    root->left = createTree();
    root->right = createTree();
    return root;
}

/* 主函数 */
int main()
{
    struct TreeNode* root = createTree();
    if (isCompleteTree(root)) {
        printf("It is a complete binary tree.\n");
    }
    else {
        printf("It is not a complete binary tree.\n");
    }
    return 0;
}

原理：

完全二叉树（Complete Binary Tree）是指除了最后一层外，其他层的结点数都达到了最大值，最后一层的结点都集中在左侧。而对于一棵二叉树，如果它的层数为 h，那么它最多有 $2^h-1$ 个结点。因此，我们可以利用层序遍历的方式，对二叉树进行遍历，如果遇到某个结点缺少左子结点或右子结点，那么后续的结点必须全部为叶子结点，否则这棵二叉树就不是完全二叉树。