用c语言数据结构写一个假设二叉树采用二叉链表的方式储存,设计算法判断二叉树T是不是完全二叉树的代码
时间: 2024-11-20 09:38:45 浏览: 37
在C语言中,我们可以使用递归的方式来判断一个二叉链表表示的二叉树是否是完全二叉树。完全二叉树的特点是从上到下所有层次都是满的,除了最后一层外,从左到右每个节点都没有空位。
下面是一个简单的函数`isCompleteBinaryTree(node)`,它接收树的根节点作为输入:
```c
typedef struct TreeNode {
int val;
struct TreeNode* left;
struct TreeNode* right;
} TreeNode;
int isCompleteBinaryTree(TreeNode* node) {
// 基本情况:空树或只有一个节点的树都是完全二叉树
if (!node) return 1;
// 如果不是叶子节点且左右孩子都存在,那么需要检查左子树和右子树也是完全二叉树
if (node->left && !isCompleteBinaryTree(node->left)) return 0;
if (node->right && !isCompleteBinaryTree(node->right)) return 0;
// 如果当前节点是最后一个非空节点,并且其所有子节点都是空的,也满足完全二叉树条件
if (!node->left && !node->right)
return 1; // 只有一个叶子节点
// 否则,当前节点还有剩余的子节点,但是应该已经满了,返回false
return 0;
}
```
这个函数首先处理基本情况,然后通过递归遍历左子树和右子树,如果其中任何一个不是完全二叉树,那么整个树也不是。如果到达了最后的叶子节点并且满足完全二叉树的条件,就返回1。
阅读全文