能将平衡二叉树的C语言编程出来吗
时间: 2023-12-20 14:11:54 浏览: 47
当然可以,以下是基于C语言实现平衡二叉树的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义平衡二叉树的结构体
typedef struct AVLNode {
int key;
int height;
struct AVLNode *left;
struct AVLNode *right;
} AVLNode;
// 获取节点高度
int getHeight(AVLNode *node) {
if (node == NULL) {
return 0;
}
return node->height;
}
// 获取节点平衡因子
int getBalanceFactor(AVLNode *node) {
if (node == NULL) {
return 0;
}
return getHeight(node->left) - getHeight(node->right);
}
// 更新节点高度
void updateHeight(AVLNode *node) {
node->height = 1 + (getHeight(node->left) > getHeight(node->right) ? getHeight(node->left) : getHeight(node->right));
}
// 左旋操作
AVLNode *leftRotate(AVLNode *node) {
AVLNode *newRoot = node->right;
node->right = newRoot->left;
newRoot->left = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
// 右旋操作
AVLNode *rightRotate(AVLNode *node) {
AVLNode *newRoot = node->left;
node->left = newRoot->right;
newRoot->right = node;
updateHeight(node);
updateHeight(newRoot);
return newRoot;
}
// 平衡二叉树插入操作
AVLNode *insert(AVLNode *root, int key) {
if (root == NULL) {
// 创建新节点并返回
AVLNode *newNode = (AVLNode *)malloc(sizeof(AVLNode));
newNode->key = key;
newNode->height = 1;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
if (key < root->key) {
// 插入到左子树
root->left = insert(root->left, key);
} else if (key > root->key) {
// 插入到右子树
root->right = insert(root->right, key);
} else {
// 已存在该节点,不需要插入
return root;
}
// 更新节点高度
updateHeight(root);
// 判断平衡因子,如果不平衡就进行旋转
int balanceFactor = getBalanceFactor(root);
if (balanceFactor > 1 && key < root->left->key) {
// LL型,进行右旋操作
return rightRotate(root);
} else if (balanceFactor < -1 && key > root->right->key) {
// RR型,进行左旋操作
return leftRotate(root);
} else if (balanceFactor > 1 && key > root->left->key) {
// LR型,先进行左旋再进行右旋
root->left = leftRotate(root->left);
return rightRotate(root);
} else if (balanceFactor < -1 && key < root->right->key) {
// RL型,先进行右旋再进行左旋
root->right = rightRotate(root->right);
return leftRotate(root);
}
return root;
}
// 中序遍历平衡二叉树
void inorderTraversal(AVLNode *root) {
if (root == NULL) {
return;
}
inorderTraversal(root->left);
printf("%d ", root->key);
inorderTraversal(root->right);
}
int main() {
AVLNode *root = NULL;
int arr[] = {10, 20, 30, 40, 50, 60, 70, 80, 90};
int i;
// 插入数据并构建平衡二叉树
for (i = 0; i < sizeof(arr) / sizeof(arr[0]); i++) {
root = insert(root, arr[i]);
}
// 中序遍历平衡二叉树
inorderTraversal(root);
return 0;
}
```
以上代码实现了平衡二叉树的插入操作和中序遍历操作,你可以根据需要进行修改和扩展。