最新国产好看的视频,伊人天堂AV在线,国产Aaaaaa视频,蜜臀视频在线观看一区,人妻av色图,密臀久久久精品影片,青青视频免费观看毛片,久草在线观看视,国产三级精品色情在线

Java刪除二叉搜索樹的任意元素的方法詳解

 更新時間:2020年03月29日 12:02:50   作者:WFaceBoss  
這篇文章主要介紹了Java刪除二叉搜索樹的任意元素的方法,結(jié)合實例形式詳細分析了java這對二叉搜索樹的遍歷、查找、刪除等相關(guān)操作技巧與使用注意事項,需要的朋友可以參考下

本文實例講述了Java刪除二叉搜索樹的任意元素的方法。分享給大家供大家參考,具體如下:

一.刪除思路分析

在刪除二叉搜索樹的任意元素時,會有三種情況:

1.1 刪除只有左孩子的節(jié)點

節(jié)點刪除之后,將左孩子所在的二叉樹取代其位置;連在原來節(jié)點父親元素右節(jié)點的位置,比如在圖中需要刪除58這個節(jié)點。

刪除58這個節(jié)點后,如下圖所示:

 

 

1.2 刪除只有右孩子的節(jié)點:

節(jié)點刪除之后,將右孩子所在的二叉樹取代其位置;連在原來節(jié)點的位置,比如在下圖中需要刪除58這個節(jié)點。

刪除58這個節(jié)點后,如下圖所示:

這里需要說明說一下,以上兩種情況其實包含了葉子節(jié)點情況的,我們可以把葉子節(jié)點理解成只有左孩子的節(jié)點,也可以把它理解為只有右孩子的節(jié)點,只不過左孩子、右孩子為null

1.3 刪除包含左右孩子的節(jié)點

如下圖,二叉搜索樹包含有左右孩子,假設(shè)現(xiàn)需要刪除58這個節(jié)點。

針對該種情況,分析如下:
我們把58這個節(jié)點記為d節(jié)點(包含有左子樹與右子樹),如下圖所示:

針對這種節(jié)點刪除情況需要把左子樹與右子樹融合起來,融合方法:
d這節(jié)點的左孩子與右孩子中找一個比d節(jié)點還要大的節(jié)點取代d節(jié)點,根據(jù)二叉搜索樹的性質(zhì)可知(左邊節(jié)點<當前節(jié)點<右邊節(jié)點),這個需要被找的節(jié)點存在于d節(jié)點的右孩子節(jié)點中。

尋找規(guī)則:
尋找需要被刪除節(jié)點58(d)的后繼的所有元素中,離 58 最近的且比 58 大的節(jié)點,在本例中為59這個節(jié)點【即右子樹中的最小值】,記為s,如下圖所示:

刪除步驟:

(1)從d的右子樹中刪除最小值,將刪除最小值s后的d的右子樹, 變?yōu)?code>d后繼節(jié)點s的右孩子,如下圖所示:

(2)將d節(jié)點(58節(jié)點)的左子樹,變?yōu)楹罄^節(jié)點s(59節(jié)點)的左子樹,如下圖所示:

(3)將后繼節(jié)點s59節(jié)點)連接到d節(jié)點(58節(jié)點)父親節(jié)點的右邊,刪除d節(jié)點(58節(jié)點)后,后繼s節(jié)點(59節(jié)點)成為新的根,如下圖所示:

二、編碼實現(xiàn)二叉搜索樹的任意元素

根據(jù)上述的分析,在此基礎(chǔ)上進行編碼,刪除代碼如下:

//從二叉搜索樹中刪除元素為e的節(jié)點
  public void remove(E e) {
    root = remove(root, e);
  }

  //刪除以node為根的二叉搜索樹中值為e的節(jié)點,遞歸算法
  //返回刪除節(jié)點后更新的二叉搜索樹的根
  private Node remove(Node node, E e) {
    if (node == null)
      return null;

    if (e.compareTo(node.e) < 0) {//e<node.e (被刪除元素e小于當前節(jié)點值e)
      node.left = remove(node.left, e);
      return node;
    }
    if (e.compareTo(node.e) > 0) {//e>node.e (被刪除元素e大于當前節(jié)點值e)
      node.right = remove(node.right, e);
      return node;
    } else {//e==node.e (被刪除元素e等于當前節(jié)點值e)

      //待刪除節(jié)點左子樹為空情況
      if (node.left == null) {
        Node rightNode = node.right;
        node.right = null;
        size--;
        return rightNode;
      }

      //待刪除節(jié)點右子樹為空情況
      if (node.right == null) {
        Node leftNode = node.left;
        node.left = null;
        size--;
        return leftNode;
      }

      //左右子樹均不為空
      //方法:找到比待刪除節(jié)點大的最小節(jié)點,即待刪除節(jié)點右子樹的最小節(jié)點
      //用這個節(jié)點頂替待刪除節(jié)點的位置
      Node successor = minimum(node.right);
      successor.right = removeMin(node.right);
      successor.left = node.left;
      node.left = node.right = null;

      return successor;
    }
  }

對于上述代碼中的minimum函數(shù),在5.3節(jié)中已經(jīng)實現(xiàn),此處同樣也把代碼列出來:

// 尋找二分搜索樹的最小元素
  public E minimum() {
    if (size == 0) {
      throw new IllegalArgumentException("BST is empty");
    }

    Node ninNode = minimum(root);
    return ninNode.e;
  }

  // 返回以node為根的二分搜索樹的最小值所在的節(jié)點
  private Node minimum(Node node) {
    if (node.left == null) {
      return node;
    }

    //返回相應(yīng)的節(jié)點的左子樹的最小值
    return minimum(node.left);
  }

源碼地址 https://github.com/FelixBin/dataStructure/blob/master/src/BST/BST.java

更多關(guān)于java算法相關(guān)內(nèi)容感興趣的讀者可查看本站專題:《Java數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Java操作DOM節(jié)點技巧總結(jié)》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總

希望本文所述對大家java程序設(shè)計有所幫助。

相關(guān)文章

  • Java+Selenium調(diào)用JavaScript的方法詳解

    Java+Selenium調(diào)用JavaScript的方法詳解

    這篇文章主要為大家講解了java在利用Selenium操作瀏覽器網(wǎng)站時候,有時會需要用的JavaScript的地方,代碼該如何實現(xiàn)呢?快跟隨小編一起學習一下吧
    2023-01-01
  • Spring Boot單元測試中使用mockito框架mock掉整個RedisTemplate的示例

    Spring Boot單元測試中使用mockito框架mock掉整個RedisTemplate的示例

    今天小編就為大家分享一篇關(guān)于Spring Boot單元測試中使用mockito框架mock掉整個RedisTemplate的示例,小編覺得內(nèi)容挺不錯的,現(xiàn)在分享給大家,具有很好的參考價值,需要的朋友一起跟隨小編來看看吧
    2018-12-12
  • java輸入多個數(shù)據(jù)(不確定),排序,并求最大值的方法

    java輸入多個數(shù)據(jù)(不確定),排序,并求最大值的方法

    今天小編就為大家分享一篇java輸入多個數(shù)據(jù)(不確定),排序,并求最大值的方法,具有很好的參考價值,希望對大家有所幫助。一起跟隨小編過來看看吧
    2018-07-07
  • 淺談SpringMVC HandlerInterceptor詭異問題排查

    淺談SpringMVC HandlerInterceptor詭異問題排查

    這篇文章主要介紹了淺談SpringMVC HandlerInterceptor詭異問題排查,小編覺得挺不錯的,現(xiàn)在分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2019-05-05
  • JAVA時間戳-Calendar類使用(包括set,get,add方法)

    JAVA時間戳-Calendar類使用(包括set,get,add方法)

    這篇文章主要介紹了JAVA時間戳-Calendar類使用(包括set,get,add方法),具有很好的參考價值,希望對大家有所幫助,如有錯誤或未考慮完全的地方,望不吝賜教
    2024-04-04
  • Spring后處理器詳細介紹

    Spring后處理器詳細介紹

    Bean后置處理器允許在調(diào)用初始化方法前后對Bean進行額外的處理。可以在?Spring容器通過插入一個或多個BeanPostProcessor的實現(xiàn)來完成實例化,配置和初始化一個?bean?之后實現(xiàn)一些自定義邏輯回調(diào)方法
    2023-02-02
  • springboot集成druid連接池配置的方法

    springboot集成druid連接池配置的方法

    這篇文章主要介紹了springboot集成druid連接池配置的方法,文中通過示例代碼介紹的非常詳細,對大家的學習或者工作具有一定的參考學習價值,需要的朋友們下面隨著小編來一起學習學習吧
    2020-12-12
  • Spring中存儲Bean的常見注解方式

    Spring中存儲Bean的常見注解方式

    Spring框架中的控制反轉(zhuǎn)(IoC)和依賴注入(DI)是核心概念,實現(xiàn)了對象的解耦和動態(tài)依賴,IoC容器負責對象的生命周期和對象間的依賴關(guān)系,通過DI方式注入依賴,本文介紹Spring中存儲Bean的常見注解方式,感興趣的朋友一起看看吧
    2024-09-09
  • Java布爾值Boolean和boolean之間轉(zhuǎn)換實例用法

    Java布爾值Boolean和boolean之間轉(zhuǎn)換實例用法

    在本篇文章里小編給大家整理的是一篇關(guān)于Java布爾值Boolean和boolean之間轉(zhuǎn)換實例用法內(nèi)容,有需要的朋友們跟著學習參考下。
    2021-06-06
  • 全面了解JAVA_BaseDAO數(shù)據(jù)處理類

    全面了解JAVA_BaseDAO數(shù)據(jù)處理類

    下面小編就為大家?guī)硪黄媪私釰AVA_BaseDAO數(shù)據(jù)處理類。小編覺得挺不錯的,現(xiàn)在就分享給大家,也給大家做個參考。一起跟隨小編過來看看吧
    2016-07-07

最新評論

神农架林区| 巴东县| 阿拉善右旗| 阳信县| 大丰市| 调兵山市| 拉萨市| 吉隆县| 龙陵县| 衡山县| 正阳县| 射洪县| 府谷县| 颍上县| 常熟市| 佳木斯市| 九江县| 湛江市| 民权县| 黔西县| 工布江达县| 永泰县| 清苑县| 桐城市| 乌鲁木齐县| 西林县| 溧水县| 龙陵县| 扎兰屯市| 梧州市| 德惠市| 西平县| 安庆市| 隆化县| 东明县| 镇安县| 兴山县| 石河子市| 达拉特旗| 浪卡子县| 渑池县|