C语言判断完全二叉树
时间: 2023-11-08 07:01:47 浏览: 169
在C语言中,可以通过层次遍历算法来判断一个二叉树是否是完全二叉树。具体的做法是,首先将根节点加入队列,然后进行循环,每次从队列中取出一个节点,并将其左右子节点加入队列。在这个过程中,如果遇到了空节点,则需要检查后面是否还有非空节点。如果有非空节点出现在空节点后面,则说明该二叉树不是完全二叉树。
代码示例:
```c
#include <stdio.h>
#include <stdbool.h>
// 定义二叉树结点
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
// 判断完全二叉树
bool isCompleteBinaryTree(TreeNode* root) {
// 定义一个队列,用于层次遍历
TreeNode* queue[100];
int front = 0, rear = 0;
bool flag = false; // 标记是否遇到空结点
// 将根节点加入队列
queue[rear++] = root;
// 层次遍历
while (front != rear) {
TreeNode* node = queue[front++];
if (node == NULL) {
flag = true;
} else {
if (flag) {
// 如果遇到空结点后面还有非空结点,则不是完全二叉树
return false;
}
queue[rear++] = node->left;
queue[rear++] = node->right;
}
}
return true;
}
int main() {
// 创建一棵二叉树
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->data = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->data = 2;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->data = 4;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->data = 5;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->data = 3;
root->right->left = (TreeNode*)malloc(sizeof(TreeNode));
root->right->left->data = 6;
root->right->left->left = NULL; root->right->left->right = NULL;
root->right->right = NULL;
// 判断是否是完全二叉树
bool result = isCompleteBinaryTree(root);
if (result) {
printf("这是一棵完全二叉树。\n");
} else {
printf("这不是一棵完全二叉树。\n");
}
// 释放二叉树的内存
return 0;
}
```
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![docx](https://img-home.csdnimg.cn/images/20210720083331.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)