java實(shí)現(xiàn) 二叉搜索樹功能

更新時(shí)間：2018年07月08日 15:09:31 作者：不懂是非

這篇文章主要介紹了java實(shí)現(xiàn) 二叉搜索樹功能,代碼簡(jiǎn)單易懂，非常不錯(cuò)，具有一定的參考借鑒價(jià)值，需要的朋友可以參考下

一、概念

二叉搜索樹也成二叉排序樹，它有這么一個(gè)特點(diǎn)，某個(gè)節(jié)點(diǎn)，若其有兩個(gè)子節(jié)點(diǎn)，則一定滿足，左子節(jié)點(diǎn)值一定小于該節(jié)點(diǎn)值，右子節(jié)點(diǎn)值一定大于該節(jié)點(diǎn)值，對(duì)于非基本類型的比較，可以實(shí)現(xiàn)Comparator接口，在本文中為了方便，采用了int類型數(shù)據(jù)進(jìn)行操作。

要想實(shí)現(xiàn)一顆二叉樹，肯定得從它的增加說(shuō)起，只有把樹構(gòu)建出來(lái)了，才能使用其他操作。

二、二叉搜索樹構(gòu)建

談起二叉樹的增加，肯定先得構(gòu)建一個(gè)表示節(jié)點(diǎn)的類，該節(jié)點(diǎn)的類，有這么幾個(gè)屬性，節(jié)點(diǎn)的值，節(jié)點(diǎn)的父節(jié)點(diǎn)、左節(jié)點(diǎn)、右節(jié)點(diǎn)這四個(gè)屬性，代碼如下

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);
    }
  }

這里采用的是內(nèi)部類的寫法，構(gòu)建完節(jié)點(diǎn)值后，再對(duì)整棵樹去構(gòu)建，一棵樹，先得有根節(jié)點(diǎn)，再能延伸到余下子節(jié)點(diǎn)，那在這棵樹里，也有一些屬性，比如基本的根節(jié)點(diǎn)root,樹中元素大小size，這兩個(gè)屬性，如果采用了泛型，可能還得增加Comparator屬性，或提供其一個(gè)默認(rèn)實(shí)現(xiàn)。具體代碼如下

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

三、增加

當(dāng)要進(jìn)行添加元素的時(shí)候，得考慮根節(jié)點(diǎn)的初始化，一般情況有兩種、當(dāng)該類的構(gòu)造函數(shù)一初始化就對(duì)根節(jié)點(diǎn)root進(jìn)行初始化，第二種、在進(jìn)行第一次添加元素的時(shí)候，對(duì)根節(jié)點(diǎn)進(jìn)行添加。理論上兩個(gè)都可以行得通，但通常采用的是第二種懶加載形式。

在進(jìn)行添加元素的時(shí)候，有這樣幾種情況需要考慮

一、添加時(shí)判斷root是否初始化，若沒(méi)初始化，則初始化，將該值賦給根節(jié)點(diǎn)，size加一。

二、因?yàn)槎鏄渌阉鳂錆M足根節(jié)點(diǎn)值大于左節(jié)點(diǎn)，小于右節(jié)點(diǎn)，需要將插入的值，先同根節(jié)點(diǎn)比較，若大，則往右子樹中進(jìn)行查找，若小，則往左子樹中進(jìn)行查找。直到某個(gè)子節(jié)點(diǎn)。

這里的插入實(shí)現(xiàn)，可以采用兩種，一、遞歸、二、迭代(即通過(guò)while循環(huán)模式)。

3.1、遞歸版本插入

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;
  }
  /**
   * 獲取要插入的節(jié)點(diǎn)的父節(jié)點(diǎn)，該父節(jié)點(diǎn)滿足以下幾種狀態(tài)之一
   * 1、父節(jié)點(diǎn)為子節(jié)點(diǎn)
   * 2、插入節(jié)點(diǎn)值比父節(jié)點(diǎn)小，但父節(jié)點(diǎn)沒(méi)有左子節(jié)點(diǎn)
   * 3、插入節(jié)點(diǎn)值比父節(jié)點(diǎn)大，但父節(jié)點(diǎn)沒(méi)有右子節(jié)點(diǎn)
   * 4、插入節(jié)點(diǎn)值和父節(jié)點(diǎn)相等。
   * 5、父節(jié)點(diǎn)為空
   * 如果滿足以上5種情況之一，則遞歸停止。
   * @param node
   * @param val
   * @return
   */
  private Node getAdapterNode(Node node,int val){
    if(node == null){
      return node;
    }
    // 往左子樹中插入，但沒(méi)左子樹，則返回
    if(node.val > val && node.leftChild == null){
      return node;
    }
    // 往右子樹中插入，但沒(méi)右子樹，也返回
    if(node.val < val && node.rightChild == null){
      return node;
    }
    // 該節(jié)點(diǎn)是葉子節(jié)點(diǎn)，則返回
    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;
    }
  }

使用遞歸，先找到遞歸的結(jié)束點(diǎn)，再去把整個(gè)問(wèn)題化為子問(wèn)題，在上述代碼里，邏輯大致是這樣的，先判斷根節(jié)點(diǎn)有沒(méi)有初始化，沒(méi)初始化則初始化，完成后返回，之后通過(guò)一個(gè)函數(shù)去獲取適配的節(jié)點(diǎn)。之后進(jìn)行插入值。

3.2、迭代版本

public boolean put(int val){
    return putVal(root,val);
  }
  private boolean putVal(Node node,int val){
    if(node == null){// 初始化根節(jié)點(diǎn)
      node = new Node(val);
      root = node;
      size++;
      return true;
    }
    Node temp = node;
    Node p;
    int t;
    /**
     * 通過(guò)do while循環(huán)迭代獲取最佳節(jié)點(diǎn)，
     */
    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;
  }

原理其實(shí)和遞歸一樣，都是獲取最佳節(jié)點(diǎn)，在該節(jié)點(diǎn)上進(jìn)行操作。

論起性能，肯定迭代版本最佳，所以一般情況下，都是選擇迭代版本進(jìn)行操作數(shù)據(jù)。

四、刪除

可以說(shuō)在二叉搜索樹的操作中，刪除是最復(fù)雜的，要考慮的情況也相對(duì)多，在常規(guī)思路中，刪除二叉搜索樹的某一個(gè)節(jié)點(diǎn)，肯定會(huì)想到以下四種情況,

1、要?jiǎng)h除的節(jié)點(diǎn)沒(méi)有左右子節(jié)點(diǎn)，如上圖的D、E、G節(jié)點(diǎn)

2、要?jiǎng)h除的節(jié)點(diǎn)只有左子節(jié)點(diǎn)，如B節(jié)點(diǎn)

3、要?jiǎng)h除的節(jié)點(diǎn)只有右子節(jié)點(diǎn)，如F節(jié)點(diǎn)

4、要?jiǎng)h除的節(jié)點(diǎn)既有左子節(jié)點(diǎn)，又有右子節(jié)點(diǎn)，如 A、C節(jié)點(diǎn)

對(duì)于前面三種情況，可以說(shuō)是比較簡(jiǎn)單，第四種復(fù)雜了。下面先來(lái)分析第一種

若是這種情況，比如刪除D節(jié)點(diǎn)，則可以將B節(jié)點(diǎn)的左子節(jié)點(diǎn)設(shè)置為null，若刪除G節(jié)點(diǎn)，則可將F節(jié)點(diǎn)的右子節(jié)點(diǎn)設(shè)置為null。具體要設(shè)置哪一邊，看刪除的節(jié)點(diǎn)位于哪一邊。

第二種，刪除B節(jié)點(diǎn)，則只需將A節(jié)點(diǎn)的左節(jié)點(diǎn)設(shè)置成D節(jié)點(diǎn)，將D節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置成A即可。具體設(shè)置哪一邊，也是看刪除的節(jié)點(diǎn)位于父節(jié)點(diǎn)的哪一邊。

第三種，同第二種。

第四種，也就是之前說(shuō)的有點(diǎn)復(fù)雜，比如要?jiǎng)h除C節(jié)點(diǎn)，將F節(jié)點(diǎn)的父節(jié)點(diǎn)設(shè)置成A節(jié)點(diǎn)，F(xiàn)節(jié)點(diǎn)左節(jié)點(diǎn)設(shè)置成E節(jié)點(diǎn)，將A的右節(jié)點(diǎn)設(shè)置成F，E的父節(jié)點(diǎn)設(shè)置F節(jié)點(diǎn)(也就是將F節(jié)點(diǎn)替換C節(jié)點(diǎn))，還有一種，直接將E節(jié)點(diǎn)替換C節(jié)點(diǎn)。那采用哪一種呢，如果刪除節(jié)點(diǎn)為根節(jié)點(diǎn)，又該怎么刪除？

對(duì)于第四種情況，可以這樣想，找到C或者A節(jié)點(diǎn)的后繼節(jié)點(diǎn)，刪除后繼節(jié)點(diǎn)，且將后繼節(jié)點(diǎn)的值設(shè)置為C或A節(jié)點(diǎn)的值。先來(lái)補(bǔ)充下后繼節(jié)點(diǎn)的概念。

一個(gè)節(jié)點(diǎn)在整棵樹中的后繼節(jié)點(diǎn)必滿足，大于該節(jié)點(diǎn)值得所有節(jié)點(diǎn)集合中值最小的那個(gè)節(jié)點(diǎn)，即為后繼節(jié)點(diǎn)，當(dāng)然，也有可能不存在后繼節(jié)點(diǎn)。

但是對(duì)于第四種情況，后繼節(jié)點(diǎn)一定存在，且一定在其右子樹中，而且還滿足，只有一個(gè)子節(jié)點(diǎn)或者沒(méi)有子節(jié)點(diǎn)兩者情況之一。具體原因可以這樣想，因?yàn)楹罄^節(jié)點(diǎn)要比C節(jié)點(diǎn)大，又因?yàn)镃節(jié)點(diǎn)左右子節(jié)一定存在，所以一定存在右子樹中的左子節(jié)點(diǎn)中。就比如C的后繼節(jié)點(diǎn)是F，A的后繼節(jié)點(diǎn)是E。

有了以上分析，那么實(shí)現(xiàn)也比較簡(jiǎn)單了，代碼如下

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;
    //以下所有父節(jié)點(diǎn)為空的情況，則表明刪除的節(jié)點(diǎn)是根節(jié)點(diǎn)
    if(leftChild == null && rightChild == null){//沒(méi)有子節(jié)點(diǎn)
      if(parent != null){
        if(parent.leftChild == node){
          parent.leftChild = null;
        }else if(parent.rightChild == node){
          parent.rightChild = null;
        }
      }else{//不存在父節(jié)點(diǎn)，則表明刪除節(jié)點(diǎn)為根節(jié)點(diǎn)
        root = null;
      }
      node = null;
      return true;
    }else if(leftChild == null && rightChild != null){// 只有右節(jié)點(diǎn)
      if(parent != null && parent.val > val){// 存在父節(jié)點(diǎn)，且node位置為父節(jié)點(diǎn)的左邊
        parent.leftChild = rightChild;
      }else if(parent != null && parent.val < val){// 存在父節(jié)點(diǎn)，且node位置為父節(jié)點(diǎn)的右邊
        parent.rightChild = rightChild;
      }else{
        root = rightChild;
      }
      node = null;
      return true;
    }else if(leftChild != null && rightChild == null){// 只有左節(jié)點(diǎn)
      if(parent != null && parent.val > val){// 存在父節(jié)點(diǎn)，且node位置為父節(jié)點(diǎn)的左邊
        parent.leftChild = leftChild;
      }else if(parent != null && parent.val < val){// 存在父節(jié)點(diǎn)，且node位置為父節(jié)點(diǎn)的右邊
        parent.rightChild = leftChild;
      }else{
        root = leftChild;
      }
      return true;
    }else if(leftChild != null && rightChild != null){// 兩個(gè)子節(jié)點(diǎn)都存在
      Node successor = getSuccessor(node);// 這種情況，一定存在后繼節(jié)點(diǎn)
      int temp = successor.val;
      boolean delete = delete(temp);
      if(delete){
        node.val = temp;
      }
      successor = null;
      return true;
    }
    return false;
  }
  
  /**
   * 找到node節(jié)點(diǎn)的后繼節(jié)點(diǎn)
   * 1、先判斷該節(jié)點(diǎn)有沒(méi)有右子樹，如果有，則從右節(jié)點(diǎn)的左子樹中尋找后繼節(jié)點(diǎn)，沒(méi)有則進(jìn)行下一步
   * 2、查找該節(jié)點(diǎn)的父節(jié)點(diǎn)，若該父節(jié)點(diǎn)的右節(jié)點(diǎn)等于該節(jié)點(diǎn)，則繼續(xù)尋找父節(jié)點(diǎn)，
   *  直至父節(jié)點(diǎn)為Null或找到不等于該節(jié)點(diǎn)的右節(jié)點(diǎn)。
   * 理由，后繼節(jié)點(diǎn)一定比該節(jié)點(diǎn)大，若存在右子樹，則后繼節(jié)點(diǎn)一定存在右子樹中，這是第一步的理由
   *   若不存在右子樹，則也可能存在該節(jié)點(diǎn)的某個(gè)祖父節(jié)點(diǎn)(即該節(jié)點(diǎn)的父節(jié)點(diǎn)，或更上層父節(jié)點(diǎn))的右子樹中，
   *   對(duì)其迭代查找，若有，則返回該節(jié)點(diǎn)，沒(méi)有則返回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;
  }

具體邏輯，看上面分析，這里不作文字?jǐn)⑹隽耍?/p>

除了這種實(shí)現(xiàn)，在算法導(dǎo)論書中，提供了另外一種實(shí)現(xiàn)。

public boolean remove(int val){
    Node node = getNode(val);
    if(node == null){
      return false;
    }
    if(node.leftChild == null){// 1、左節(jié)點(diǎn)不存在，右節(jié)點(diǎn)可能存在，包含兩種情況 ，兩個(gè)節(jié)點(diǎn)都不存在和只存在右節(jié)點(diǎn)
      transplant(node, node.rightChild);
    }else if(node.rightChild == null){//2、左孩子存在，右節(jié)點(diǎn)不存在
      transplant(node, node.leftChild);
    }else{// 3、兩個(gè)節(jié)點(diǎn)都存在
      Node successor = getSuccessor(node);// 得到node后繼節(jié)點(diǎn) 
      if(successor.parent != node){// 后繼節(jié)點(diǎn)存在node的右子樹中。
        transplant(successor, successor.rightChild);// 用后繼節(jié)點(diǎn)的右子節(jié)點(diǎn)替換該后繼節(jié)點(diǎn)
        successor.rightChild = node.rightChild;// 將node節(jié)點(diǎn)的右子樹賦給后繼節(jié)點(diǎn)的右節(jié)點(diǎn)，即類似后繼與node節(jié)點(diǎn)調(diào)換位置
        successor.rightChild.parent = successor;// 接著上一步 給接過(guò)來(lái)的右節(jié)點(diǎn)的父引用復(fù)制
      }
      transplant(node, successor);
      successor.leftChild = node.leftChild;
      successor.leftChild.parent = successor;
    }
    return true;
  }
  /**
   * 將child節(jié)點(diǎn)替換node節(jié)點(diǎn)
   * @param root  根節(jié)點(diǎn)
   * @param node  要?jiǎng)h除的節(jié)點(diǎn)
   * @param child  node節(jié)點(diǎn)的子節(jié)點(diǎn)
   */
  private void transplant(Node node,Node child){
    /**
     * 1、先判斷 node是否存在父節(jié)點(diǎn)
     *  1、不存在，則child替換為根節(jié)點(diǎn)
     *  2、存在，則繼續(xù)下一步
     * 2、判斷node節(jié)點(diǎn)是父節(jié)點(diǎn)的那個(gè)孩子(即判斷出 node是右節(jié)點(diǎn)還是左節(jié)點(diǎn))，
     *  得出結(jié)果后，將child節(jié)點(diǎn)替換node節(jié)點(diǎn) ，即若node節(jié)點(diǎn)是左節(jié)點(diǎn) 則child替換后 也為左節(jié)點(diǎn)，否則為右節(jié)點(diǎn)
     * 3、將node節(jié)點(diǎn)的父節(jié)點(diǎn)置為child節(jié)點(diǎn)的父節(jié)點(diǎn)
     */
    
    if(node.parent == null){
      this.root = child;
    }else if(node.parent.leftChild == node){
      node.parent.leftChild = child;
    }else if(node.parent.rightChild == node){
      node.parent.rightChild = child;
    }
    if(child != null){
      child.parent = node.parent;
    }
  }

五、查找

查找也比較簡(jiǎn)單，其實(shí)在增加的時(shí)候，已經(jīng)實(shí)現(xiàn)了。實(shí)際情況中，這部分可以抽出來(lái)單獨(dú)方法。代碼如下

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;
  }

六、二叉搜索樹遍歷

在了解二叉搜索樹的性質(zhì)后，很清楚的知道，它的中序遍歷是從小到大依次排列的，這里提供中序遍歷代碼

public void print(){
    print(root);
  }
  private void print(Node root){
    if(root != null){
      print(root.leftChild);
      System.out.println(root.val);// 位置在中間，則中序，若在前面，則為先序，否則為后續(xù)
      print(root.rightChild);
    }
  }

總結(jié)

以上所述是小編給大家介紹的java實(shí)現(xiàn) 二叉搜索樹功能，希望對(duì)大家有所幫助，如果大家有任何疑問(wèn)歡迎給我留言，小編會(huì)及時(shí)回復(fù)大家的！

您可能感興趣的文章: