数据结构平衡二叉树C语言代码
时间: 2023-07-15 08:08:50 浏览: 93
当然,下面是一个简单的平衡二叉树的C语言代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义二叉树节点结构
typedef struct Node {
int data; // 节点值
struct Node* left; // 左子节点指针
struct Node* right; // 右子节点指针
int height; // 节点高度
} Node;
// 计算节点的高度
int height(Node* node) {
if (node == NULL) {
return 0;
}
return node->height;
}
// 获取两个数中较大的值
int max(int a, int b) {
return (a > b) ? a : b;
}
// 创建一个新节点
Node* createNode(int data) {
Node* newNode = (Node*)malloc(sizeof(Node));
newNode->data = data;
newNode->left = NULL;
newNode->right = NULL;
newNode->height = 1;
return newNode;
}
// 执行右旋操作
Node* rightRotate(Node* y) {
Node* x = y->left;
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;
}
// 执行左旋操作
Node* leftRotate(Node* x) {
Node* y = x->right;
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 getBalanceFactor(Node* node) {
if (node == NULL) {
return 0;
}
return height(node->left) - height(node->right);
}
// 插入节点
Node* insertNode(Node* node, int data) {
if (node == NULL) {
return createNode(data);
}
if (data < node->data) {
node->left = insertNode(node->left, data);
} else if (data > node->data) {
node->right = insertNode(node->right, data);
} else {
// 忽略插入相同的节点
return node;
}
node->height = 1 + max(height(node->left), height(node->right));
int balanceFactor = getBalanceFactor(node);
// 左-左情况,执行右旋操作
if (balanceFactor > 1 && data < node->left->data) {
return rightRotate(node);
}
// 右-右情况,执行左旋操作
if (balanceFactor < -1 && data > node->right->data) {
return leftRotate(node);
}
// 左-右情况,先对左子节点进行左旋,再对当前节点进行右旋
if (balanceFactor > 1 && data > node->left->data) {
node->left = leftRotate(node->left);
return rightRotate(node);
}
// 右-左情况,先对右子节点进行右旋,再对当前节点进行左旋
if (balanceFactor < -1 && data < node->right->data) {
node->right = rightRotate(node->right);
return leftRotate(node);
}
return node;
}
// 中序遍历二叉树
void inorderTraversal(Node* root) {
if (root != NULL) {
inorderTraversal(root->left);
printf("%d ", root->data);
inorderTraversal(root->right);
}
}
int main() {
Node* root = NULL;
root = insertNode(root, 10);
root = insertNode(root, 20);
root = insertNode(root, 30);
root = insertNode(root, 40);
root = insertNode(root, 50);
root = insertNode(root, 25);
printf("中序遍历结果:");
inorderTraversal(root);
return 0;
}
```
这段代码实现了一个平衡二叉树的插入和中序遍历操作。你可以根据需要自行修改和扩展。希望对你有所帮助!