C语言实现,己知一棵以二叉链表方式存储的二叉树,判断该二叉树是否是一棵完全二叉树
时间: 2025-01-05 14:39:52 浏览: 38
在C语言中,判断一颗以二叉链表方式存储的二叉树是否为完全二叉树,可以通过遍历树节点并检查每个层是否都是满的,除了最后一层外,如果不满也是从左到右填满。以下是简单的步骤:
1. 定义一个辅助函数 `isCompleteTree(node, height)`,其中 `node` 是当前遍历的节点,`height` 是当前二叉树的高度。
2. 遍历树直到找到空节点或达到最大高度:
- 如果遇到非空节点,继续向下搜索。
- 当层的高度小于前一层,说明不是完全二叉树。
3. 检查最后一个非空层:如果它没有从左到右完全填充,则树不是完全二叉树。
```c
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
int isCompleteBinaryTree(TreeNode* root) {
int height = 0;
if (root == NULL) return 1; // 空树视为完全二叉树
while (root && root->left != NULL && root->right != NULL) { // 一直向上走,直到到达叶子节点或非完整层
height++;
root = root->right->right; // 跳过当前层的所有节点,直接指向下一层最右边的节点
}
// 检查剩余部分是否从左到右填充
for (TreeNode* node = root; node != NULL; node = node->left) {
if (node->right != NULL) return 0; // 如果有非空节点在未完成层的右侧,则不是完全二叉树
}
return 1; // 否则,树是完全二叉树
}
```
阅读全文
相关推荐


















