java项目---用java实现二叉平衡树（AVL树）并打印结果（详）

              1
            package
             Demo;

              2
              3
            public
            class
             AVLtree  {

              4
            private Node root;                      //首先定义根节点  5  6privatestaticclass Node{                              //定义Node指针参数  7privateint key;                //节点  8privateint balance;                    //平衡值  9privateint height;             //树的高度 10private Node left;                      //左节点 11private Node right;             //右节点 12private Node parent;                    //父母节点 13 14 15     Node(int key, Node parent){             //构造器中引用该构造器正在初始化的对象 16this.key = key;
 17this.parent = parent;
 18 19        }
 20    }
 21publicboolean insert(int key){             //判断这里是否能插入新的节点 22if(root == null){
 23             root = new Node(key,null);
 24returntrue;
 25        }
 26 27         Node n = root;
 28while (true){                           //如果根节点下的子节点和新插进来的子节点相同 29if(n.key == key)
 30returnfalse;                   //则不进行插入操作 31 32             Node parent = n;
 33 34boolean goLeft = n.key > key;           //判断新的节点插入父母节点的左边or右边 35             n = goLeft ? n.left : n.right;             //小的话插左边，大的话插右边 36 37if(n == null){
 38if(goLeft){
 39                     parent.left = new Node (key,parent);
 40                 }else{
 41                     parent.right = new Node(key,parent);
 42                }
 43                rebalance(parent);
 44break;
 45            }
 46        }
 47returntrue;
 48    }
 49 50privatevoid delete(Node node){                     //删除节点 51if(node.left == null && node.right == null){
 52if(node.parent == null){
 53                 root = null;
 54             }else{
 55                 Node parent = node.parent;
 56if(parent.left == node){            //如果父母节点的左孩子节点和根节点一样 57                     parent.left = null;             //则左节点为空 58                 }else{
 59                     parent.right = null;            //反之右节点为空 60                }
 61                rebalance(parent);
 62            }
 63return ;
 64        }
 65 66if(node.left != null){              //如果左节点不空 67             Node child = node.left;
 68while(child.right != null)child = child.right;
 69             node.key = child.key;
 70            delete(child);
 71         }else{
 72             Node child = node.right;
 73while (child.left != null)child = child.left;
 74             node.key = child.key;
 75            delete(child);
 76            }
 77        }
 78 79publicvoid Delete(int delKey){
 80if(root == null)
 81return;
 82 83         Node child = root;
 84while (child != null){
 85             Node node = child;                           //交换根节点给node , 再判断新的孩子节点插在哪里 86             child = delKey >= node.key ? node.right : node.left;
 87if(delKey == node.key){
 88                delete(node);
 89return;
 90            }
 91        }
 92    }
 93 94privatevoid setBalance(Node... nodes){
 95for(Node n : nodes){
 96            reheight(n);
 97             n.balance = height(n.right) - height(n.left);           //平衡因子，任意节点左右子树高度差 98        }
 99    }
100101privatevoid rebalance (Node n){
102        setBalance(n);
103104if(n.balance == -2){
105if(height(n.left.left) >= height(n.left.right))
106                 n = rotateRight(n);
107else108                 n = rotateLeftThenRight(n) ;
109110         }elseif(n.balance == 2){                                   //等于2和-2都是不平衡的，需要重新调整111if(height(n.right.right) >= height(n.right.left))
112                 n = rotateLeft(n);
113else114                 n = rotateRightThenLeft(n);
115116        }
117118if(n.parent != null){
119            rebalance(n.parent);
120         }else{
121             root = n;
122        }
123    }
124125private Node rotateLeft(Node a){
126127         Node b = a.right;
128         b.parent = a.parent;
129130         a.right = b.left;
131132if(a.right != null)
133             a.right.parent = a;
134135         b.left = a;
136         a.parent = b;
137138if(b.parent != null){
139if(b.parent.right == a){
140                 b.parent.right = b;
141             }else{
142                 b.parent.left = b;
143            }
144        }
145146        setBalance(a, b);
147148return b;
149    }
150151private Node rotateRight(Node a){
152153         Node b = a.left;
154         b.parent = a.parent;
155156         a.left = b.right;
157158if(a.left != null){
159             a.left.parent = a;
160161             b.right = a;
162             a.parent = b;
163164if(b.parent.right == a){
165                 b.parent.right = b;
166             }else{
167                 b.parent.left = b;
168            }
169        }
170171        setBalance(a, b);
172173return b;
174    }
175176private Node rotateLeftThenRight(Node n){
177         n.left = rotateLeft(n.left);
178return rotateRight(n);
179    }
180181private Node rotateRightThenLeft(Node n){
182         n.right = rotateRight(n.right);
183return rotateLeft(n);
184    }
185186privateint height (Node n){
187if(n == null)
188return -1;
189return n.height;
190    }
191192193194publicvoid printBalance(){
195        printBalance(root);
196    }
197198privatevoid printBalance(Node n){
199if(n != null){
200            printBalance(n.left);
201             System.out.printf("%s ",n.balance);
202            printBalance(n.right);
203        }
204    }
205206privatevoid reheight(Node node){
207if(node != null){
208             node.height = 1 + Math.max(height(node.left),height(node.right));           //新的二叉平衡树高度为：209        }
210    }
211publicstaticvoid main(String[] args) {
212         AVLtree tree = new AVLtree();
213214         System.out.println("Inserting values 1 to 10");     //最后输出的结果代表平衡因子，0为左右子树高度相等，1为左右子树高度相差1层215for (int i = 1; i < 10; i++)
216            tree.insert(i);
217218         System.out.println("Print balance : ");
219        tree.printBalance();
220    }
221 }