给定一个二叉树(存储结构采用二叉链表表示),试设计算法判断该二叉树 是否为二叉平衡树,用C语言完成
时间: 2023-08-22 15:03:32 浏览: 146
写一算法,判断一棵二叉树是否是一棵二叉排序树。
二叉平衡树是指任意节点的左右子树的高度差不超过1的二叉树。可以通过递归的方式,对每个节点的左右子树进行判断,判断它们的高度差是否小于等于1,如果小于等于1,继续递归判断其左右子树,否则直接返回false。
以下是C语言实现的代码:
```c
// 二叉树结点的定义
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 计算二叉树的高度
int getHeight(TreeNode *root) {
if (root == NULL) {
return 0;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
return leftHeight > rightHeight ? leftHeight + 1 : rightHeight + 1;
}
// 判断一棵二叉树是否为平衡二叉树
bool isBalanced(TreeNode *root) {
if (root == NULL) {
return true;
}
int leftHeight = getHeight(root->left);
int rightHeight = getHeight(root->right);
if (abs(leftHeight - rightHeight) > 1) {
return false;
}
return isBalanced(root->left) && isBalanced(root->right);
}
```
其中,getHeight函数计算二叉树的高度,isBalanced函数则使用递归判断每个节点是否满足平衡条件。
阅读全文