數(shù)據(jù)結(jié)構(gòu)（一）數(shù)組實(shí)現(xiàn)一個(gè)簡單的ArrayList
數(shù)據(jù)結(jié)構(gòu)（二）鏈表實(shí)現(xiàn)LinkedList
數(shù)據(jù)結(jié)構(gòu)（三）用兩種方式簡單實(shí)現(xiàn)棧
數(shù)據(jù)結(jié)構(gòu)（四）棧和隊(duì)列的簡單應(yīng)用
數(shù)據(jù)結(jié)構(gòu)（五）用兩種方式簡單實(shí)現(xiàn)隊(duì)列
數(shù)據(jù)結(jié)構(gòu)（六）二分搜索樹(Binary Search Tree)（上）
數(shù)據(jù)結(jié)構(gòu)（六）二分搜索樹(Binary Search Tree)（下）
數(shù)據(jù)結(jié)構(gòu)（七）兩種方式實(shí)現(xiàn)set
數(shù)據(jù)結(jié)構(gòu)（八）兩種方式實(shí)現(xiàn)map
數(shù)據(jù)結(jié)構(gòu)（九）set解決LeetCode349號(hào)問題
今天這篇文章是接上次的文章茵休，二分搜索樹還有幾個(gè)方法沒有分析完薪棒。簡單回顧一下，昨天我們分析了添加操作榕莺，是否包含操作赃阀，最小值澎媒，最大值镇眷，以及刪除最大值最小值操作鼓鲁。今天我們分析一下刪除操作，以及他的幾個(gè)遍歷方法：前序遍歷唠雕，中序遍歷以及后續(xù)遍歷扣蜻。
- preOrder
// 二分搜索樹的前序遍歷
public void preOrder(){
preOrder(root);
}
// 前序遍歷以node為根的二分搜索樹, 遞歸算法
private void preOrder(Node node){
if(node == null)
return;
System.out.println(node.e);
preOrder(node.left);
preOrder(node.right);
}
這里我們同樣用遞歸實(shí)現(xiàn)前序遍歷。先找到結(jié)束的條件就是當(dāng)前節(jié)點(diǎn)為空就結(jié)束了及塘。前序遍歷就是先打印當(dāng)前節(jié)點(diǎn)莽使，然后再打印左子樹然后是右子樹。這樣前序遍歷就完成笙僚。
大家可以看一下上邊這個(gè)圖芳肌。這里就是前序遍歷的順序圖。下邊這個(gè)圖是她的打印結(jié)果肋层。
- inOrder 好了看完了前序遍歷我們來看一下中序遍歷其實(shí)和前序遍歷一樣
// 二分搜索樹的中序遍歷
public void inOrder(){
inOrder(root);
}
// 中序遍歷以node為根的二分搜索樹, 遞歸算法
private void inOrder(Node node){
if(node == null)
return;
inOrder(node.left);
System.out.println(node.e);
inOrder(node.right);
}
這里唯一一點(diǎn)不同的是 先打印左子樹亿笤，然后是根節(jié)點(diǎn)，然后是右子樹栋猖。下邊是她的打印結(jié)果净薛。
大家有沒有發(fā)現(xiàn)一個(gè)好玩的地方，對沒錯(cuò)他是按從小到大的順序排序好的蒲拉。所以二分搜索樹的一個(gè)特性就是中序遍歷是從小到大的排序好的肃拜。
- postOrder
后續(xù)遍歷跟之前的前序痴腌、中序遍歷一樣我想大家都可以自己寫出代碼,這里我們就不過多的解釋。
postOrder(node.left);
postOrder(node.right);
System.out.println(node.e);
- remove
//刪除以node為根的二分搜索樹中元素為e的節(jié)點(diǎn)燃领，遞歸算法
//返回刪除節(jié)點(diǎn)后二分搜索樹的根
private Node remove(Node node, E e) {
if (node == null)
return null;
if (e.compareTo(node.e) < 0) {
node.left = remove(node.left, e);
return node;
} else if (e.compareTo(node.e) > 0) {
node.right = remove(node.right, e);
return node;
} else {// e == node.e
if (node.left == null) {
Node right = node.right;
node.right = null;
size--;
return right;
}
if (node.right == null) {
Node left = node.left;
node.left = null;
size--;
return left;
}
Node successor = mininum(node.right);
successor.right = removeMin(node.right);
successor.left = node.left;
node.left = node.right = null;
return successor;
}
}
刪除方法這個(gè)比較復(fù)雜了士聪，這里也是遞歸的方式實(shí)現(xiàn)。寫一個(gè)以node為根的節(jié)點(diǎn)的方法猛蔽。如果這個(gè)節(jié)點(diǎn)為空就返回空剥悟，如果傳入的元素比當(dāng)前節(jié)點(diǎn)的的元素小，那么就去他的左子樹去找曼库；如果傳入的元素比當(dāng)前節(jié)點(diǎn)的元素大那么就去他的右子樹去找区岗。如果傳入的元素等于當(dāng)前節(jié)點(diǎn)那么又有三種情況：如果左子樹是空的，那么直接刪除這個(gè)節(jié)點(diǎn)毁枯，然后把他的右子樹返回就可以了躏尉；如果這個(gè)節(jié)點(diǎn)的右子樹為空那么就刪除這個(gè)節(jié)點(diǎn)，然后把它的左子樹返回就可以了后众；如果刪除的這個(gè)節(jié)點(diǎn)左右子樹都不為空，那么就吧右子樹的最小值放到這個(gè)節(jié)點(diǎn)上就可以了颅拦，當(dāng)然也可以把左子樹的最大值放到這個(gè)節(jié)點(diǎn)上蒂誉，這樣還滿足這是一棵二分搜索樹。具體的替換綠色的小球表示要替換旁邊紅色的小球距帅，紅色小球是要被替換的小球右锨。
到這里二分搜索書的基本方法都介紹完了。希望大家可以明白碌秸，有什么不明白的可以評論里說绍移。
