，这是我的分配。
写一个使用AVL树来存储通用值和键的Java类。
方法
- 构造函数
- 列表项目
- 插入
- 删除
- 找到键的值
- inorder-返回带有顺序的值的数组
- POSTORDER-返回具有后顺序序列值的数组
- 预订 - 返回带有预订序列值的数组
- 使用包含密钥和值的内部节点类。
- 使用ArrayList作为从遍历返回的数组。
我认为我有基本的想法，但是我的树不能正确地平衡。此外，在我实现ArrayList之前，Inorder，Predore，Pordored，postored正在工作中，试图确保其对其进行正确的排序。
任何帮助或解决方案都是巨大的。这是我到目前为止所拥有的。
public class AVLTree {
Node root;
public class Node{ //subclass of Node in AVL tree
private Node left;
private Node right;
int height = 1;
int key;
public Node(int n)
{
this.key = n;
height = 1;
}
}
public int height(Node n){
if(n == null)
return 0;
return n.height;
}
public void in(int key)
{
root = insert(root, key);
}
public Node insert(Node node, int key) //insert
{
if(node == null)
{
node = new Node(key);
}
else if(key < node.key)
{
node.left = insert(node.left, key);
if(height(node.left)- height(node.right) == 2) {
if(key < node.left.key)
{
node = rotateLeft(node);
}
else {
node.left = rotateRight(node.left);
rotateLeft(node);
}
}
}
else if(key > node.key)
{
node.right = insert(node.right, key);
if(height(node.right)- height(node.left) == 2) {
if(key < node.right.key)
{
node = rotateRight(node);
}
else {
node.right = rotateLeft(node.right);
rotateRight(node);
}
}
}
else {
node.height = Math.max(height(node.left), height(node.right)) + 1; //increase height of the node
}
return node;
}
public Node delete(Node root, int key) {
if(root == null)
return root;
Node temp;
if (key < root.key) {
root.left = delete(root.left, key);
}
else if(key > root.key) {
root.right = delete(root.right,key);
}
else if(key == root.key){
if(root.left == null || root.right == null){ //root has one child
if(root.left != null)
temp = root.left;
else
temp = root.right;
if( temp == null) { // no child
temp = root;
root = null;
}
else
root = temp;
temp = null;
}
else {
temp = minNode(root.right);
root.key = temp.key;
root.right = delete(root.right, temp.key);
}
}
if(root == null)
return root;
root.height = Math.max(height(root.left), height(root.right)) + 1;
//once deleted we must rebalance it
int balance = height(root.left) - height(root.right); //check balance of top node
if(balance > 1 && key < root.left.key) //left left rotation
return rotateRight(root);
else if(balance < -1 && key > root.right.key) //right right
return rotateLeft(root);
else if(balance > 1 && key > root.left.key) //left righ
return rotateRight(root);
else if(balance > -1 && key < root.right.key) //right left
return rotateRight(root);
return root;
}
private Node rotateLeft(Node y) {
Node x = y.left;
y.left = x.right;
x.right = y; //rotates
x.height = Math.max(height(x.left), height(x.right))+1;
y.height = Math.max(height(y.left), height(y.right))+1;
return x;
}
private Node rotateRight(Node x)
{
Node y = x.right;
x.right = y.left;
y.left = x; //rotates
x.height = Math.max(height(x.left), height(x.right))+1;
y.height = Math.max(height(y.left), height(y.right))+1;
return y;
}
void TpreOrder(Node node)
{
if (node != null)
{
System.out.print(node.key + " ");
TpreOrder(node.left);
TpreOrder(node.right);
}
}
void TpostOrder(Node node)
{
if (node != null)
{
TpreOrder(node.left);
TpreOrder(node.right);
System.out.print(node.key + " ");
}
}
public void TinOrder(Node root)
{
if(root != null) {
TinOrder(root.left);
System.out.print(root.key+" ");
TinOrder(root.right);
}
}
public void inOrder(Node root, ArrayList<Integer> pre)
{
if(root != null) {
inOrder(root.left, pre);
pre.add(root.key);
pre.add(root.key);
inOrder(root.right, pre);
}
}
public ArrayList<Integer> toArray() {
ArrayList<Integer> result = new ArrayList<Integer>();
inOrder(root, result);
return result;
}
public void preOrder(Node root, ArrayList<Integer> in)
{
if(root != null) {
preOrder(root.left, in);
in.add(root.key);
preOrder(root.right, in);
}
}
public void postOrder(Node root, ArrayList<Integer> post)
{
if(root != null) {
postOrder(root.right, post);
post.add(root.key);
postOrder(root.left, post);
}
}
private Node minNode(Node node) {
Node cur = node;
while(cur.left != null)
cur = cur.left;
return cur;
}
}
也许这会帮助您：
重新计算树的高度：
public void computeHeight() {
height = 1;
if (left != null) {
height += left.height;
}
if (right != null) {
height += right.height;
}
}
返回平衡因子：
private int getBalance(){
int balance = 0;
if (left != null) {
balance += left.height;
}
if (right != null) {
balance -= right.height;
}
return balance;
}
平衡节点：
private Node balance() {
computeHeight();
int balance = getBalance();
if (balance > 1) {
if (left.getBalance() < 0) {
left = left.rotateLeft();
}
return rotateRight();
}else if (balance < -1) {
if (right.getBalance() > 0) {
right = right.rotateRight();
}
return rotateLeft();
}
return this;
}