你的位置:首页 > 软件开发 > Java > 树——平衡二叉树插入和查找的JAVA实现

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

发布时间:2015-03-31 02:01:31
package com.tomsnail.data.tree;/** * AVL二叉平衡树 * @author tomsnail * @date 2015年3月30日 下午4:35:50 */public class AVLTree { /** * 根节点 * @a ...
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;  }}

原标题:树——平衡二叉树插入和查找的JAVA实现

关键词:JAVA

*特别声明:以上内容来自于网络收集,著作权属原作者所有,如有侵权,请联系我们: admin#shaoqun.com (#换成@)。