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

以上就是“java如何實現二叉搜索樹功能”這篇文章的所有內容，感謝各位的閱讀！相信大家閱讀完這篇文章都有很大的收獲，小編每天都會為大家更新不同的知識，如果還想學習更多的知識，請關注億速云行業資訊頻道。