c语言判断是否为完全二叉树

在C语言中，判断一个给定的二叉树是否为完全二叉树通常涉及深度优先搜索（DFS）算法，特别是前序遍历或后序遍历。完全二叉树的特点是除了最后一层外，每一层都是满的，并且所有节点都尽可能地向左靠拢。

以下是一个简单的步骤来判断：

1. 首先，你需要有一个递归函数，它会检查当前节点以及它的左右子节点是否都已访问过，并且如果最后一个节点是在最右边，那么这个树就是完全二叉树。

2. 在前序遍历（根-左-右）过程中，如果你遇到第一个未访问的节点并且它是叶子节点，但是其右侧还有节点，那么树不是完全二叉树。
3. 如果遍历到最后一层的所有节点都被访问了，且所有的非叶子节点都有两个子节点，那么就可以确定这是一个完全二叉树。

// 假设我们有结构体Node表示二叉树节点
typedef struct Node {
    int data;
    struct Node* left, *right;
} Node;

int isCompleteBinaryTree(Node* root) {
    if (root == NULL)
        return 1; // 空树视为完全二叉树

    // 检查最后一个节点
    if (root->left != NULL && root->right != NULL && !isCompleteBinaryTree(root->right)) {
        return 0; // 右侧有未访问节点，不是完全二叉树
    }

    // 如果当前节点是叶节点且没有更多的节点，返回1
    if (!root->right && !root->left)
        return 1;

    return isCompleteBinaryTree(root->left); // 否则继续检查左侧
}