平衡二叉树,c语言代码
时间: 2023-10-17 18:18:33 浏览: 41
以下是平衡二叉树的C语言代码:
```
#include <stdio.h>
#include <stdlib.h>
// 定义平衡二叉树的节点结构体
struct AVLNode {
int data; // 数据
struct AVLNode* left; // 左子树指针
struct AVLNode* right; // 右子树指针
int height; // 节点高度
};
// 获取节点高度
int getHeight(struct AVLNode* node) {
if (node == NULL) {
return -1;
}
return node->height;
}
// 获取节点的平衡因子
int getBalanceFactor(struct AVLNode* node) {
return getHeight(node->left) - getHeight(node->right);
}
// 右旋函数
struct AVLNode* rightRotate(struct AVLNode* y) {
struct AVLNode* x = y->left;
struct AVLNode* T2 = x->right;
// 执行旋转操作
x->right = y;
y->left = T2;
// 更新节点高度
y->height = 1 + fmax(getHeight(y->left), getHeight(y->right));
x->height = 1 + fmax(getHeight(x->left), getHeight(x->right));
// 返回新的根节点
return x;
}
// 左旋函数
struct AVLNode* leftRotate(struct AVLNode* x) {
struct AVLNode* y = x->right;
struct AVLNode* T2 = y->left;
// 执行旋转操作
y->left = x;
x->right = T2;
// 更新节点高度
x->height = 1 + fmax(getHeight(x->left), getHeight(x->right));
y->height = 1 + fmax(getHeight(y->left), getHeight(y->right));
// 返回新的根节点
return y;
}
// 创建一个新节点
struct AVLNode* createNode(int data) {
struct AVLNode* node = (struct AVLNode*)malloc(sizeof(struct AVLNode));
node->data = data;
node->left = NULL;
node->right = NULL;
node->height = 0;
return node;
}
// 插入节点
struct AVLNode* insertNode(struct AVLNode* node, int data) {
if (node == NULL) {
return createNode(data);
}
if (data < node->data) {
node->left = insertNode(node->left, data);
} else if (data > node->data) {
node->right = insertNode(node->right, data);
} else {
return node; // 如果节点已经存在,则直接返回该节点
}
// 更新节点高度
node->height = 1 + fmax(getHeight(node->left), getHeight(node->right));
// 获取平衡因子
int balanceFactor = getBalanceFactor(node);
// 左子树比右子树高,需要进行右旋操作
if (balanceFactor > 1 && data < node->left->data) {
return rightRotate(node);
}
// 右子树比左子树高,需要进行左旋操作
if (balanceFactor < -1 && data > node->right->data) {
return leftRotate(node);
}
// 左子树比右子树高,需要进行左右旋转操作
if (balanceFactor > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// 右子树比左子树高,需要进行右左旋转操作
if (balanceFactor < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
// 返回当前节点
return node;
}
// 中序遍历平衡二叉树
void inorderTraversal(struct AVLNode* node) {
if (node == NULL) {
return;
}
inorderTraversal(node->left);
printf("%d ", node->data);
inorderTraversal(node->right);
}
int main() {
struct AVLNode* root = NULL;
// 插入节点
root = insertNode(root, 10);
root = insertNode(root, 20);
root = insertNode(root, 30);
root = insertNode(root, 40);
root = insertNode(root, 50);
root = insertNode(root, 25);
// 中序遍历平衡二叉树
printf("Inorder Traversal of AVL tree: ");
inorderTraversal(root);
return 0;
}
```