java 实现排序二叉树及其实例详解

public class Node {
int key;
Node left, right;
int height;

public Node(int item){
this.key = item;
left = null;
right = null;
height = 1; // 新建结点初始高度为1
}
}

class AVLTree {
private static final int ALLOWED_IMBALANCE = 1;

/* 获取当前节点的最大深度 */
private int getBalanceFactor(Node N){
if (N == null)
return 0;

return getHeight(N.left) - getHeight(N.right);
}

/* 计算给定节点的高度 */
private int getHeight(Node N) {
if (N==null)
return 0;

return N.height;
}

/* 插入新元素到AVL树中的函数*/
public void insert(Integer value){
root = insertRec(root,value);
}

/*递归插入方法*/
private Node insertRec(Node root,Integer val){
if(root == null){
root=new Node(val);
} else{
if( val.compareTo((Integer)(root.val)) < 0 )
root.left=insertRec(root.left,val);
else if( val > ((Integer)(root.val)))
root.right=insertRec(root.right,val);

// 更新height of the current ancestor node and rebalance it.
root.height = 1 + Math.max(getHeight(root.left),getHeight(root.right));

// Check whether this node became unbalanced after insertion or not
int balance = getBalanceFactor(root);

// If this node becomes unbalanced, then there are four cases to check for rotation:
// Left Left Case
if(balance > 1 && getBalanceFactor(root.left)>0)
root = rotateRight(root);

// Right Right Case
if(balance < -1 && getBalanceFactor(root.right)<0 )
root = rotateLeft(root);

// Left Right Case
if(balance > 1 && getBalanceFactor(root.left)<0 ){
root.left = rotateLeft(root.left);
root = rotateRight(root);
}

// Right Left Case
if(balance < -1 && getBalanceFactor(root.right)>0 ){
root.right = rotateRight(root.right);
root = rotateLeft(root);
}
}
return root;
}

// 定义左右旋转变换的方法
...
}

// 这里省略rotateLeft() 和 rotateRight() 方法的具体实现，
// 其功能是对失衡节点执行相应的向左或者向右旋转使得整棵树重新恢复平衡。

AVLTree tree = new AVLTree();
tree.insert(50);
tree.insert(30);
tree.insert(20);
tree.insert(40);
tree.insert(70);
tree.insert(60);
...