乐趣区

关于java:java完成二叉搜索树功用

java 实现二叉搜寻树功能

概念

  二叉搜寻树也成二叉排序树,它有这么一个个性,某个节点,若其有两个子节点,则肯定满足,左子节点值肯定小于该节点值,右子节点值肯定大于该节点值,对于非基本类型的比较,可能实现 Comparator 接口,在本文中为了便利,采纳了 int 类型数据进行操作。
  要想实现一颗二叉树,必定得从它的减少说起,只有把树构建进去了,才能使用其余操作。
二叉搜寻树构建
   谈起二叉树的减少,必定先得构建一个示意节点的类,该节点的类,有这么几个属性,节点的值,节点的父节点、左节点、右节点这四个属性,代码如下

static class Node{
 Node parent;
 Node leftChild;
 Node rightChild;
 int val;
 public Node(Node parent, Node leftChild, Node rightChild,int val) {super();
   this.parent = parent;
   this.leftChild = leftChild;
   this.rightChild = rightChild;
   this.val = val;
 }
 public Node(int val){this(null,null,null,val);
 }
 public Node(Node node,int val){this(node,null,null,val);
 }
}

复制代码
        这里采纳的是外部类的写法,构建完节点值后,再对整棵树去构建,一棵树,先得有根节点,再能延长到余下子节点,那在这棵树里,也有一些属性,比如基本的根节点 root, 树中元素大小 size,这两个属性,如果采纳了泛型,可能还得减少 Comparator 属性,或提供其一个默认实现。具体代码如下

public class SearchBinaryTree {
private Node root;
private int size;
public SearchBinaryTree() {super();
}
}

复制代码

减少

    当要进行增加元素的时候,得考虑根节点的初始化,一般情况有两种、当该类的结构函数一初始化就对根节点 root 进行初始化,第二种、在进行第一次增加元素的时候,对根节点进行增加。实践上两个都可能行得通,但通常采纳的是第二种懒加载形式。
    在进行增加元素的时候,有这样几种情况需要考虑
       一、增加时判断 root 是否初始化,若没初始化,则初始化,将该值赋给根节点,size 加一。
       二、因为二叉树搜寻树满足根节点值大于左节点,小于右节点,需要将插入的值,先同根节点比较,若大,则往右子树中进行查找,若小,则往左子树中进行查找。直到某个子节点。
       这里的插入实现,可能采纳两种,一、递归、二、迭代(即通过 while 循环模式)。
 递归版本插入

public boolean add(int val){if(root == null){root = new Node(val);
     size++;
     return true;
   }
   Node node = getAdapterNode(root, val);
   Node newNode = new Node(val);
   if(node.val > val){
     node.leftChild = newNode;
     newNode.parent = node;
   }else if(node.val < val){
     node.rightChild = newNode;
     newNode.parent = node;
   }else{// 暂不做处理}
   size++;19     return true;
 }
 /**
  * 获取要插入的节点的父节点,该父节点满足以下几种状态之一
  * 1、父节点为子节点
  * 2、插入节点值比父节点小,但父节点没有左子节点
  * 3、插入节点值比父节点大,但父节点没有右子节点
  * 4、插入节点值和父节点相等。* 5、父节点为空
  * 如果满足以上 5 种情况之一,则递归停止。* @param node
  * @param val
  * @return
  */
 private Node getAdapterNode(Node node,int val){if(node == null){return node;}
   // 往左子树中插入,但没左子树,则返回
   if(node.val > val && node.leftChild == null){return node;}
   // 往右子树中插入,但没右子树,也返回
   if(node.val < val && node.rightChild == null){return node;}
   // 该节点是叶子节点,则返回
   if(node.leftChild == null && node.rightChild == null){return node;}
   if(node.val > val && node.leftChild != null){return getAdaptarNode(node.leftChild, val);
   }else if(node.val < val && node.rightChild != null){return getAdaptarNode(node.rightChild, val);
   }else{return node;}
 }

复制代码
   使用递归,先找到递归的结束点,再去把整个问题化为子问题,在上述代码里,逻辑大抵是这样的,先判断根节点有没有初始化,没初始化则初始化,实现后返回,之后通过一个函数去获取适配的节点。之后进行插入值。
迭代版本

public boolean put(int val){return putVal(root,val);
  }
  private boolean putVal(Node node,int val){if(node == null){// 初始化根节点
      node = new Node(val);
      root = node;
      size++;
      return true;
    }
    Node temp = node;
    Node p;
    int t;
    /**
     * 通过 do while 循环迭代获取最佳节点,*/
    do{ 
      p = temp;
      t = temp.val-val;
      if(t > 0){temp = temp.leftChild;}else if(t < 0){temp = temp.rightChild;}else{
        temp.val = val;
        return false;
      }
    }while(temp != null);
    Node newNode = new Node(p, val);
    if(t > 0){p.leftChild = newNode;}else if(t < 0){p.rightChild = newNode;}
    size++;
    return true;
  }

复制代码
原理其实和递归一样,都是获取最佳节点,在该节点上进行操作。
论起性能,必定迭代版本最佳,所以一般情况下,都是抉择迭代版本进行操作数据。

删除

    可能说在二叉搜寻树的操作中,删除是最简单的,要考虑的情况也绝对多,在惯例思路中,删除二叉搜寻树的某一个节点,必定会想到以下四种情况,
   1、要删除的节点没有左右子节点,如上图的 D、E、G 节点
   2、要删除的节点只有左子节点,如 B 节点
   3、要删除的节点只有右子节点,如 F 节点
   4、要删除的节点既有左子节点,又有右子节点,如 A、C 节点
对于后面三种情况,可能说是比较简略,第四种简单了。上面先来分析第一种
 若是这种情况,比如 删除 D 节点,则可能将 B 节点的左子节点设置为 null,若删除 G 节点,则可将 F 节点的右子节点设置为 null。具体要设置哪一边,看删除的节点位于哪一边。
第二种,删除 B 节点,则只需将 A 节点的左节点设置成 D 节点,将 D 节点的父节点设置成 A 即可。具体设置哪一边,也是看删除的节点位于父节点的哪一边。
第三种,同第二种。
第四种,也就是之前说的有点简单,比如要删除 C 节点,将 F 节点的父节点设置成 A 节点,F 节点左节点设置成 E 节点,将 A 的右节点设置成 F,E 的父节点设置 F 节点 (也就是将 F 节点替换 C 节点),还有一种,间接将 E 节点替换 C 节点。那采纳哪一种呢,如果删除节点为根节点,又该怎么删除?
 对于第四种情况,可能这样想,找到 C 或者 A 节点的后继节点,删除后继节点,且将后继节点的值设置为 C 或 A 节点的值。先来补充下后继节点的概念。
一个节点在整棵树中的后继节点必满足,大于该节点值得所有节点会合中值最小的那个节点,即为后继节点,当然,也有可能不存在后继节点。
然而对于第四种情况,后继节点肯定存在,且肯定在其右子树中,而且还满足,只有一个子节点或者没有子节点两者情况之一。具体原因可能这样想,因为后继节点要比 C 节点大,又因为 C 节点左右子节肯定存在,所以肯定存在右子树中的左子节点中。就比如 C 的后继节点是 F,A 的后继节点是 E。
有了以上分析,那么实现也比较简略了,代码如下

public boolean delete(int val){Node node = getNode(val);
    if(node == null){return false;}
    Node parent = node.parent;
    Node leftChild = node.leftChild;
    Node rightChild = node.rightChild;
    // 以下所有父节点为空的情况,则表明删除的节点是根节点
    if(leftChild == null && rightChild == null){// 没有子节点
      if(parent != null){if(parent.leftChild == node){parent.leftChild = null;}else if(parent.rightChild == node){parent.rightChild = null;}
      }else{// 不存在父节点,则表明删除节点为根节点
        root = null;
      }
      node = null;
      return true;
    }else if(leftChild == null && rightChild != null){// 只有右节点
      if(parent != null && parent.val > val){// 存在父节点,且 node 地位为父节点的右边
        parent.leftChild = rightChild;
      }else if(parent != null && parent.val < val){// 存在父节点,且 node 地位为父节点的左边
        parent.rightChild = rightChild;
      }else{root = rightChild;}
      node = null;
      return true;
    }else if(leftChild != null && rightChild == null){// 只有左节点
      if(parent != null && parent.val > val){// 存在父节点,且 node 地位为父节点的右边
        parent.leftChild = leftChild;
      }else if(parent != null && parent.val < val){// 存在父节点,且 node 地位为父节点的左边
        parent.rightChild = leftChild;
      }else{root = leftChild;}
      return true;
    }else if(leftChild != null && rightChild != null){// 两个子节点都存在
      Node successor = getSuccessor(node);// 这种情况,肯定存在后继节点
      int temp = successor.val;
      boolean delete = delete(temp);
      if(delete){node.val = temp;}
      successor = null;
      return true;
    }
    return false;
  }
  
  /**
   * 找到 node 节点的后继节点
   * 1、先判断该节点有没有右子树,如果有,则从右节点的左子树中寻找后继节点,没有则进行下一步
   * 2、查找该节点的父节点,若该父节点的右节点等于该节点,则持续寻找父节点,*  直至父节点为 Null 或找到不等于该节点的右节点。* 理由,后继节点肯定比该节点大,若存在右子树,则后继节点肯定存在右子树中,这是第一步的理由
   *   若不存在右子树,则也可能存在该节点的某个祖父节点 (即该节点的父节点,或更下层父节点) 的右子树中,*   对其迭代查找,若有,则返回该节点,没有则返回 null
   * @param node
   * @return
   */
  private Node getSuccessor(Node node){if(node.rightChild != null){
      Node rightChild = node.rightChild;
      while(rightChild.leftChild != null){rightChild = rightChild.leftChild;}
      return rightChild;
    }
    Node parent = node.parent;
    while(parent != null && (node == parent.rightChild)){
      node = parent;
      parent = parent.parent;
    }
    return parent;
  }

复制代码

查找

  查找也比较简略,其实在减少的时候,已经实现了。实际情况中,这部分可能抽出来独自方法。代码如下

public Node getNode(int val){
    Node temp = root;
    int t;
    do{
      t = temp.val-val;
      if(t > 0){temp = temp.leftChild;}else if(t < 0){temp = temp.rightChild;}else{return temp;}
    }while(temp != null);
    return null;
  }

复制代码

二叉搜寻树遍历

  在了解二叉搜寻树的性质后,很明显的知道,它的中序遍历是从小到大顺次排列的,这里提供中序遍历代码

public void print(){print(root);
  }
  private void print(Node root){if(root != null){print(root.leftChild);
      System.out.println(root.val);// 地位在两头,则中序,若在后面,则为先序,否则为后续
      print(root.rightChild);
    }
  }
退出移动版