亚洲激情专区-91九色丨porny丨老师-久久久久久久女国产乱让韩-国产精品午夜小视频观看

溫馨提示×

溫馨提示×

您好,登錄后才能下訂單哦!

密碼登錄×
登錄注冊×
其他方式登錄
點擊 登錄注冊 即表示同意《億速云用戶服務條款》

java實現 二叉搜索樹功能

發布時間:2020-08-19 16:21:16 來源:腳本之家 閱讀:141 作者:不懂是非 欄目:編程語言

一、概念

  二叉搜索樹也成二叉排序樹,它有這么一個特點,某個節點,若其有兩個子節點,則一定滿足,左子節點值一定小于該節點值,右子節點值一定大于該節點值,對于非基本類型的比較,可以實現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循環模式)。

  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;
  }
  /**
   * 獲取要插入的節點的父節點,該父節點滿足以下幾種狀態之一
   * 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;
    }
  }

   使用遞歸,先找到遞歸的結束點,再去把整個問題化為子問題,在上述代碼里,邏輯大致是這樣的,先判斷根節點有沒有初始化,沒初始化則初始化,完成后返回,之后通過一個函數去獲取適配的節點。之后進行插入值。

3.2、迭代版本

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

原理其實和遞歸一樣,都是獲取最佳節點,在該節點上進行操作。

論起性能,肯定迭代版本最佳,所以一般情況下,都是選擇迭代版本進行操作數據。

四、刪除

    可以說在二叉搜索樹的操作中,刪除是最復雜的,要考慮的情況也相對多,在常規思路中,刪除二叉搜索樹的某一個節點,肯定會想到以下四種情況,

 java實現 二叉搜索樹功能

   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 boolean remove(int val){
    Node node = getNode(val);
    if(node == null){
      return false;
    }
    if(node.leftChild == null){// 1、左節點不存在,右節點可能存在,包含兩種情況 ,兩個節點都不存在和只存在右節點
      transplant(node, node.rightChild);
    }else if(node.rightChild == null){//2、左孩子存在,右節點不存在
      transplant(node, node.leftChild);
    }else{// 3、兩個節點都存在
      Node successor = getSuccessor(node);// 得到node后繼節點 
      if(successor.parent != node){// 后繼節點存在node的右子樹中。
        transplant(successor, successor.rightChild);// 用后繼節點的右子節點替換該后繼節點
        successor.rightChild = node.rightChild;// 將node節點的右子樹賦給后繼節點的右節點,即類似后繼與node節點調換位置
        successor.rightChild.parent = successor;// 接著上一步 給接過來的右節點的父引用復制
      }
      transplant(node, successor);
      successor.leftChild = node.leftChild;
      successor.leftChild.parent = successor;
    }
    return true;
  }
  /**
   * 將child節點替換node節點
   * @param root  根節點
   * @param node  要刪除的節點
   * @param child  node節點的子節點
   */
  private void transplant(Node node,Node child){
    /**
     * 1、先判斷 node是否存在父節點
     *  1、不存在,則child替換為根節點
     *  2、存在,則繼續下一步
     * 2、判斷node節點是父節點的那個孩子(即判斷出 node是右節點還是左節點),
     *  得出結果后,將child節點替換node節點 ,即若node節點是左節點 則child替換后 也為左節點,否則為右節點
     * 3、將node節點的父節點置為child節點的父節點
     */
    
    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;
    }
  }

五、查找

  查找也比較簡單,其實在增加的時候,已經實現了。實際情況中,這部分可以抽出來單獨方法。代碼如下


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實現 二叉搜索樹功能,希望對大家有所幫助,如果大家有任何疑問歡迎給我留言,小編會及時回復大家的!

向AI問一下細節

免責聲明:本站發布的內容(圖片、視頻和文字)以原創、轉載和分享為主,文章觀點不代表本網站立場,如果涉及侵權請聯系站長郵箱:is@yisu.com進行舉報,并提供相關證據,一經查實,將立刻刪除涉嫌侵權內容。

AI

安国市| 怀远县| 准格尔旗| 安化县| 襄垣县| 南皮县| 大港区| 涟源市| 华蓥市| 开封市| 乌审旗| 丹巴县| 依安县| 郧西县| 托里县| 福鼎市| 南江县| 和田市| 正镶白旗| 龙山县| 米林县| 阳城县| 循化| 墨江| 区。| 五峰| 罗甸县| 铜梁县| 华蓥市| 香河县| 大方县| 石门县| 南昌市| 米泉市| 阳新县| 柳林县| 清远市| 襄垣县| 井冈山市| 拜泉县| 即墨市|