完全二叉树问题。要求： 1、创建一个有n个结点的二叉链存储结构完全二叉树； 2、判断该二叉树是否为完全二叉树； 创建一个有n个结点的二叉链存储结构非完全二叉树，并判断该二叉树是否为完全二叉树。

创建一个有n个结点的完全二叉树的过程如下：

1. 如果n为0，则返回空树。

2. 如果n为1，则创建一个只有根节点的树。

3. 如果n为奇数，则将n减1，使之为偶数。

4. 将n除以2，并将商保存为m。

5. 创建一个根节点。

6. 递归创建一个有m个结点的完全二叉树，并将其作为根节点的左子树。

7. 递归创建一个有m个结点的完全二叉树，并将其作为根节点的右子树。

8. 返回根节点。

判断一个二叉树是否为完全二叉树的方法如下：

1. 对于一个二叉树的每个节点，如果它有右子树但是没有左子树，则该二叉树不是完全二叉树。

2. 对于一个二叉树的每个节点，如果它有左子树但是没有右子树，则该二叉树只有当该节点所在的层次为最后一层或者倒数第二层时才是完全二叉树。

3. 对于一个二叉树的每个节点，如果它既有左子树又有右子树，则该二叉树只有当该节点的左子树和右子树都是完全二叉树时才是完全二叉树。

创建一个有n个结点的非完全二叉树，并判断其是否为完全二叉树的方法如下：

1. 首先创建一个有n个结点的二叉树。

2. 找到该二叉树中最大的编号k，使得编号1到k的节点都存在。

3. 对于编号k+1到n的节点，如果它们存在，则该二叉树不是完全二叉树。

4. 如果该二叉树中所有节点都存在，则按照完全二叉树的方法进行判断即可。

注意：在这里，节点的编号指的是按照完全二叉树的方式给每个节点编号，根节点的编号为1，左子节点的编号为2k，右子节点的编号为2k+1。

相关问题

用C语言代码实现完全二叉树要求: (1)创建一个有n个结点的二叉链存储结构完全二叉树(参见习题8-34)。 (2)判断该二叉树是否为完全二叉树。 (3)创建一一个有 n个结点的二叉链存储结构非完全二叉树，并判断该二叉树是否为完全二叉树。

你好！感谢您的提问。以下是我对您的问题的回答：

1. 用C语言代码实现完全二叉树：

完全二叉树是指除了最后一层的节点不满外，其它每一层的节点数都是最大节点数。而最后一层的节点都靠左排列。所以我们需要根据这个特点来构建完全二叉树。

首先，我们需要定义完全二叉树的节点结构体：

struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
};

接着，我们可以用数组来表示完全二叉树。因为完全二叉树的节点是从上到下、从左到右依次排列的，所以我们可以按照这个顺序将二叉树的节点存储在一个数组中。具体代码实现如下：

struct TreeNode* createCompleteBinaryTree(int* nums, int n) {
struct TreeNode** nodes = (struct TreeNode**)malloc(n * sizeof(struct TreeNode*));
int i;
for (i = 0; i < n; i++) {
if (nums[i] == -1) {
nodes[i] = NULL;
} else {
struct TreeNode* node = (struct TreeNode*)malloc(sizeof(struct TreeNode));
node->val = nums[i];
nodes[i] = node;
}
}
for (i = 0; i < n; i++) {
if (!nodes[i]) {
continue;
}
int left = i * 2 + 1;
int right = i * 2 + 2;
if (left < n) {
nodes[i]->left = nodes[left];
}
if (right < n) {
nodes[i]->right = nodes[right];
}
}
return nodes[0];
}

上面的代码中，nums数组是按照二叉树的从上到下、从左到右的顺序存储的节点值，-1表示该节点为空。

2. 判断该二叉树是否为完全二叉树：

要判断是否为完全二叉树，我们需要使用bfs（宽度优先搜索）遍历的方式遍历整棵树。具体代码实现如下：

bool isCompleteBinaryTree(struct TreeNode* root) {
if (!root) {
return true;
}
struct TreeNode** queue = (struct TreeNode**)malloc(1000 * sizeof(struct TreeNode*));
int front = 0;
int rear = 0;
bool flag = false;
queue[rear++] = root;
while (front != rear) {
struct TreeNode* node = queue[front++];
if (!node) {
flag = true;
} else {
if (flag) {
return false;
}
queue[rear++] = node->left;
queue[rear++] = node->right;
}
}
return true;
}

上面的代码中，我们使用队列来实现宽度优先搜索，如果遇到空节点，则将之后的所有节点都应该是空节点。

3. 创建一个有n个结点的二叉链存储结构非完全二叉树，并判断该二叉树是否为完全二叉树。

我们可以按照以下方式构建一个非完全二叉树：将值为1~n的节点插入到二叉树中，插入顺序是随机的。具体代码实现如下：

struct TreeNode* createNonCompleteBinaryTree(int n) {
struct TreeNode* root = NULL;
int* nums = (int*)malloc(n * sizeof(int));
int i;
for (i = 0; i < n; i++) {
nums[i] = i + 1;
}
for (i = 0; i < n; i++) {
int j = rand() % (n - i) + i;
int tmp = nums[i];
nums[i] = nums[j];
nums[j] = tmp;
}
for (i = 0; i < n; i++) {
root = insert(root, nums[i]);
}
return root;
}

上面的代码中，我们首先用一个数组按顺序存储1~n个数字，然后随机打乱这个数组，将数字插入到二叉树中。

我们可以调用上面的isCompleteBinaryTree函数来判断这颗二叉树是否为完全二叉树。

希望我的回答能够帮到您。如果您有其他问题，可以继续提问哟。

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;
}

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

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