Java刪除二叉搜索樹的任意元素的方法詳解
本文實例講述了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é)點<當(dāng)前節(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é)點s(59節(jié)點)連接到d節(jié)點(58節(jié)點)父親節(jié)點的右邊,刪除d節(jié)點(58節(jié)點)后,后繼s節(jié)點(59節(jié)點)成為新的根,如下圖所示:

二、編碼實現(xiàn)二叉搜索樹的任意元素
根據(jù)上述的分析,在此基礎(chǔ)上進(jìn)行編碼,刪除代碼如下:
//從二叉搜索樹中刪除元素為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小于當(dāng)前節(jié)點值e)
node.left = remove(node.left, e);
return node;
}
if (e.compareTo(node.e) > 0) {//e>node.e (被刪除元素e大于當(dāng)前節(jié)點值e)
node.right = remove(node.right, e);
return node;
} else {//e==node.e (被刪除元素e等于當(dāng)前節(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)文章
AQS同步組件CyclicBarrier循環(huán)屏障用例剖析
這篇文章主要為大家介紹了AQS同步組件CyclicBarrier循環(huán)屏障用例剖析,有需要的朋友可以借鑒參考下,希望能夠有所幫助,祝大家多多進(jìn)步,早日升職加薪2022-08-08
MyBatis關(guān)聯(lián)查詢的實現(xiàn)
MyBatis可以通過定義多個表的關(guān)聯(lián)關(guān)系,實現(xiàn)多表查詢,本文主要介紹了MyBatis關(guān)聯(lián)查詢的實現(xiàn),具有一定的參考價值,感興趣的可以了解一下2023-11-11
Java使用抽象工廠模式實現(xiàn)的肯德基消費案例詳解
這篇文章主要介紹了Java使用抽象工廠模式實現(xiàn)的肯德基消費案例,較為詳細(xì)的分析了抽象工廠模式的定義、原理并結(jié)合實例形式分析了Java使用抽象工廠模式實現(xiàn)肯德基消費案例的步驟與相關(guān)操作技巧,需要的朋友可以參考下2018-05-05
java發(fā)起http請求調(diào)用post與get接口的方法實例
在實際開發(fā)過程中,我們經(jīng)常需要調(diào)用對方提供的接口或測試自己寫的接口是否合適,下面這篇文章主要給大家介紹了關(guān)于java發(fā)起http請求調(diào)用post與get接口的相關(guān)資料,需要的朋友可以參考下2022-08-08

