用c语言Check if given binary tree is complete binary tree or not，通过比较结点数量

以下是用C语言实现判断二叉树是否为完全二叉树的代码：

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

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

// 计算二叉树的结点数量
int countNodes(struct Node* root) {
    if (root == NULL) {
        return 0;
    }
    return 1 + countNodes(root->left) + countNodes(root->right);
}

// 判断二叉树是否为完全二叉树
int isCompleteTree(struct Node* root, int index, int numNodes) {
    // 如果为空树，返回true
    if (root == NULL) {
        return 1;
    }

    // 如果当前结点的索引超过了结点数量，返回false
    if (index >= numNodes) {
        return 0;
    }

    // 递归判断左右子树是否为完全二叉树
    return isCompleteTree(root->left, 2 * index + 1, numNodes) &&
           isCompleteTree(root->right, 2 * index + 2, numNodes);
}

int main() {
    // 创建一个二叉树
    struct Node* root = (struct Node*)malloc(sizeof(struct Node));
    root->val = 1;
    root->left = (struct Node*)malloc(sizeof(struct Node));
    root->left->val = 2;
    root->left->left = (struct Node*)malloc(sizeof(struct Node));
    root->left->left->val = 4;
    root->left->right = (struct Node*)malloc(sizeof(struct Node));
    root->left->right->val = 5;
    root->right = (struct Node*)malloc(sizeof(struct Node));
    root->right->val = 3;
    root->right->left = (struct Node*)malloc(sizeof(struct Node));
    root->right->left->val = 6;

    int nodeCount = countNodes(root);
    int index = 0;

    if (isCompleteTree(root, index, nodeCount)) {
        printf("This is a complete binary tree.\n");
    } else {
        printf("This is not a complete binary tree.\n");
    }

    return 0;
}

该程序首先定义了一个二叉树结点的结构体，包含结点值、左右子树的指针。接着定义了两个函数：

- `countNodes`：计算二叉树的结点数量，使用递归方式遍历二叉树，每遍历一个结点，就累加1，最终返回结点数量。
- `isCompleteTree`：判断二叉树是否为完全二叉树，使用递归方式遍历二叉树，同时记录每个结点的索引。如果当前结点的索引超过了结点数量，说明已经遍历到了不存在的结点，因此返回false。如果当前结点的索引小于结点数量，就继续递归遍历它的左右子树，直到遍历完整棵树。如果递归过程中没有返回false，说明该树是完全二叉树，返回true。

在主函数中，我们创建了一个二叉树，并调用`countNodes`计算结点数量，调用`isCompleteTree`判断二叉树是否为完全二叉树。最终根据返回值输出判断结果。