判断是否为完全二叉树用栈队列，C语言代码

判断一个给定的二叉树是否为完全二叉树可以使用广度优先搜索（BFS）结合栈来实现。在完全二叉树中，除了最后一层外，所有层级的节点都尽可能多地填充，并且最后一层的所有节点都集中在左边。

以下是C语言的一个简单算法：

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

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 检查是否为空
bool isEmpty(TreeNode* node) {
    return node == NULL;
}

// 使用栈检查是否为完全二叉树
bool isCompleteBinaryTree(TreeNode* root) {
    if (isEmpty(root)) {
        return true; // 空树被认为是完全二叉树
    }

    bool levelIsFull = false;
    TreeNode* prevLevel = NULL;
    queue_t q;
    enqueue(&q, root);

    while (!isEmpty(q)) {
        size_t count = dequeue(&q, &prevLevel);
        if (count > 0 && !levelIsFull) { // 如果当前层有节点且不是满的
            levelIsFull = true;
        }
        for (size_t i = 0; i < count; ++i) {
            TreeNode* current = prevLevel[i];
            if (current->left != NULL || current->right != NULL) {
                if (current->left == NULL && current->right != NULL) {
                    levelIsFull = false; // 非空右节点导致非满层
                    break;
                } else if (current->left != NULL && current->right == NULL) {
                    // 类似情况，左节点非空则层不满
                    levelIsFull = false;
                    break;
                }
                enqueue(&q, current->left); // 添加左右子节点到队列
                enqueue(&q, current->right);
            }
        }
        if (!levelIsFull) {
            break; // 如果某层不满，则直接返回false
        }
    }
    return levelIsFull; // 如果所有层都是满的，返回true
}

// 宏定义队列操作
#define enqueue(queue, item) (push((queue), (item)))
#define dequeue(queue, prevLevel) (pop((queue), (prevLevel)))

// 这里省略了具体的队列数据结构实现，如用数组模拟

int main() {
    // 测试代码
    TreeNode* testTree = ...; // 实际的二叉树构造代码
    if (isCompleteBinaryTree(testTree)) {
        printf("完全二叉树\n");
    } else {
        printf("非完全二叉树\n");
    }
    return 0;
}