c语言实现判断完全二叉树

在C语言中，我们可以使用递归的方式来判断一棵二叉树是否为完全二叉树。完全二叉树的特点是除了最后一层外，每一层都是满的，并且所有节点都尽可能地向左靠拢。以下是递归函数的基本思路：

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

// 判断是否为完全二叉树的辅助函数
int isCompleteBinaryTreeHelper(TreeNode* root, int level) {
    if (root == NULL) {
        // 空或仅有一个节点的树都是完全二叉树
        return 1;
    }
    
    // 如果当前层级不是最后一层，检查当前节点是否有右孩子
    if (level < height(root)) {
        if (root->right != NULL) {
            // 如果有右孩子，说明当前节点不是最左边的节点，这不符合完全二叉树的条件
            return 0;
        } else {
            // 只有一个左孩子，继续检查下一层
            return isCompleteBinaryTreeHelper(root->left, level + 1);
        }
    } else {
        // 当前层级是最后一层，检查所有的节点都有左孩子
        return isAllNodesHaveLeftChild(root);
    }
}

// 辅助函数：检查所有节点是否都有左孩子
int isAllNodesHaveLeftChild(TreeNode* node) {
    while (node) {
        if (node->right != NULL) {
            return 0; // 发现右孩子，不是完全二叉树
        }
        node = node->left;
    }
    return 1; // 所有节点都没有右孩子，是完全二叉树
}

// 主函数：输入根节点，返回整型值表示是否为完全二叉树
int isCompleteBinaryTree(TreeNode* root) {
    return isCompleteBinaryTreeHelper(root, 0);
}