用C语言写出用一个用递归算法判断一个二叉树是否为完全二叉树的代码
时间: 2024-10-13 15:14:18 浏览: 3
在 C 语言中,我们可以使用递归来检查一个二叉树是否为完全二叉树。这里给出一个简单的函数示例,该函数接受一个二叉树节点的指针作为输入,如果这个树是完全二叉树则返回 `true`,否则返回 `false`。请注意,这个函数假设二叉树节点包含一个 `left` 和 `right` 指针指向其左右孩子,以及一个 `is_leaf` 函数来判断节点是否为叶子节点(无孩子的节点)。
```c
#include <stdbool.h>
typedef struct TreeNode {
int data;
struct TreeNode* left;
struct TreeNode* right;
bool (*is_leaf)(struct TreeNode*);
} Node;
bool isCompleteBinaryTree(Node* root) {
if (root == NULL || !(*root->is_leaf)(root)) { // 基本情况:空树或叶节点直接返回
return true;
}
// 检查左子树
if (!root->left || (!(*root->left->is_leaf)(root->left) && !isCompleteBinaryTree(root->left))) {
return false;
}
// 如果左子树是完全二叉树,检查右子树是否满足条件
if (root->left->right != NULL) {
return isCompleteBinaryTree(root->left->right);
} else {
// 左子树已经是完全二叉树,但右子树可能不完整
// 如果右子树存在且不是完整的,那么整个树也不完整
return root->right == NULL || isCompleteBinaryTree(root->right);
}
}
// 简化版本,假设每个节点都有 is_leaf 函数
bool is_leaf(Node* node) {
return node->left == NULL && node->right == NULL;
}
```