可以用c语言代码写一下上述过程吗
时间: 2024-01-22 10:02:03 浏览: 75
当然可以,以下是用 C 语言实现该过程的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct Node {
int key;
int bf; // 平衡因子
struct Node* left;
struct Node* right;
};
typedef struct Node Node;
int get_height(Node* node) {
if (node == NULL) {
return 0;
}
int left_height = get_height(node->left);
int right_height = get_height(node->right);
return (left_height > right_height) ? left_height + 1 : right_height + 1;
}
int get_balance_factor(Node* node) {
if (node == NULL) {
return 0;
}
return get_height(node->left) - get_height(node->right);
}
Node* right_rotate(Node* node) {
Node* new_root = node->left;
node->left = new_root->right;
new_root->right = node;
node->bf = get_balance_factor(node);
new_root->bf = get_balance_factor(new_root);
return new_root;
}
Node* left_rotate(Node* node) {
Node* new_root = node->right;
node->right = new_root->left;
new_root->left = node;
node->bf = get_balance_factor(node);
new_root->bf = get_balance_factor(new_root);
return new_root;
}
Node* insert_node(int key, Node* root) {
if (root == NULL) {
root = (Node*)malloc(sizeof(Node));
root->key = key;
root->bf = 0;
root->left = NULL;
root->right = NULL;
} else if (key < root->key) {
root->left = insert_node(key, root->left);
root->bf = get_balance_factor(root);
if (root->bf == 2) {
if (key < root->left->key) {
root = right_rotate(root);
} else {
root->left = left_rotate(root->left);
root = right_rotate(root);
}
}
} else if (key > root->key) {
root->right = insert_node(key, root->right);
root->bf = get_balance_factor(root);
if (root->bf == -2) {
if (key > root->right->key) {
root = left_rotate(root);
} else {
root->right = right_rotate(root->right);
root = left_rotate(root);
}
}
}
return root;
}
Node* delete_node(int key, Node* root) {
if (root == NULL) {
return root;
} else if (key < root->key) {
root->left = delete_node(key, root->left);
root->bf = get_balance_factor(root);
if (root->bf == -2) {
if (get_balance_factor(root->right) <= 0) {
root = left_rotate(root);
} else {
root->right = right_rotate(root->right);
root = left_rotate(root);
}
}
} else if (key > root->key) {
root->right = delete_node(key, root->right);
root->bf = get_balance_factor(root);
if (root->bf == 2) {
if (get_balance_factor(root->left) >= 0) {
root = right_rotate(root);
} else {
root->left = left_rotate(root->left);
root = right_rotate(root);
}
}
} else {
if (root->left == NULL && root->right == NULL) {
free(root);
root = NULL;
} else if (root->left == NULL) {
Node* temp = root;
root = root->right;
free(temp);
} else if (root->right == NULL) {
Node* temp = root;
root = root->left;
free(temp);
} else {
Node* temp = root->left;
while (temp->right != NULL) {
temp = temp->right;
}
root->key = temp->key;
root->left = delete_node(temp->key, root->left);
root->bf = get_balance_factor(root);
if (root->bf == -2) {
if (get_balance_factor(root->right) <= 0) {
root = left_rotate(root);
} else {
root->right = right_rotate(root->right);
root = left_rotate(root);
}
}
}
}
return root;
}
void print_tree(Node* root) {
if (root != NULL) {
printf("[%d(%d)]", root->key, root->bf);
if (root->left != NULL || root->right != NULL) {
printf("(");
print_tree(root->left);
printf(",");
print_tree(root->right);
printf(")");
}
}
}
int main() {
int keys[] = {16, 3, 7, 11, 9, 26, 18, 14, 15};
int num_keys = sizeof(keys) / sizeof(keys[0]);
Node* root = NULL;
for (int i = 0; i < num_keys; i++) {
root = insert_node(keys[i], root);
print_tree(root);
printf("\n");
}
printf("\n");
root = delete_node(11, root);
print_tree(root);
printf("\n");
return 0;
}
```
请注意,此代码仅演示了平衡二叉树的基本操作,并且只能处理整数类型的关键字。在实际应用中,可能需要根据具体情况进行修改。
阅读全文