C语言代码创建一个有n个结点的二叉链存储结构完全二叉树和非完全二叉树、判断该二叉树是否为完全二叉树

创建一个有n个结点的完全二叉树可以采用数组来存储，而非完全二叉树则需要使用链表来存储。以下是完全二叉树和非完全二叉树的创建方法：

完全二叉树的创建：

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

#define MAXSIZE 100

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode, *Tree;

Tree CreateCompleteBinaryTree(int arr[], int n)
{
    Tree t[MAXSIZE];
    for (int i = 1; i <= n; i++) {
        t[i] = (TreeNode *)malloc(sizeof(TreeNode));
        t[i]->data = arr[i - 1];
        t[i]->left = t[i]->right = NULL;
    }
    for (int i = 1; i <= n / 2; i++) {
        if (i * 2 <= n) t[i]->left = t[i * 2];
        if (i * 2 + 1 <= n) t[i]->right = t[i * 2 + 1];
    }
    return t;
}

int main()
{
    int arr[] = {1, 2, 3, 4, 5, 6};
    int n = sizeof(arr) / sizeof(int);
    Tree root = CreateCompleteBinaryTree(arr, n);
    return 0;
}

非完全二叉树的创建：

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

typedef struct TreeNode {
    int data;
    struct TreeNode *left;
    struct TreeNode *right;
}TreeNode, *Tree;

void CreateNonCompleteBinaryTree(Tree *root)
{
    int val;
    scanf("%d", &val);
    if (val == -1) {
        *root = NULL;
        return;
    }
    *root = (TreeNode *)malloc(sizeof(TreeNode));
    (*root)->data = val;
    CreateNonCompleteBinaryTree(&((*root)->left));
    CreateNonCompleteBinaryTree(&((*root)->right));
}

int IsCompleteBinaryTree(Tree root)
{
    if (root == NULL) return 1;
    int level = 0;
    Tree q[MAXSIZE];
    int front = -1, rear = -1;
    q[++rear] = root;
    while (front != rear) {
        int len = rear - front;
        level++;
        while (len--) {
            front++;
            if (q[front] == NULL) {
                for (int i = front + 1; i <= rear; i++) {
                    if (q[i] != NULL) return 0;
                }
                return 1;
            }
            q[++rear] = q[front]->left;
            q[++rear] = q[front]->right;
        }
    }
    return 1;
}

int main()
{
    Tree root;
    CreateNonCompleteBinaryTree(&root);
    int isComplete = IsCompleteBinaryTree(root);
    if (isComplete) printf("This is a complete binary tree\n");
    else printf("This is not a complete binary tree\n");
    return 0;
}

判断二叉树是否为完全二叉树的方法：

在层次遍历的过程中，如果某个结点的左子树为空，而右子树不为空，则该树不是完全二叉树；或者在某一层中，如果某个结点没有左子树或右子树，那么这个结点后面的所有结点都必须是叶子结点，否则该树不是完全二叉树。