平衡二叉树的实现c语言
- 格式：doc
- 大小：36.88 KB
- 文档页数：5
平衡二叉树的实现c语言
平衡二叉树（AVL树）是一种自平衡的二叉查找树，其中任何节点的两个子树的高度差最多为1。下面是一个简单的AVL树的C语言实现：
```c
include <>
include <>
typedef struct AVLNode {
int key;
int height;
struct AVLNode left, right;
} AVLNode;
typedef struct {
AVLNode root;
} AVLTree;
int getHeight(AVLNode node) { if (node == NULL)
return 0;
return node->height;
}
int getBalance(AVLNode node) {
if (node == NULL)
return 0;
return getHeight(node->left) - getHeight(node->right);
}
AVLNode rotateRight(AVLNode y) {
AVLNode x = y->left;
AVLNode T2 = x->right;
x->right = y;
y->left = T2;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x; // new root is x
}
AVLNode rotateLeft(AVLNode x) {
AVLNode y = x->right;
AVLNode T2 = y->left;
y->left = x;
x->right = T2;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y; // new root is y
}
AVLNode insert(AVLTree tree, int key) {
AVLNode root = tree->root;
if (root == NULL) { // tree is empty, create a new node as root.
tree->root = (AVLNode)malloc(sizeof(AVLNode));
root = tree->root;
root->key = key;
root->height = 1;
return root;
} else if (key < root->key) { // insert into left subtree.
root->left = insert(root->left, key);
} else if (key > root->key) { // insert into right subtree. root->right = insert(root->right, key);
} else { // duplicate keys not allowed.
return root; // don't insert duplicate key.
}
root->height = 1 + max(getHeight(root->left), getHeight(root->right)); // adjust height of current node.
int balance = getBalance(root);
if (balance > 1 && key < root->left->key) { // left left case.
return rotateRight(root); // rotate right.
} else if (balance < -1 && key > root->right->key) { // right right
case.
return rotateLeft(root); // rotate left.
} else if (balance > 1 && key > root->left->key) { // left right case.
root->left = rotateLeft(root->left); // rotate left first.
return rotateRight(root); // then rotate right.
} else if (balance < -1 && key < root->right->key) { // right left
case.
root->right = rotateRight(root->right); // rotate right first.
return rotateLeft(root); // then rotate left.
} // keep balance.
return root; // already balanced. }
```
