溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
本文實例講述了Java刪除二叉搜索樹的任意元素的方法。分享給大家供大家參考，具體如下：
在刪除二叉搜索樹的任意元素時，會有三種情況：
節點刪除之后，將左孩子所在的二叉樹取代其位置；連在原來節點父親元素右節點的位置，比如在圖中需要刪除58這個節點。
刪除58這個節點后，如下圖所示：
節點刪除之后，將右孩子所在的二叉樹取代其位置；連在原來節點的位置，比如在下圖中需要刪除58這個節點。
刪除58這個節點后，如下圖所示：
這里需要說明說一下，以上兩種情況其實包含了葉子節點情況的，我們可以把葉子節點理解成只有左孩子的節點，也可以把它理解為只有右孩子的節點，只不過左孩子、右孩子為null。
如下圖，二叉搜索樹包含有左右孩子，假設現需要刪除58這個節點。
針對該種情況，分析如下：
我們把58這個節點記為d節點（包含有左子樹與右子樹）,如下圖所示：
針對這種節點刪除情況需要把左子樹與右子樹融合起來，融合方法：
從d這節點的左孩子與右孩子中找一個比d節點還要大的節點取代d節點，根據二叉搜索樹的性質可知（左邊節點<當前節點<右邊節點），這個需要被找的節點存在于d節點的右孩子節點中。
尋找規則：
尋找需要被刪除節點58(d)的后繼的所有元素中，離 58 最近的且比 58 大的節點，在本例中為59這個節點【即右子樹中的最小值】，記為s，如下圖所示：
刪除步驟：
（1）從d的右子樹中刪除最小值，將刪除最小值s后的d的右子樹, 變為d后繼節點s的右孩子，如下圖所示：
（2）將d節點（58節點）的左子樹，變為后繼節點s(59節點)的左子樹，如下圖所示：
(3)將后繼節點s（59節點）連接到d節點（58節點）父親節點的右邊，刪除d節點（58節點）后,后繼s節點（59節點）成為新的根，如下圖所示：
根據上述的分析，在此基礎上進行編碼，刪除代碼如下：
//從二叉搜索樹中刪除元素為e的節點
public void remove(E e) {
root = remove(root, e);
}
//刪除以node為根的二叉搜索樹中值為e的節點，遞歸算法
//返回刪除節點后更新的二叉搜索樹的根
private Node remove(Node node, E e) {
if (node == null)
return null;
if (e.compareTo(node.e) < 0) {//e<node.e (被刪除元素e小于當前節點值e)
node.left = remove(node.left, e);
return node;
}
if (e.compareTo(node.e) > 0) {//e>node.e (被刪除元素e大于當前節點值e)
node.right = remove(node.right, e);
return node;
} else {//e==node.e (被刪除元素e等于當前節點值e)
//待刪除節點左子樹為空情況
if (node.left == null) {
Node rightNode = node.right;
node.right = null;
size--;
return rightNode;
}
//待刪除節點右子樹為空情況
if (node.right == null) {
Node leftNode = node.left;
node.left = null;
size--;
return leftNode;
}
//左右子樹均不為空
//方法：找到比待刪除節點大的最小節點，即待刪除節點右子樹的最小節點
//用這個節點頂替待刪除節點的位置
Node successor = minimum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
對于上述代碼中的minimum函數，在5.3節中已經實現，此處同樣也把代碼列出來：
// 尋找二分搜索樹的最小元素
public E minimum() {
if (size == 0) {
throw new IllegalArgumentException("BST is empty");
}
Node ninNode = minimum(root);
return ninNode.e;
}
// 返回以node為根的二分搜索樹的最小值所在的節點
private Node minimum(Node node) {
if (node.left == null) {
return node;
}
//返回相應的節點的左子樹的最小值
return minimum(node.left);
}
源碼地址 https://github.com/FelixBin/dataStructure/blob/master/src/BST/BST.java
更多關于java算法相關內容感興趣的讀者可查看本站專題：《Java數據結構與算法教程》、《Java操作DOM節點技巧總結》、《Java文件與目錄操作技巧匯總》和《Java緩存操作技巧匯總》
希望本文所述對大家java程序設計有所幫助。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
