用c写一个平衡二叉树的插入算法
时间: 2023-03-20 19:00:27 浏览: 97
以下是使用 C 语言编写平衡二叉树插入算法的示例代码:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义平衡二叉树节点的结构体
typedef struct node {
int value; // 节点的值
struct node *left; // 左子节点指针
struct node *right; // 右子节点指针
int height; // 节点的高度
} node_t;
// 计算节点的高度
int get_height(node_t *node) {
if (node == NULL) {
return -1;
} else {
return node->height;
}
}
// 计算节点的平衡因子
int get_balance(node_t *node) {
if (node == NULL) {
return 0;
} else {
return get_height(node->left) - get_height(node->right);
}
}
// 创建新节点
node_t *create_node(int value) {
node_t *node = (node_t*) malloc(sizeof(node_t));
node->value = value;
node->left = NULL;
node->right = NULL;
node->height = 0;
return node;
}
// 向平衡二叉树中插入新节点
node_t *insert(node_t *node, int value) {
// 如果当前节点为空,创建新节点并返回
if (node == NULL) {
return create_node(value);
}
// 如果插入的值小于当前节点的值,递归地向左子树中插入新节点
if (value < node->value) {
node->left = insert(node->left, value);
}
// 如果插入的值大于等于当前节点的值,递归地向右子树中插入新节点
else {
node->right = insert(node->right, value);
}
// 更新节点的高度
node->height = 1 + max(get_height(node->left), get_height(node->right));
// 计算节点的平衡因子
int balance = get_balance(node);
// 如果节点的平衡因子大于 1(左子树比右子树高度大),需要进行平衡调整
if (balance > 1) {
// 如果新节点插入到当前节点的左子树的左子树中,执行右旋操作
if (value < node->left->value) {
node_t *tmp = node->left;
node->left = tmp->right;
tmp->right = node;
node = tmp;
}
// 如果新节点插入到当前节点的左子树的右子树中,执行先左旋后右旋操作
else {
node_t *tmp1 = node->left;
node_t *tmp2 = tmp1->right;
tmp1->right = tmp2->left;
node->left = tmp2->right;
tmp2->left = tmp1;
tmp2->right = node;
node = tmp2;
}
}
// 如果节点的平衡因子小于 -1(右子树比左子树高度大),需要进行平衡调整
相关推荐
![txt](https://img-home.csdnimg.cn/images/20210720083642.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)