用c语言 Given a binary tree, check if it is a complete binary tree or not.

下面是用C语言实现的代码，判断一棵二叉树是否为完全二叉树。

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

typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

typedef struct Queue {
    TreeNode **data;
    int front;
    int rear;
    int size;
} Queue;

Queue *createQueue(int size) {
    Queue *q = (Queue *)malloc(sizeof(Queue));
    q->data = (TreeNode **)malloc(sizeof(TreeNode *) * size);
    q->front = q->rear = 0;
    q->size = size;
    return q;
}

bool isEmpty(Queue *q) {
    return q->front == q->rear;
}

bool isFull(Queue *q) {
    return (q->rear + 1) % q->size == q->front;
}

void enqueue(Queue *q, TreeNode *node) {
    if (isFull(q)) {
        return;
    }
    q->data[q->rear] = node;
    q->rear = (q->rear + 1) % q->size;
}

TreeNode *dequeue(Queue *q) {
    if (isEmpty(q)) {
        return NULL;
    }
    TreeNode *node = q->data[q->front];
    q->front = (q->front + 1) % q->size;
    return node;
}

bool isCompleteTree(TreeNode* root) {
    if (root == NULL) {
        return true;
    }
    Queue *q = createQueue(1000);
    bool flag = false;
    enqueue(q, root);
    while (!isEmpty(q)) {
        TreeNode *node = dequeue(q);
        if (node->left) {
            if (flag) {
                return false;
            }
            enqueue(q, node->left);
        } else {
            flag = true;
        }
        if (node->right) {
            if (flag) {
                return false;
            }
            enqueue(q, node->right);
        } else {
            flag = true;
        }
    }
    return true;
}

int main() {
    TreeNode *root = (TreeNode *)malloc(sizeof(TreeNode));
    root->val = 1;
    root->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->val = 2;
    root->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->val = 3;
    root->left->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->left->val = 4;
    root->left->right = (TreeNode *)malloc(sizeof(TreeNode));
    root->left->right->val = 5;
    root->right->left = (TreeNode *)malloc(sizeof(TreeNode));
    root->right->left->val = 6;
    printf("%s\n", isCompleteTree(root) ? "true" : "false");
    return 0;
}

代码中使用了队列来存储二叉树中的节点，判断是否为完全二叉树的方法是，从根节点开始，每层的节点必须都存在，否则后面的节点都必须是叶子节点才满足完全二叉树的定义。