用C语言实现平衡二叉树的判定,用递归创建树
时间: 2024-02-18 19:03:48 浏览: 21
好的,我知道了您的问题。以下是C语言实现平衡二叉树的判定,用递归创建树的代码:
```
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树结构体
typedef struct TreeNode {
int val;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 创建新节点
TreeNode* newNode(int val) {
TreeNode* node = (TreeNode*) malloc(sizeof(TreeNode));
node->val = val;
node->left = NULL;
node->right = NULL;
return node;
}
// 计算树的高度
int height(TreeNode* root) {
if (root == NULL) return 0;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
return (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// 判断平衡二叉树
int isBalanced(TreeNode* root) {
if (root == NULL) return 1;
int leftHeight = height(root->left);
int rightHeight = height(root->right);
if (abs(leftHeight - rightHeight) <= 1 && isBalanced(root->left) && isBalanced(root->right)) {
return 1;
}
return 0;
}
// 创建平衡二叉树
TreeNode* createBalancedTree(int arr[], int start, int end) {
if (start > end) return NULL;
int mid = (start + end) / 2;
TreeNode* root = newNode(arr[mid]);
root->left = createBalancedTree(arr, start, mid - 1);
root->right = createBalancedTree(arr, mid + 1, end);
return root;
}
int main() {
int arr[] = {1, 2, 3, 4, 5, 6, 7};
int n = sizeof(arr) / sizeof(arr[0]);
TreeNode* root = createBalancedTree(arr, 0, n - 1);
if (isBalanced(root)) {
printf("这是一棵平衡二叉树\n");
} else {
printf("这不是一棵平衡二叉树\n");
}
return 0;
}
```
以上代码实现了创建平衡二叉树并判断是否为平衡二叉树,可以根据需要进行修改。