平衡二叉树c语言实现
时间: 2023-11-01 08:58:55 浏览: 42
平衡二叉树是一种特殊的二叉树,它的左子树和右子树的高度差不超过1。它的设计是为了解决有序二叉树在某些情况下性能下降的问题。在平衡二叉树中,任意节点的左子树和右子树都是平衡二叉树。通过保持树的平衡性,平衡二叉树可以提供较快的插入、删除和搜索操作。
在C语言中,我们可以使用以下方式实现平衡二叉树:
1. 定义一个结构体表示二叉树的节点,节点包含值、左子节点和右子节点的指针。
2. 实现插入函数,每次插入新节点时,判断树的平衡性并进行相应的旋转操作,使树保持平衡。
3. 实现删除节点的函数,同样需要考虑树的平衡性,并进行适当的旋转操作。
4. 实现搜索函数,按照二叉搜索树的规则在树中查找指定的值。
相关问题
平衡二叉树c语言实现代码
以下是一个简单的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 *n) {
if (n == NULL) {
return 0;
}
return n->height;
}
int max(int a, int b) {
return (a > b) ? a : b;
}
node *new_node(int data) {
node *n = (node *)malloc(sizeof(node));
n->data = data;
n->left = NULL;
n->right = NULL;
n->height = 1;
return n;
}
node *right_rotate(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 *left_rotate(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 get_balance(node *n) {
if (n == NULL) {
return 0;
}
return height(n->left) - height(n->right);
}
node *insert(node *n, int data) {
if (n == NULL) {
return new_node(data);
}
if (data < n->data) {
n->left = insert(n->left, data);
} else if (data > n->data) {
n->right = insert(n->right, data);
} else {
return n;
}
n->height = 1 + max(height(n->left), height(n->right));
int balance = get_balance(n);
if (balance > 1 && data < n->left->data) {
return right_rotate(n);
}
if (balance < -1 && data > n->right->data) {
return left_rotate(n);
}
if (balance > 1 && data > n->left->data) {
n->left = left_rotate(n->left);
return right_rotate(n);
}
if (balance < -1 && data < n->right->data) {
n->right = right_rotate(n->right);
return left_rotate(n);
}
return n;
}
void pre_order(node *n) {
if (n != NULL) {
printf("%d ", n->data);
pre_order(n->left);
pre_order(n->right);
}
}
int main() {
node *root = NULL;
root = insert(root, 10);
root = insert(root, 20);
root = insert(root, 30);
root = insert(root, 40);
root = insert(root, 50);
root = insert(root, 25);
printf("Preorder traversal of the constructed AVL tree is: \n");
pre_order(root);
return 0;
}
```
实现平衡二叉树C语言
以下是C语言实现平衡二叉树的代码示例:
```c
#include <stdio.h>
#include <stdlib.h>
// 定义平衡二叉树结点
typedef struct AVLNode {
int data; // 数据
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) {
if (node == NULL) {
return; }
int leftHeight = getHeight(node->left);
int rightHeight = getHeight(node->right);
node->height = (leftHeight > rightHeight ? leftHeight : rightHeight) + 1;
}
// LL旋转
AVLNode *LLRotate(AVLNode *node) {
AVLNode *leftChild = node->left;
node->left = leftChild->right;
leftChild->right = node;
updateHeight(node);
updateHeight(leftChild);
return leftChild;
}
// RR旋转
AVLNode *RRRotate(AVLNode *node) {
AVLNode *rightChild = node->right;
node->right = rightChild->left;
rightChild->left = node;
updateHeight(node);
updateHeight(rightChild);
return rightChild;
}
// LR旋转
AVLNode *LRRotate(AVLNode *node) {
node->left = RRRotate(node->left);
return LLRotate(node);
}
// RL旋转
AVLNode *RLRotate(AVLNode *node) {
node->right = LLRotate(node->right);
return RRRotate(node);
}
// 插入结点
AVLNode *insertNode(AVLNode *node, int data) {
if (node == NULL) {
AVLNode *newNode = (AVLNode *)malloc(sizeof(AVLNode));
newNode->data = data;
newNode->height = 1;
newNode->left = NULL;
newNode->right = NULL;
return newNode;
}
if (data < node->data) {
node->left = insertNode(node->left, data);
updateHeight(node);
if (getBalanceFactor(node) == 2) {
if (getBalanceFactor(node->left) == 1) {
node = LLRotate(node);
} else {
node = LRRotate(node);
}
}
} else {
node->right = insertNode(node->right, data);
updateHeight(node);
if (getBalanceFactor(node) == -2) {
if (getBalanceFactor(node->right) == -1) {
node = RRRotate(node);
} else {
node = RLRotate(node);
}
}
}
return node;
}
// 中序遍历
void inorderTraversal(AVLNode *node) {
if (node == NULL) {
return;
}
inorderTraversal(node->left);
printf("%d ", node->data);
inorderTraversal(node->right);
}
// 主函数
int main() {
AVLNode *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;
}
```