C语言实现：判定给定二叉树是否为完全二叉树

在C语言中，判断一个二叉树是否为完全二叉树通常涉及深度优先搜索（DFS）策略。完整二叉树是一种特殊的二叉树，除了最后一层外，所有层次的节点都尽可能多地填充，并且所有叶子节点都在最底层。下面是一个简单的递归函数实现：

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

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

bool isCompleteBinaryTree(TreeNode* root) {
    // 基本情况：空树或只有一个节点都是完全二叉树
    if (!root) return true;
    if (!root->left && !root->right) return true; // 叶子节点

    // 深度优先搜索，检查当前节点及其左右子树是否满足条件
    bool leftIsComplete = isCompleteBinaryTree(root->left);
    bool rightIsComplete = isCompleteBinaryTree(root->right);

    // 当前节点不是叶子节点，如果左右子树都不为空，则必须左满再右非空
    if (leftIsComplete && (rightIsComplete || !root->right)) {
        return true;
    } else {
        return false;
    }
}

int main() {
    // 创建示例二叉树，并调用isCompleteBinaryTree函数验证
    TreeNode *root = // 初始化你的二叉树...
    // ...
    if (isCompleteBinaryTree(root)) {
        printf("给定二叉树是完全二叉树\n");
    } else {
        printf("给定二叉树不是完全二叉树\n");
    }

    return 0;
}