重新说明一下,我的意思是说将你提出的AVL树部分代码使用C语言实现
时间: 2023-06-16 14:05:23 浏览: 46
好的,以下是使用C语言实现的AVL树部分代码:
```c
#include <stdio.h>
#include <stdlib.h>
// AVL树节点结构体
struct Node {
int key;
int height;
struct Node* left;
struct Node* right;
};
// 获取节点高度
int height(struct Node* node) {
if (node == NULL)
return 0;
return node->height;
}
// 获取两个数中较大的数
int max(int a, int b) {
return (a > b) ? a : b;
}
// 创建新节点
struct Node* newNode(int key) {
struct Node* node = (struct Node*)malloc(sizeof(struct Node));
node->key = key;
node->height = 1;
node->left = NULL;
node->right = NULL;
return node;
}
// 右旋转
struct Node* rightRotate(struct Node* y) {
struct Node* x = y->left;
struct Node* T2 = x->right;
// 旋转
x->right = y;
y->left = T2;
// 更新高度
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
// 返回新根节点
return x;
}
// 左旋转
struct Node* leftRotate(struct Node* x) {
struct Node* y = x->right;
struct Node* T2 = y->left;
// 旋转
y->left = x;
x->right = T2;
// 更新高度
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
// 返回新根节点
return y;
}
// 获取平衡因子
int getBalance(struct Node* node) {
if (node == NULL)
return 0;
return height(node->left) - height(node->right);
}
// 插入节点
struct Node* insert(struct Node* node, int key) {
// 执行标准BST插入
if (node == NULL)
return newNode(key);
if (key < node->key)
node->left = insert(node->left, key);
else if (key > node->key)
node->right = insert(node->right, key);
else // 如果key已经存在
return node;
// 更新节点高度
node->height = 1 + max(height(node->left), height(node->right));
// 获取节点的平衡因子
int balance = getBalance(node);
// 如果节点不平衡,则有以下4种情况
// 左左情况
if (balance > 1 && key < node->left->key)
return rightRotate(node);
// 右右情况
if (balance < -1 && key > node->right->key)
return leftRotate(node);
// 左右情况
if (balance > 1 && key > node->left->key) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// 右左情况
if (balance < -1 && key < node->right->key) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
// 如果节点平衡,则返回原始节点
return node;
}
// 获取最小值节点
struct Node* minValueNode(struct Node* node) {
struct Node* current = node;
while (current->left != NULL)
current = current->left;
return current;
}
// 删除节点
struct Node* deleteNode(struct Node* root, int key) {
// 执行标准BST删除
if (root == NULL)
return root;
if (key < root->key)
root->left = deleteNode(root->left, key);
else if (key > root->key)
root->right = deleteNode(root->right, key);
else {
// 如果节点只有一个或没有子节点
if ((root->left == NULL) || (root->right == NULL)) {
struct Node* temp = root->left ? root->left : root->right;
// 没有子节点的情况
if (temp == NULL) {
temp = root;
root = NULL;
} else // 有一个子节点的情况
*root = *temp;
free(temp);
} else {
// 如果节点有两个子节点,则获取右子树的最小值节点
struct Node* temp = minValueNode(root->right);
// 将右子树的最小值节点赋值给当前节点
root->key = temp->key;
// 删除右子树的最小值节点
root->right = deleteNode(root->right, temp->key);
}
}
// 如果树为空,则直接返回
if (root == NULL)
return root;
// 更新节点高度
root->height = 1 + max(height(root->left), height(root->right));
// 获取节点的平衡因子
int balance = getBalance(root);
// 如果节点不平衡,则有以下4种情况
// 左左情况
if (balance > 1 && getBalance(root->left) >= 0)
return rightRotate(root);
// 左右情况
if (balance > 1 && getBalance(root->left) < 0) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
// 右右情况
if (balance < -1 && getBalance(root->right) <= 0)
return leftRotate(root);
// 右左情况
if (balance < -1 && getBalance(root->right) > 0) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
// 如果节点平衡,则返回原始节点
return root;
}
// 中序遍历
void inOrder(struct Node* root) {
if (root == NULL)
return;
inOrder(root->left);
printf("%d ", root->key);
inOrder(root->right);
}
// 测试程序
int main() {
struct Node* root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
printf("Inorder traversal of the constructed AVL tree: \n");
inOrder(root);
root = deleteNode(root, 30);
printf("\nInorder traversal after deletion of 30: \n");
inOrder(root);
return 0;
}
```
希望对你有所帮助。