你的位置:首页 > Java教程

[Java教程]树——平衡二叉树插入和查找的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);        }        reBuild(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:20   */   public void delete(int value){    AVLNode wantDeleteNode = find(value);    if(wantDeleteNode==null){      return;    }else{      if(wantDeleteNode.getLeftNode()==null&&wantDeleteNode.getRightNode()==null){//删除节点没有左右子树        AVLNode rootNode = wantDeleteNode.getRootNode();        if(rootNode!=null){          if(rootNode.getLeftNode()==wantDeleteNode){            rootNode.setLeftNode(null);          }else{            rootNode.setRightNode(null);          }          reBuild(rootNode);        }      }else if(wantDeleteNode.getRightNode()==null){//删除节点只有左子树        AVLNode rootNode = wantDeleteNode.getRootNode();        if(rootNode!=null){          if(rootNode.getLeftNode()==wantDeleteNode){            rootNode.setLeftNode(wantDeleteNode.getLeftNode());          }else{            rootNode.setRightNode(wantDeleteNode.getLeftNode());          }          wantDeleteNode.setLeftNode(null);          reBuild(rootNode);        }      }else if(wantDeleteNode.getLeftNode()==null){//删除节点只有右子树        AVLNode rootNode = wantDeleteNode.getRootNode();        if(rootNode!=null){          if(rootNode.getRightNode()==wantDeleteNode){            rootNode.setLeftNode(wantDeleteNode.getRightNode());          }else{            rootNode.setRightNode(wantDeleteNode.getRightNode());          }          wantDeleteNode.setRightNode(null);          reBuild(rootNode);        }      }else {//删除节点有左右子树        AVLNode maxNode = getLeftMaxValueNode(wantDeleteNode.getLeftNode());//找到节点左子树最大值的节点        AVLNode rootMaxNode = maxNode.getRootNode();//获得该节点的父节点        if(maxNode.getLeftNode()!=null){//如果最大值节点有左子树,则将最大值节点的父节点的右子树设为它          rootMaxNode.setRightNode(maxNode.getLeftNode());          maxNode.setLeftNode(null);        }else{//否则置空          rootMaxNode.setRightNode(null);        }        wantDeleteNode.setValue(maxNode.getValue());//把要删除节点的值用最大值节点的值替换        maxNode=null;//引用置空        reBuild(rootMaxNode);      }    }  }  //得到左子树最大值节点  private AVLNode getLeftMaxValueNode(AVLNode node){    if(node!=null&&node.getRightNode()!=null){      return getLeftMaxValueNode(node.getRightNode());    }else{      return node;    }  }    /**   * 查找一个节点   * @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;    }  }    /**   * 中序遍历   * @author tomsnail   * @date 2015年3月31日 下午6:23:05   */  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());    tree.delete(4);    System.out.println(isBalance(tree.getRootNode()));    System.out.println();    //tree.find(40);  }      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;  }}