生成avl树的代码c++
时间: 2023-05-26 20:03:46 浏览: 72
以下是生成AVL树的C代码示例:
```
#include <stdio.h>
#include <stdlib.h>
// AVL树节点
typedef struct avl_node_t {
int data;
struct avl_node_t *left;
struct avl_node_t *right;
int height;
} avl_node_t;
// 获取节点高度
int height(avl_node_t *node) {
if (node == NULL) {
return 0;
} else {
return node->height;
}
}
// 获取最大值
int max(int a, int b) {
if (a > b) {
return a;
} else {
return b;
}
}
// 创建新节点
avl_node_t* create_node(int data) {
avl_node_t *node = (avl_node_t*) malloc(sizeof(avl_node_t));
node->data = data;
node->left = NULL;
node->right = NULL;
node->height = 1;
return node;
}
// 右旋
avl_node_t* rotate_right(avl_node_t *y) {
avl_node_t *x = y->left;
avl_node_t *B = x->right;
// 右旋转
x->right = y;
y->left = B;
// 更新高度
y->height = max(height(y->left), height(y->right)) + 1;
x->height = max(height(x->left), height(x->right)) + 1;
// 返回新的根节点
return x;
}
// 左旋
avl_node_t* rotate_left(avl_node_t *x) {
avl_node_t *y = x->right;
avl_node_t *B = y->left;
// 左旋转
y->left = x;
x->right = B;
// 更新高度
x->height = max(height(x->left), height(x->right)) + 1;
y->height = max(height(y->left), height(y->right)) + 1;
// 返回新的根节点
return y;
}
// 获取平衡因子
int get_balance(avl_node_t *node) {
if (node == NULL) {
return 0;
} else {
return height(node->left) - height(node->right);
}
}
// 添加节点
avl_node_t* insert_node(avl_node_t *node, int data) {
// 如果节点为空,直接创建节点
if (node == NULL) {
return create_node(data);
}
if (data < node->data) {
// 插入到左子树中
node->left = insert_node(node->left, data);
} else if (data > node->data) {
// 插入到右子树中
node->right = insert_node(node->right, data);
} else {
// 如果节点已经存在,则返回原节点
return node;
}
// 更新节点高度
node->height = max(height(node->left), height(node->right)) + 1;
// 获取当前节点的平衡因子
int balance = get_balance(node);
// 如果平衡因子大于1,需要做旋转操作
if (balance > 1) {
if (data < node->left->data) {
// 左子树的左边
return rotate_right(node);
} else if (data > node->left->data) {
// 左子树的右边
node->left = rotate_left(node->left);
return rotate_right(node);
}
} else if (balance < -1) {
if (data > node->right->data) {
// 右子树的右边
return rotate_left(node);
} else if (data < node->right->data) {
// 右子树的左边
node->right = rotate_right(node->right);
return rotate_left(node);
}
}
// 已经平衡,返回当前节点
return node;
}
// 中序遍历AVL树
void inorder_traversal(avl_node_t *node) {
if (node == NULL) {
return;
}
inorder_traversal(node->left);
printf("%d ", node->data);
inorder_traversal(node->right);
}
int main() {
avl_node_t *root = NULL;
int data;
printf("输入AVL树节点数据,以-1结束:\n");
scanf("%d", &data);
while (data != -1) {
root = insert_node(root, data);
scanf("%d", &data);
}
printf("中序遍历AVL树:\n");
inorder_traversal(root);
return 0;
}
```
以上代码演示了如何创建新节点、获取高度、添加节点、获取平衡因子和做旋转操作等。在这个示例中,程序根据用户输入创建了一个AVL树,然后对树进行中序遍历,输出树节点数据。