树——平衡二叉树插入和查找的JAVA实现

package com.tomsnail.data.tree;/** * AVL二叉平衡树 * @author tomsnail * @date 2015年3月30日 下午4:35:50 */public class AVLTree {        /**     * 根节点     * @author tomsnail     * @date 2015年3月30日 下午4:36:54     */    PRivate AVLNode rootNode;        private String bulidType = "";        /**     * 增加一个节点     * @author tomsnail     * @date 2015年3月30日 下午4:36:08     */    public void add(int value){        AVLNode subNode = null;        if(rootNode==null){            subNode  = new AVLNode(value);            rootNode = subNode;        }else{                        subNode = addNode(rootNode,value);        }        reBuild(subNode);    }        private AVLNode addNode(AVLNode node,int value){        AVLNode subNode = null;        if(node.getValue()>value){            if(node.getLeftNode()==null){                subNode = new AVLNode(value);                node.setLeftNode(subNode);            }else{                subNode = addNode(node.getLeftNode(), value);            }        }        if(node.getValue()<value){            if(node.getRightNode()==null){                subNode = new AVLNode(value);                node.setRightNode(subNode);            }else{                subNode = addNode(node.getRightNode(),value);            }        }        return subNode;    }    /**     * 重平衡树     * @author tomsnail     * @date 2015年3月30日 下午5:42:00     */    private void reBuild(AVLNode node){        if(node!=null){            AVLNode tempRootNode = findTempRootNode(node);            if(tempRootNode!=null){                if(bulidType.equals("ll")){                    Lrotate(node,tempRootNode);                }else if(bulidType.equals("rr")){                    Rrotate(node,tempRootNode);                }else if(bulidType.equals("lr")){                    Rrotate(node,tempRootNode.getLeftNode());                    Lrotate(node,tempRootNode);                }else if(bulidType.equals("rl")){                    Lrotate(node,tempRootNode.getRightNode());                    Rrotate(node,tempRootNode);                }            }        }    }    /**     * 左旋     * @author tomsnail     * @date 2015年3月30日 下午9:23:28     */    private void Rrotate(AVLNode node,AVLNode tempRootNode){        AVLNode rotateNode = tempRootNode.getRightNode();        AVLNode rootNode = tempRootNode.getRootNode();        String type = "";        if(rootNode!=null){            if(rootNode.getLeftNode()==tempRootNode){                type="l";            }else{                type="r";            }        }        AVLNode adjustNode = rotateNode.getLeftNode();        rotateNode.setLeftNode(tempRootNode);        tempRootNode.setRightNode(null);        if(adjustNode!=null){            tempRootNode.setRightNode(adjustNode);        }        if(rootNode==null){            rotateNode.setRootNode(null);            this.rootNode = rotateNode;        }        if(type.equals("r")){            rootNode.setRightNode(rotateNode);        }else if(type.equals("l")){            rootNode.setLeftNode(rotateNode);        }    }    /**     * 右旋     * @author tomsnail     * @date 2015年3月30日 下午9:23:28     */    private void Lrotate(AVLNode node,AVLNode tempRootNode){        AVLNode rotateNode = tempRootNode.getLeftNode();        AVLNode rootNode = tempRootNode.getRootNode();        String type = "";        if(rootNode!=null){            if(rootNode.getLeftNode()==tempRootNode){                type="l";            }else{                type="r";            }        }        AVLNode adjustNode = rotateNode.getRightNode();        rotateNode.setRightNode(tempRootNode);        tempRootNode.setLeftNode(null);        if(adjustNode!=null){            tempRootNode.setLeftNode(adjustNode);        }        if(rootNode==null){            rotateNode.setRootNode(null);            this.rootNode = rotateNode;        }        if(type.equals("r")){            rootNode.setRightNode(rotateNode);        }else if(type.equals("l")){            rootNode.setLeftNode(rotateNode);        }    }        /**     * 查找最小不平衡的根节点     * @author tomsnail     * @date 2015年3月30日 下午5:40:55     */    private AVLNode findTempRootNode(AVLNode node){        AVLNode noB = getNoBalance(node);        if(noB==null){            return null;        }        if(isTypeLL(noB)){            bulidType = "ll";        }else if(isTypeRR(noB)){            bulidType = "rr";        }else if(isTypeLR(noB)){            bulidType = "lr";        }else if(isTypeRL(noB)){            bulidType = "rl";        }        return noB;    }        private boolean isTypeLL(AVLNode noB){        try {            if(noB.getRightNode()==null&&noB.getLeftNode().getRightNode()==null&&!noB.getLeftNode().getLeftNode().hasSubNode()){                return true;            }            if(noB.getRightNode()!=null&&noB.getLeftNode().getRightNode()!=null&&noB.getLeftNode().getLeftNode().hasSubNode()){                return true;            }        } catch (Exception e) {        }        return false;    }    private boolean isTypeRR(AVLNode noB){        try {            if(noB.getLeftNode()==null&&noB.getRightNode().getLeftNode()==null&&!noB.getRightNode().getRightNode().hasSubNode()){                return true;            }            if(noB.getLeftNode()!=null&&noB.getRightNode().getLeftNode()!=null&&noB.getRightNode().getRightNode().hasSubNode()){                return true;            }        } catch (Exception e) {        }        return false;    }    private boolean isTypeLR(AVLNode noB){        try {            if(noB.getRightNode()==null&&noB.getLeftNode().getLeftNode()==null&&!noB.getLeftNode().getRightNode().hasSubNode()){                return true;            }            if(noB.getRightNode()!=null&&noB.getLeftNode().getLeftNode()!=null&&noB.getLeftNode().getRightNode().hasSubNode()){                return true;            }        } catch (Exception e) {        }        return false;    }    private boolean isTypeRL(AVLNode noB){        try {            if(noB.getLeftNode()==null&&noB.getRightNode().getRightNode()==null&&!noB.getRightNode().getLeftNode().hasSubNode()){                return true;            }            if(noB.getLeftNode()!=null&&noB.getRightNode().getRightNode()!=null&&noB.getRightNode().getLeftNode().hasSubNode()){                return true;            }        } catch (Exception e) {        }        return false;    }        private AVLNode getNoBalance(AVLNode node){        if(node.getRootNode()==null){            return null;        }else{            if(!isBalance(node.getRootNode())){                return node.getRootNode();            }else{                return getNoBalance(node.getRootNode());            }        }    }/**     * 查找一个节点     * @author tomsnail     * @date 2015年3月30日 下午4:36:35     */    public AVLNode find(int value){        return findWith2(rootNode,value);    }    private AVLNode findWith2(AVLNode node,int value){        if(node==null){            return null;        }        System.out.println(node.getValue());        if(node.getValue()>value){            return findWith2(node.getLeftNode(),value);        }else if(node.getValue()<value){            return findWith2(node.getRightNode(),value);        }else{            return node;        }    }        public void midScan(AVLNode node){        if(node==null){            return;        }        midScan(node.getLeftNode());        System.out.println(node.getValue());        midScan(node.getRightNode());    }        public AVLNode getRootNode() {        return rootNode;    }    public static void main(String[] args) {        int[] is = new int[]{10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80};//10,11,23,3,5,44,32,4,6,18,19,7,8,70,50,60,40,55,65,53,80        AVLTree tree = new AVLTree();        for(int i=0;i<is.length;i++){            tree.add(is[i]);        }        System.out.println(tree.getRootNode().getValue());        System.out.println("----------------------------");        tree.midScan(tree.getRootNode());        System.out.println(isBalance(tree.getRootNode()));    }            public static int depth(AVLNode node){        if(node==null){            return 0;        }else{                    int ld = depth(node.getLeftNode());                    int rd = depth(node.getRightNode());                    return 1 + (ld >rd ? ld : rd);            }    }        public static boolean isBalance(AVLNode node){            if (node==null)                     return true;            int dis = depth(node.getLeftNode()) - depth(node.getRightNode());            if (dis>1 || dis<-1 )                    return false;            else                    return isBalance(node.getLeftNode()) && isBalance(node.getRightNode());    }}class AVLNode{    private int value;    private AVLNode leftNode;    private AVLNode rightNode;    private AVLNode rootNode;    public int getValue() {        return value;    }    public void setValue(int value) {        this.value = value;    }    public AVLNode getLeftNode() {        return leftNode;    }    public void setLeftNode(AVLNode leftNode) {        this.leftNode = leftNode;        if(leftNode!=null){            leftNode.setRootNode(this);        }    }    public AVLNode getRightNode() {        return rightNode;    }    public void setRightNode(AVLNode rightNode) {        this.rightNode = rightNode;        if(rightNode!=null){            rightNode.setRootNode(this);        }    }        public AVLNode getRootNode() {        return rootNode;    }    public void setRootNode(AVLNode rootNode) {        this.rootNode = rootNode;    }        public boolean hasSubNode(){        if(this.leftNode!=null||this.rightNode!=null){            return true;        }else{            return false;        }    }        public AVLNode(){    }    public AVLNode(int value){        this.value = value;    }}