平衡二叉树的c语言代码
时间: 2023-06-22 14:25:05 浏览: 53
以下是平衡二叉树的 C 语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct AVLNode {
int data;
struct AVLNode *left;
struct AVLNode *right;
int height;
} AVLNode;
int max(int a, int b) {
return (a > b) ? a : b;
}
int getHeight(AVLNode *node) {
if (node == NULL) {
return 0;
}
return node->height;
}
AVLNode *createNode(int data) {
AVLNode *node = (AVLNode *) malloc(sizeof(AVLNode));
node->data = data;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
AVLNode *rightRotate(AVLNode *node) {
AVLNode *leftChild = node->left;
AVLNode *rightGrandChild = leftChild->right;
leftChild->right = node;
node->left = rightGrandChild;
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
leftChild->height = max(getHeight(leftChild->left), getHeight(leftChild->right)) + 1;
return leftChild;
}
AVLNode *leftRotate(AVLNode *node) {
AVLNode *rightChild = node->right;
AVLNode *leftGrandChild = rightChild->left;
rightChild->left = node;
node->right = leftGrandChild;
node->height = max(getHeight(node->left), getHeight(node->right)) + 1;
rightChild->height = max(getHeight(rightChild->left), getHeight(rightChild->right)) + 1;
return rightChild;
}
int getBalance(AVLNode *node) {
if (node == NULL) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}
AVLNode *insertNode(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 = max(getHeight(node->left), getHeight(node->right)) + 1;
int balance = getBalance(node);
if (balance > 1 && data < node->left->data) {
return rightRotate(node);
}
if (balance < -1 && data > node->right->data) {
return leftRotate(node);
}
if (balance > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
if (balance < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
void inorderTraversal(AVLNode *node) {
if (node != NULL) {
inorderTraversal(node->left);
printf("%d ", node->data);
inorderTraversal(node->right);
}
}
int main() {
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 the constructed AVL tree is: \n");
inorderTraversal(root);
return 0;
}
```
这份代码实现了平衡二叉树的插入操作和中序遍历操作。当然,还可以实现删除操作等其他功能。