平衡二叉树的构树过程

  1 package testStudy;
  2 /**平衡因子枚举类*/
  3 enum BalanceFactor{
  4     LH("左子树高"),EH("左右等高"),RH("右子树高");
  5     
  6     private String illustration="";
  7     
  8     private BalanceFactor(String s){
  9         this.illustration=s;
 10     }
 11     
 12     public String toString(){
 13         return this.illustration;
 14     }
 15 }
 16 /**
 17  * 平衡二叉树结点
 18  */
 19 class AVLNode<E extends Comparable<E>>{
 20     /**结点关键字*/
 21     E key=null;
 22     /**结点的平衡因子*/
 23     BalanceFactor bFactor=BalanceFactor.EH;
 24     /**结点的直接父亲*/
 25     AVLNode<E> parent=null;
 26     /**结点的左右孩子*/
 27     AVLNode<E> lchild,rchild=null;
 28     
 29     AVLNode(E k){
 30         this.key=k;
 31     }
 32     /**
 33      * 格式输出结点
 34      */
 35     public String toString(){
 36         //String fomateStr="";
 37         //if(this.lchild==null)
 38         String lchildStr=(this.lchild==null)?"null":this.lchild.key.toString();
 39         String rchildStr=(this.rchild==null)?"null":this.rchild.key.toString();
 40         return this.key+"[lchild="+lchildStr+"，rchild="+rchildStr+"]";
 41     }
 42 
 43 }
 44 /**
 45  * 平衡二叉查找树
 46  */
 47 public class AVL<E extends Comparable<E>> {
 48 
 49     /**树根*/
 50     private AVLNode<E> root=null;
 51     /**当前树是否变高*/
 52     public boolean isTaller=false;
 53     
 54     public AVL(){
 55     }
 56     
 57     
 58     public boolean insert(E key){
 59         System.out.print("插入["+key+"]：");
 60         if(key==null) return false;
 61         if(root==null){
 62             System.out.println("插入到树根。");
 63             root=new AVLNode<E>(key);
 64             return true;
 65         }
 66         else{
 67             System.out.print("搜索路径[");
 68             return insertAVL(key,root);
 69         }
 70     }
 71     
 72     private boolean insertAVL(E key,AVLNode<E> node){
 73         System.out.print(node.key+" —>");
 74         // 树中存在相同的key,不需要插入
 75         if(node.key.compareTo(key)==0){
 76             System.out.println("].  搜索有相同关键字，插入失败");
 77             isTaller=false;
 78             return false;
 79         }
 80         else{
 81             //左子树搜索
 82             if(node.key.compareTo(key)>0){
 83                 //当前node的左孩子为空,则插入到结点的做孩子并修改结点的平衡因子为LH
 84                 if(node.lchild==null){
 85                     System.out.println("].  插入到"+node.key+"的左孩子");
 86                     AVLNode<E> newNode=new AVLNode<E>(key);
 87                     node.lchild=newNode; //设置左孩子结点
 88                     newNode.parent=node; //设置父亲结点
 89                     isTaller=true; //树长高了
 90                 }
 91                 //左孩子不为空，则继续搜索下去
 92                 else{
 93                     insertAVL(key,node.lchild);
 94                 }
 95                 //当前如果树长高了，说明是因为左孩子的添加改变了平衡因子（左高）。
 96                 if(isTaller){
 97                     System.out.print("          树变化了，"+node.key+"的平衡因子变化");
 98                     switch(node.bFactor){
 99                         //原来结点平衡因子是LH(bf=1)，则左高以后bf=2，因此需要做左平衡旋转
100                         case LH: {
101                             System.out.println("[LH=1 ——> LH=2]. 出现了不平衡现象[左比右高2]");
102                             System.out.println("          ★ 以"+node.key+"为根将树进行左平衡处理");
103                             leftBalance(node);
104                             isTaller=false; 
105                             break;
106                         }
107                         //原来结点平衡因子是EH(bf=0),则左高了以后bf=1,不需要平衡处理。
108                         case EH:{
109                             System.out.println("[EH=0 ——> LH=1]. 没有不平衡现象");
110                             node.bFactor=BalanceFactor.LH;
111                             isTaller=true;
112                             break;
113                         }
114                         //原来结点平衡因子是RH(bf=-1)，则左高以后bf=0,不需要平衡处理。
115                         case RH:{
116                             System.out.println("[RH=-1 ——> EH=0]. 没有不平衡现象");
117                             node.bFactor=BalanceFactor.EH;
118                             isTaller=false;
119                             break;
120                         }
121                     }//end switch
122                 }//end if
123             }//end if
124             //右子树搜索
125             else{
126                 if(node.rchild==null){
127                     System.out.println("].  插入到"+node.key+"的右孩子");
128                     AVLNode<E> newNode=new AVLNode<E>(key);
129                     node.rchild=newNode; //设置右孩子结点
130                     newNode.parent=node; //设置父亲结点
131                     isTaller=true; //树长高了
132                 }
133                 else{
134                     insertAVL(key,node.rchild);
135                 }
136                 //当前如果树长高了，说明是因为右孩子的添加改变了平衡因子（右高）。
137                 if(isTaller){
138                     System.out.print("          树变化了，"+node.key+"的平衡因子变化");
139                     switch(node.bFactor){
140                         //原来结点平衡因子是LH(bf=1)，则右高以后bf=0，不需要平衡处理。
141                         case LH: {
142                             System.out.println("[LH=1 ——> EH=0]. 没有不平衡现象");
143                             node.bFactor=BalanceFactor.EH;
144                             isTaller=false;
145                             break;
146                         }
147                         //原来结点平衡因子是EH(bf=0),则右高了以后bf=-1,不需要平衡处理。
148                         case EH:{
149                             System.out.println("[EH=0 ——> RH=-1]. 没有不平衡现象");
150                             node.bFactor=BalanceFactor.RH;
151                             isTaller=true;
152                             break;
153                         }
154                         //原来结点平衡因子是RH(bf=-1)，则右高以后bf=0,因此需要做右平衡旋转。
155                         case RH:{
156                             System.out.println("[RH=-1 ——> RH=-2]. 出现了不平衡现象[左比右矮2]");
157                             rightBalance(node);
158                             isTaller=false; 
159                             break;
160                         }
161                     }//end switch
162                 }//end if(isTaller)
163             }//end else
164             return true;
165         }//end else
166     }
167     /**
168      * 左平衡旋转处理
169      * 先对node的左子树进行单左旋处理，在对node树进行单右旋处理
170      * 
171      *     100                100                90
172      *    /   \       左旋    /  \      右旋     /   173      *   80  120   ------>  90  120  ------>   80  100  
174      *   / \                /                 /  \   175      *  60 90              80                60  85  120
176      *      /             /   177      *     85             60  85
178      * 
179      * @param node 需要做处理的子树的根结点
180      */
181     private void leftBalance(AVLNode<E> node){
182         // node.parent指向新的孩子结点
183         AVLNode<E> lc=node.lchild;//lc指向node的左孩子结点
184         switch(lc.bFactor){
185             case LH:{  //新结点插入在node的左孩子的左子树上，则需要单右旋处理
186                 System.out.println("           ┖ 对"+node.key+"进行单右旋转处理");
187                 node.bFactor=lc.bFactor=BalanceFactor.EH;
188                 rRotate(node);
189                 break;
190             }
191             case RH:{  //新结点插入在node的左孩子的右子树上，需要双旋处理
192                 System.out.println("            ┖ 对"+node.key+"的左子树进行单左旋转处理，再对其本身树进行单右循环处理");
193                 AVLNode<E> rd=lc.rchild; //rd指向node左孩子的右子树根
194                 switch(rd.bFactor){ //修改node与其左孩子的平衡因子
195                     case LH:{
196                         node.bFactor=BalanceFactor.RH;
197                         lc.bFactor=BalanceFactor.EH;
198                         break;
199                     }
200                     case EH:{
201                         node.bFactor=lc.bFactor=BalanceFactor.EH;
202                         break;
203                     }
204                     case RH:{
205                         node.bFactor=BalanceFactor.EH;
206                         lc.bFactor=BalanceFactor.LH;
207                         break;
208                     }
209                 }//switch
210                 rd.bFactor=BalanceFactor.EH;
211                 lRotate(node.lchild);
212                 rRotate(node);
213                 break;
214             }
215         }
216         
217     }
218     /**
219      * 右平衡旋转处理
220      * 
221      *        80               80                     85  
222          *   /  \        右 旋 /  \       左 旋        /  \     
223          *  60  100    ------>60  85   ------->     80    100
224          *      /  \                \              /      /  \       
225          *     85  120               100        60       90  120
226          *      \                              /  227          *      90                            90  120 
228      * 
229      * @param node
230      */
231     private void rightBalance(AVLNode<E> node){
232         AVLNode<E> lc=node.rchild;//lc指向node的右孩子结点
233         switch(lc.bFactor){
234             case RH:{  //新结点插入在node的右孩子的右子树上，则需要单左旋处理
235                 node.bFactor=lc.bFactor=BalanceFactor.EH;
236                 lRotate(node);
237                 break;
238             }
239             case LH:{  //新结点插入在node的右孩子的左子树上，需要双旋处理
240                 AVLNode<E> rd=lc.lchild; //rd指向node右孩子的左子树根
241                 switch(rd.bFactor){ //修改node与其右孩子的平衡因子
242                     case LH:{
243                         node.bFactor=BalanceFactor.EH;
244                         lc.bFactor=BalanceFactor.RH;
245                         break;
246                     }
247                     case EH:{
248                         node.bFactor=lc.bFactor=BalanceFactor.EH;
249                         break;
250                     }
251                     case RH:{
252                         node.bFactor=BalanceFactor.LH;
253                         lc.bFactor=BalanceFactor.EH;
254                         break;    
255                     }
256                 }//switch
257                 rd.bFactor=BalanceFactor.EH;
258                 rRotate(node.rchild);
259                 lRotate(node);
260                 break;
261             }
262         }
263     }
264     
265     
266     /**
267      * 对以node为根的子树进行单右旋处理，处理后node.parent指向新的树根，即旋转之前
268      * node的左孩子结点
269      *      100<-node.parent           80<-node.parent
270      *      /                          /  271      *     80             ———>        60   100
272      *    /  \                             /
273      *   60  85                           85
274      */
275     private void rRotate(AVLNode<E> node){
276         
277         AVLNode<E> lc=node.lchild;//lc指向node的左孩子结点
278         
279         node.lchild=lc.rchild;
280         lc.rchild=node;
281         if(node.parent==null){
282             root=lc;
283         }
284         else if(node.parent.lchild.key.compareTo(node.key)==0)
285             node.parent.lchild=lc;
286         else node.parent.rchild=lc;
287     }
288     /**
289      * 对以node为根的子树进行单左旋处理，处理后node.parent指向新的树根，即旋转之前
290      * node的右孩子结点
291      *      100<-node.parent        110<-node.parent
292      *        \                     /  293      *        110        ————>    100  120
294      *        /  \                   295      *      105  120                 105
296      */
297     private void lRotate(AVLNode<E> node){
298         AVLNode<E> rc=node.rchild;//lc指向node的右孩子结点
299         node.rchild=rc.lchild;
300         rc.lchild=node;
301         if(node.parent==null){
302             root=rc;
303             
304         }
305         else if(node.parent.lchild.key.compareTo(node.key)==0)
306                 node.parent.lchild=rc;
307         else node.parent.rchild=rc;
308     }
309     
310     /**
311      * 得到BST根节点
312      * @return BST根节点f
313      */
314     public AVLNode<E> getRoot(){
315         return this.root;
316     }
317  
318     /**
319      * 递归前序遍历树
320      */
321     public void preOrderTraverse(AVLNode<E> node){
322         if(node!=null){
323             System.out.println(node);
324             preOrderTraverse(node.lchild);
325             preOrderTraverse(node.rchild);
326         }
327     }
328     /**
329      * 测试
330      * @param args
331      */
332     public static void main(String[] args) {
333         AVL<Integer> avl=new AVL<Integer>();
334         avl.insert(new Integer(80));
335         avl.insert(new Integer(60));
336         avl.insert(new Integer(90));
337         avl.insert(new Integer(85));
338         avl.insert(new Integer(120));
339         avl.insert(new Integer(100));
340     
341         System.out.println("前序遍历AVL：");
342         avl.preOrderTraverse(avl.getRoot());
343 
344     }
345 }