编写一个JAVA算法,将整数序列(4,5,7,2,1,3,6)中的整数依次插入到一棵空的平衡二叉树中,试构造相应的平衡二叉树。
时间: 2024-06-13 12:08:40 浏览: 179
首先,我们需要了解平衡二叉树(AVL树)的基本概念。平衡二叉树是一种特殊的二叉搜索树,它的每个节点的左子树和右子树的高度差不超过1。为了实现这个特性,我们需要在插入节点时进行旋转操作。
下面是一个简单的Java算法,用于将整数序列插入到一棵空的平衡二叉树中:
1. 定义一个平衡二叉树节点类`AVLNode`,包含整数值、高度、左右子节点等属性。
2. 定义一个`AVLTree`类,包含插入、旋转等方法。
3. 使用给定的整数序列构建平衡二叉树。
```java
class AVLNode {
int value;
int height;
AVLNode left;
AVLNode right;
public AVLNode(int value) {
this.value = value;
this.height = 1;
}
}
class AVLTree {
private AVLNode root;
public void insert(int value) {
root = insert(root, value);
}
private AVLNode insert(AVLNode node, int value) {
if (node == null) {
return new AVLNode(value);
}
if (value < node.value) {
node.left = insert(node.left, value);
} else if (value > node.value) {
node.right = insert(node.right, value);
} else {
return node;
}
node.height = 1 + Math.max(height(node.left), height(node.right));
int balance = getBalance(node);
if (balance > 1 && value < node.left.value) {
return rightRotate(node);
}
if (balance < -1 && value > node.right.value) {
return leftRotate(node);
}
if (balance > 1 && value > node.left.value) {
node.left = leftRotate(node.left);
return rightRotate(node);
}
if (balance < -1 && value < node.right.value) {
node.right = rightRotate(node.right);
return leftRotate(node);
}
return node;
}
private int height(AVLNode node) {
return node == null ? 0 : node.height;
}
private int getBalance(AVLNode node) {
return node == null ? 0 : height(node.left) - height(node.right);
}
private AVLNode rightRotate(AVLNode y) {
AVLNode x = y.left;
AVLNode T2 = x.right;
x.right = y;
y.left = T2;
y.height = Math.max(height(y.left), height(y.right)) + 1;
x.height = Math.max(height(x.left), height(x.right)) + 1;
return x;
}
private AVLNode leftRotate(AVLNode x) {
AVLNode y = x.right;
AVLNode T2 = y.left;
y.left = x;
x.right = T2;
x.height = Math.max(height(x.left), height(x.right)) + 1;
y.height = Math.max(height(y.left), height(y.right)) + 1;
return y;
}
}
public class Main {
public static void main(String[] args) {
AVLTree tree = new AVLTree();
tree.insert(4);
tree.insert(5);
tree.insert(7);
tree.insert(2);
tree.insert(1);
tree.insert(3);
tree.insert(6);
}
}
```
这个算法首先创建一个空的平衡二叉树,然后按照给定的整数序列依次插入节点。在插入过程中,会根据节点的左子树和右子树的高度差来判断是否需要进行旋转
阅读全文