平衡二叉树的判定,要c语言完整代码
时间: 2023-10-26 20:10:02 浏览: 71
以下是一个简单的平衡二叉树判定的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点
typedef struct TreeNode {
int val;
int height;
struct TreeNode *left;
struct TreeNode *right;
} TreeNode;
// 计算节点高度
int height(TreeNode *node) {
if (node == NULL) {
return 0;
} else {
return node->height;
}
}
// 计算节点平衡因子
int balanceFactor(TreeNode *node) {
return height(node->left) - height(node->right);
}
// 更新节点高度
void updateHeight(TreeNode *node) {
node->height = 1 + fmax(height(node->left), height(node->right));
}
// 左旋操作
TreeNode* leftRotate(TreeNode *node) {
TreeNode *newRoot = node->right;
node->right = newRoot->left;
newRoot->left = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
// 右旋操作
TreeNode* rightRotate(TreeNode *node) {
TreeNode *newRoot = node->left;
node->left = newRoot->right;
newRoot->right = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
// 插入节点
TreeNode* insertNode(TreeNode *node, int val) {
if (node == NULL) {
node = (TreeNode*)malloc(sizeof(TreeNode));
node->val = val;
node->height = 1;
node->left = NULL;
node->right = NULL;
} else if (val < node->val) {
node->left = insertNode(node->left, val);
} else {
node->right = insertNode(node->right, val);
}
// 平衡调整
int balance = balanceFactor(node);
if (balance > 1 && val < node->left->val) {
return rightRotate(node);
} else if (balance < -1 && val > node->right->val) {
return leftRotate(node);
} else if (balance > 1 && val > node->left->val) {
node->left = leftRotate(node->left);
return rightRotate(node);
} else if (balance < -1 && val < node->right->val) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
updateHeight(node);
return node;
}
// 判断是否为平衡二叉树
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;
}
int main() {
TreeNode *root = NULL;
root = insertNode(root, 3);
root = insertNode(root, 2);
root = insertNode(root, 1);
root = insertNode(root, 4);
root = insertNode(root, 5);
root = insertNode(root, 6);
printf("%d\n", isBalanced(root)); // 输出1,代表是平衡二叉树
return 0;
}
```
该代码中实现了平衡二叉树的插入操作,以及判断一棵二叉树是否为平衡二叉树的函数。在插入新节点时,会自动进行平衡调整。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![-](https://csdnimg.cn/download_wenku/file_type_column_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)