写个C语言的二叉平衡树的算法
时间: 2023-05-30 11:07:37 浏览: 53
以下是C语言的二叉平衡树的算法:
//定义二叉平衡树节点结构体
typedef struct node {
int data; //节点数据
int height; //节点高度
struct node* left; //左子树指针
struct node* right; //右子树指针
} node;
//获取节点高度
int getHeight(node* n) {
if (n == NULL) {
return 0;
}
return n->height;
}
//获取节点平衡因子
int getBalance(node* n) {
if (n == NULL) {
return 0;
}
return getHeight(n->left) - getHeight(n->right);
}
//创建新节点
node* createNode(int data) {
node* n = (node*)malloc(sizeof(node));
n->data = data;
n->height = 1;
n->left = NULL;
n->right = NULL;
return n;
}
//左旋转子树
node* leftRotate(node* n) {
node* r = n->right;
node* rl = r->left;
r->left = n;
n->right = rl;
n->height = 1 + max(getHeight(n->left), getHeight(n->right));
r->height = 1 + max(getHeight(r->left), getHeight(r->right));
return r;
}
//右旋转子树
node* rightRotate(node* n) {
node* l = n->left;
node* lr = l->right;
l->right = n;
n->left = lr;
n->height = 1 + max(getHeight(n->left), getHeight(n->right));
l->height = 1 + max(getHeight(l->left), getHeight(l->right));
return l;
}
//插入节点
node* insertNode(node* root, int data) {
if (root == NULL) {
return createNode(data);
}
if (data < root->data) {
root->left = insertNode(root->left, data);
}
else if (data > root->data) {
root->right = insertNode(root->right, data);
}
else {
return root;
}
root->height = 1 + max(getHeight(root->left), getHeight(root->right));
int balance = getBalance(root);
if (balance > 1 && data < root->left->data) {
return rightRotate(root);
}
if (balance < -1 && data > root->right->data) {
return leftRotate(root);
}
if (balance > 1 && data > root->left->data) {
root->left = leftRotate(root->left);
return rightRotate(root);
}
if (balance < -1 && data < root->right->data) {
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
//寻找最小值节点
node* findMinNode(node* root) {
while (root->left != NULL) {
root = root->left;
}
return root;
}
//删除节点
node* deleteNode(node* root, int data) {
if (root == NULL) {
return root;
}
if (data < root->data) {
root->left = deleteNode(root->left, data);
}
else if (data > root->data) {
root->right = deleteNode(root->right, data);
}
else {
if (root->left == NULL || root->right == NULL) {
node* temp = root->left ? root->left : root->right;
if (temp == NULL) {
temp = root;
root = NULL;
}
else {
*root = *temp;
}
free(temp);
}
else {
node* temp = findMinNode(root->right);
root->data = temp->data;
root->right = deleteNode(root->right, temp->data);
}
}
if (root == NULL) {
return root;
}
root->height = 1 + max(getHeight(root->left), getHeight(root->right));
int balance = getBalance(root);
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;
}