平衡二叉树java代码
时间: 2023-10-12 17:18:59 浏览: 49
当然,我可以为您提供一个简单的平衡二叉树的Java代码:
```
public class AVLTree {
public Node root;
public AVLTree() {
root = null;
}
public void insert(int key) {
root = insert(root, key);
}
private int height(Node node) {
if (node == null)
return 0;
return node.height;
}
private int max(int a, int b) {
return (a > b) ? a : b;
}
private Node insert(Node node, int key) {
if (node == null)
return new Node(key);
if (key < node.key)
node.left = insert(node.left, key);
else if (key > node.key)
node.right = insert(node.right, key);
else
return node;
node.height = 1 + max(height(node.left),
height(node.right));
int balance = getBalance(node);
if (balance > 1 && key < node.left.key)
return rightRotate(node);
if (balance < -1 && key > node.right.key)
return leftRotate(node);
if (balance > 1 && key > node.left.key) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && key < node.right.key) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
private int getBalance(Node node) {
if (node == null)
return 0;
return height(node.left) - height(node.right);
}
private 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;
}
private 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;
}
private void preOrder(Node node) {
if (node != null) {
System.out.print(node.key + " ");
preOrder(node.left);
preOrder(node.right);
}
}
public void printPreorder() {
preOrder(root);
}
private class Node {
int key, height;
Node left, right;
Node(int d) {
key = d;
height = 1;
}
}
}
```
这是一个基本的AVL树实现,其中包括插入,旋转和打印(通过先序遍历)。