判断二叉树是不是二叉平衡树,用c语言学
时间: 2024-02-03 14:13:14 浏览: 26
判断二叉树是否为平衡树,可以通过递归的方式判断其左右子树的高度差是否小于等于1。具体实现可以参考以下代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
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 : 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) { // 如果左右子树高度差大于1,不是平衡树
return false;
}
return isBalanced(root->left) && isBalanced(root->right); // 递归判断左右子树是否都是平衡树
}
// 测试代码
int main() {
TreeNode* root = (TreeNode*)malloc(sizeof(TreeNode));
root->val = 1;
root->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->val = 2;
root->right = (TreeNode*)malloc(sizeof(TreeNode));
root->right->val = 2;
root->left->left = (TreeNode*)malloc(sizeof(TreeNode));
root->left->left->val = 3;
root->left->right = (TreeNode*)malloc(sizeof(TreeNode));
root->left->right->val = 3;
root->left->left->left = NULL;
root->left->left->right = NULL;
root->left->right->left = NULL;
root->left->right->right = NULL;
root->right->left = NULL;
root->right->right = NULL;
bool result = isBalanced(root);
if (result) {
printf("This is a balanced binary tree.\n");
} else {
printf("This is not a balanced binary tree.\n");
}
return 0;
}
```
上述代码中,首先定义了二叉树的结构体,包含节点的值、左子树和右子树。然后实现了一个计算树高的函数 `getHeight`,通过递归计算当前节点的左右子树高度,然后取左右子树高度的最大值再加1,就可以得到当前节点的高度。接着实现了一个判断二叉树是否为平衡树的函数 `isBalanced`,首先计算当前节点的左右子树高度,如果左右子树高度差大于1,则当前节点不是平衡树。否则,递归判断当前节点的左右子树是否都是平衡树。最后,通过测试代码构建了一棵二叉树,并调用 `isBalanced` 函数判断其是否为平衡树。