1 package AVLTree2;
  2 
  3 public class Node {
  4     int val;
  5     Node left;
  6     Node right;
  7 
  8     public Node(int val) {
  9         this.val = val;
 10     }
 11 
 12     @Override
 13     public String toString() {
 14         return "Node{" +
 15                 "val=" + val +
 16                 ‘}‘;
 17     }
 18 
 19 
 20     //获取树的高度：即最大高度
 21     public int getDeepth(Node root){
 22         if(root==null){
 23             return 0;
 24         }
 25 
 26         int leftDeepth=getDeepth(root.left)+1;
 27         int rightDeepth=getDeepth(root.right)+1;
 28 
 29         return Math.max(leftDeepth,rightDeepth);
 30     }
 31 
 32 
 33     //左旋转:右子树高度-左子树高度>1,向左旋转
 34     public Node turnLeft(Node root){
 35         Node newRoot=root.right;
 36         root.right=newRoot.left;
 37         newRoot.left=root;
 38         return newRoot;
 39     }
 40 
 41 
 42     //右旋转：左子树高度-右子树高度>1,向右旋转
 43     public Node turnRight(Node root){
 44         Node newRoot=root.left;
 45         root.left=newRoot.right;
 46         newRoot.right=root;
 47 
 48         return newRoot;
 49     }
 50 
 51 
 52     //平衡
 53     public Node balance(Node root){
 54         if(root==null){
 55             return null;
 56         }
 57 
 58 
 59         //右子树高度-左子树高度>1
 60         if(getDeepth(root.right)-getDeepth(root.left)>1){
 61             if(getDeepth(root.right.right)>=getDeepth(root.right.left)){
 62                 //单旋转
 63                 root=turnLeft(root);
 64             }else{
 65                 //双旋转
 66                 root.right=turnRight(root.right);
 67                 root=turnLeft(root);
 68             }
 69         }
 70 
 71 
 72 
 73        //左子树高度-右子树高度>1
 74         if(getDeepth(root.left)-getDeepth(root.right)>1){
 75 
 76             //单旋转
 77             if(getDeepth(root.left.left)>=getDeepth(root.left.right)){
 78                 root=turnRight(root);
 79             }else{
 80                 //双旋转
 81                 root.left=turnLeft(root.left);
 82                 root=turnRight(root);
 83             }
 84         }
 85 
 86 
 87         return root;
 88     }
 89 
 90 
 91 
 92     //添加节点
 93     //添加结点
 94     /*
 95      root:根节点
 96      val:要新添加的新节点的值
 97      */
 98     public Node insertNode(Node root,int val){
 99 
100         //如果当前节点为null，则直接在当前节点处插入结点
101         if(root==null){
102             return new Node(val);
103         }
104 
105         int compare=val-root.val;
106 
107         //如果新插入节点的值>当前节点的值，则将新节点往当前节点的右子树上放
108         if(compare>0){
109             root.right=insertNode(root.right,val);
110         }else{
111             //如果新插入节点的值<当前节点的值，则将新节点往当前节点的左子树上放
112             root.left=insertNode(root.left,val);
113         }
114 
115         //平衡将以当前节点为父节点子树
116         return balance(root);
117 
118     }
119 
120 
121     //前序遍历
122     public void preOrder(Node root){
123         if(root==null){
124             return;
125         }
126 
127         System.out.println(root.val);
128 
129         preOrder(root.left);
130 
131         preOrder(root.right);
132     }
133 
134 
135 
136 }

 1 package AVLTree2;
 2 
 3 public class Tree {
 4 
 5     Node root;
 6 
 7     public void insertNode(int val){
 8 
 9         root=root.insertNode(root,val);
10     }
11 
12     public void preOrder(){
13 
14         root.preOrder(root);
15     }
16 }

 1 package AVLTree2;
 2 
 3 import AVLTree.AVLTree;
 4 
 5 public class Test {
 6 
 7     public static void main(String[] args){
 8         AVLTree tree=new AVLTree();
 9 
10         for(int i=1;i<=10;i++){
11             tree.insertNode(i);
12         }
13         tree.preOrder();
14     }
15 }