判断是否为完全二叉树 C语言
时间: 2024-10-17 15:04:58 浏览: 4
在C语言中,判断一个给定的二叉树是否为完全二叉树可以采用递归或迭代的方式。完全二叉树是一种特殊的二叉树,除了最后一层外,每一层都尽可能地填满节点,且所有叶子节点都在最底层。
以下是递归函数的一个简单示例:
```c
#include <stdio.h>
#include <stdbool.h>
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
bool isCompleteBinaryTree(TreeNode* root) {
if (root == NULL) return true; // 空树视为完全二叉树
bool is_left_full = (root->left == NULL && root->right == NULL); // 最左子树为空,则上一层也是完全填充
bool is_right_full = (root->left != NULL && root->right == NULL);
// 如果根节点不是最右节点,且左右子树状态相反,说明这不是完全二叉树
if (!is_left_full && !is_right_full) {
return false;
}
// 递归检查左子树和右子树
return isCompleteBinaryTree(root->left) && isCompleteBinaryTree(root->right);
}
```
对于非递归版本,你可以使用队列或栈辅助遍历。这里给出的是递归方法的简化版,实际应用时需要考虑边界条件和其他细节。
阅读全文