C语言代码创建一个有n个结点的二叉链存储结构完全二叉树和非完全二叉树、判断该二叉树是否为完全二叉树
时间: 2024-05-09 22:13:21 浏览: 99
C++基于递归和非递归算法判定两个二叉树结构是否完全相同(结构和数据都相同)
5星 · 资源好评率100%
创建一个有n个结点的完全二叉树可以采用数组来存储,而非完全二叉树则需要使用链表来存储。以下是完全二叉树和非完全二叉树的创建方法:
完全二叉树的创建:
```c
#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;
}
```
非完全二叉树的创建:
```c
#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;
}
```
判断二叉树是否为完全二叉树的方法:
在层次遍历的过程中,如果某个结点的左子树为空,而右子树不为空,则该树不是完全二叉树;或者在某一层中,如果某个结点没有左子树或右子树,那么这个结点后面的所有结点都必须是叶子结点,否则该树不是完全二叉树。
阅读全文