一、定义AVL树类
public class AVLTree> { private AVLNode mRoot; //结点 //AVL树的结点(内部类) class AVLNode >{ T key; //结点的值 int height; //高度 AVLNode left; //左孩子 AVLNode right; //右孩子 public AVLNode(T key, AVLNode left, AVLNode right) { this.key = key; this.left = left; this.right = right; this.height = 0; } } //构造函数 public AVLTree() { mRoot = null; } //获取树的高度 private int height(AVLNode tree){ if (tree != null){ return tree.height; } return 0; } public int getHeight(){ return height(mRoot); } //找两个树的最大值 private int max(int a,int b){ return a>b ? a : b; } //前序遍历 private void preOrder(AVLNode tree){ if (tree != null){ System.out.print("["+tree.key+"] "); preOrder(tree.left); preOrder(tree.right); } } public void proOrder(){ preOrder(mRoot); } //中序遍历 private void inOrder(AVLNode tree){ if (tree != null){ inOrder(tree.left); System.out.print("["+tree.key+"] "); inOrder(tree.right); } } public void inOrder(){ inOrder(mRoot); } //后序遍历 private void postOrder(AVLNode tree){ if (tree != null){ postOrder(tree.left); postOrder(tree.right); System.out.print("["+tree.key+"] "); } } public void postOrder(){ postOrder(mRoot); } private AVLNode search(AVLNode x,T key){ if (x == null){ return x; } int cmp = key.compareTo(x.key); //比较 if (cmp < 0){ //如果key比x的key小,在x的左子树中找 return search(x.left,key); }else if (cmp > 0){//如果key比x的key大,在x的右子树中找 return search(x.right,key); }else{ return x; } } public AVLNode search(T key){ return search(mRoot,key); } private AVLNode iterativeSearch(AVLNode x, T key){ while ( x != null){ int cmp = key.compareTo(x.key); if (cmp < 0){ x = x.left; }else if (cmp > 0){ x = x.right; }else{ return x; } } return x; } public AVLNode iterativeSearch(T key){ return iterativeSearch(mRoot,key); } private AVLNode minNum(AVLNode tree){ if (tree == null){ return null; } while (tree.left != null){ //在tree的左子树中查找 tree = tree.left; } return tree; } public T minNum(){ AVLNode p = minNum(mRoot); if (p != null){ return p.key; } return null; } private AVLNode maxNum(AVLNode tree){ if (tree == null){ return null; } while (tree.right != null){ //在tree的右子树中查找 tree = tree.right; } return tree; } public T maxNum(){ AVLNode p = maxNum(mRoot); if (p != null){ return p.key; } return null; } private AVLNode leftLeftRotate(AVLNode k2){ AVLNode k1; k1 = k2.left; k2.left = k1.right; k1.right = k2; k2.height = max(height(k2.left),height(k2.right)) + 1; k1.height = max(height(k1.left),k2.height) + 1; return k1; } private AVLNode rightRightRotate(AVLNode k1){ AVLNode k2; k2 = k1.right; k1.right = k2.left; k2.left = k1; k1.height = max(height(k1.left),height(k1.right)) + 1; k2.height = max(height(k2.right),k1.height) + 1; return k2; } private AVLNode leftRightRotate(AVLNode k3){ k3.left = rightRightRotate(k3.left); return leftLeftRotate(k3); } private AVLNode rightLeftRotate(AVLNode k1){ k1.right = leftLeftRotate(k1.right); return rightRightRotate(k1); } private AVLNode insert(AVLNode tree,T key){ if (tree == null){ //如果树为空,新建结点 tree = new AVLNode (key,null,null); if (tree == null){ System.out.println("Error:create avltree node failed!"); return null; } }else { int cmp = key.compareTo(tree.key); if (cmp < 0){ //若key小于根结点,则插入到左子树 tree.left = insert(tree.left,key); //插入结点后,若AVL树失去平衡,则进行相应的调节 if (height(tree.left) - height(tree.right) == 2){ if (key.compareTo(tree.left.key) < 0){ tree = leftLeftRotate(tree); }else { tree = leftRightRotate(tree); } } }else if (cmp > 0){ //若key大于根结点,则插入到右子树 tree.right = insert(tree.right,key); //插入结点后,若AVL树失去平衡,则进行相应的调节 if (height(tree.right) - height(tree.left) == 2){ if (key.compareTo(tree.right.key) > 0){ tree = rightRightRotate(tree); }else{ tree = rightLeftRotate(tree); } } }else{ //cmp ==0 System.out.println("添加失败:不允许添加相同的结点!"); } } tree.height = max(height(tree.left),height(tree.right)) + 1; return tree; } public void insert(T key){ mRoot = insert(mRoot,key); } private AVLNode remove(AVLNode tree,AVLNode z){ //根为空 或者 没有要删除的结点,直接返回null if (tree == null || z == null){ return null; } int cmp = z.key.compareTo(tree.key); if (cmp < 0){ //待删除结点在tree的左子树中 tree.left = remove(tree.left,z); //删除结点后,若AVL树失去平衡,则进行相应的调节 if (height(tree.right) - height(tree.left) == 2){ AVLNode r = tree.right; if (height(r.left) > height(r.right)){ tree = rightLeftRotate(tree); }else{ tree = rightRightRotate(tree); } } }else if (cmp > 0){ //待删除结点在tree的右子树中 tree.right = remove(tree.right,z); //删除结点后,若AVL树失去平衡,则进行相应的调节 if (height(tree.left) - height(tree.right) == 2){ AVLNode l = tree.left; if (height(l.right) > height(l.left)){ tree = leftRightRotate(tree); }else{ tree = leftLeftRotate(tree); } } }else{ //tree是对应要删除的结点 if ((tree.left != null) &&(tree.right != null)){ //tree的左右孩子都非空 if (height(tree.left) > height(tree.right)){ AVLNode max = minNum(tree.left); tree.key = max.key; tree.left = remove(tree.left,max); }else{ AVLNode min = minNum(tree.right); tree.key = min.key; tree.right = remove(tree.right,min); } }else{ AVLNode tmp = tree; tree = (tree.left != null)?tree.left : tree.right; tmp = null; } } return tree; } public void remove(T key){ AVLNode z = search(mRoot,key); if (z != null){ mRoot = remove(mRoot,z); } } private void destroy(AVLNode tree){ if (tree == null){ return; } if (tree.left != null){ destroy(tree.left); } if (tree.right != null){ destroy(tree.right); } tree = null; } public void destroy(){ destroy(mRoot); } private void print(AVLNode tree,T key,int direction){ if (tree != null){ if (direction ==0){ //tree是根结点 System.out.printf("%2d is rootn",tree.key,key); }else{ //tree的分支结点 System.out.printf("%2d is %2d's %6s childn",tree.key,key,direction==1?"right":"left"); } print(tree.left,tree.key,-1); print(tree.right,tree.key,1); } } public void print(){ if (mRoot != null){ print(mRoot,mRoot.key,0); } } }
二、测试
public class AVLTreeTest {
private static int arr[]= {33,32,1,4,5,6,17,16,15,14,13,12,11,10,8,9};
public static void main(String[] args) {
int i;
AVLTree tree = new AVLTree<>();
System.out.printf("== 依次添加:");
for ( i = 0; i < arr.length ; i++) {
System.out.printf("%d ",arr[i]);
tree.insert(arr[i]);
}
System.out.printf("n== 前序遍历:");
tree.proOrder();
System.out.printf("n== 中序遍历:");
tree.inOrder();
System.out.printf("n== 后序遍历:");
tree.postOrder();
System.out.println();
System.out.printf("== 高度:%dn",tree.getHeight());
System.out.printf("== 最小值:%dn",tree.minNum());
System.out.printf("== 最大值:%dn",tree.maxNum());
System.out.println("== 树的详细信息:");
tree.print();
i = 8;
System.out.printf("n== 删除结点:%d",i);
tree.remove(i);
System.out.printf("n== 高度:%d",tree.getHeight());
System.out.printf("n== 中序遍历:");
tree.inOrder();
System.out.printf("n== 树的详细信息:n");
tree.print();
tree.destroy();//销毁二叉树
}
}



