Java數(shù)據(jù)結(jié)構(gòu)篇之實(shí)現(xiàn)二叉搜索樹的核心方法
1.0 二叉搜索樹的概述
二叉搜索樹是一種數(shù)據(jù)結(jié)構(gòu)，用于存儲數(shù)據(jù)并支持快速的插入、刪除和搜索操作。它是一種樹形結(jié)構(gòu)。
它具有以下特點(diǎn)：
- 每個節(jié)點(diǎn)最多有兩個子節(jié)點(diǎn)，分別稱為左子節(jié)點(diǎn)和右子節(jié)點(diǎn)。
- 對于每個節(jié)點(diǎn)，其左子節(jié)點(diǎn)的值小于該節(jié)點(diǎn)的值，右子節(jié)點(diǎn)的值大于該節(jié)點(diǎn)的值。
- 中序遍歷二叉搜索樹可以得到有序的元素序列。
由于其特性，二叉搜索樹在插入、刪除和搜索操作上具有較高的效率。在平均情況下，這些操作的時間復(fù)雜度為 O(log n)，其中 n 為樹中節(jié)點(diǎn)的數(shù)量。然而，如果樹的結(jié)構(gòu)不平衡，最壞情況下這些操作的時間復(fù)雜度可能會達(dá)到 O(n)。由于其高效的搜索特性，二叉搜索樹常被用于實(shí)現(xiàn)關(guān)聯(lián)數(shù)組和集合等數(shù)據(jù)結(jié)構(gòu)。然而，為了避免樹的結(jié)構(gòu)不平衡導(dǎo)致性能下降，人們也發(fā)展了平衡二叉搜索樹（如紅黑樹、AVL樹）等變種。
2.0 二叉搜索樹的成員變量及其構(gòu)造方法
外部類成員變量有：根節(jié)點(diǎn)、節(jié)點(diǎn)類（內(nèi)部類）。
外部類構(gòu)造方法：默認(rèn)的構(gòu)造方法，對外公開二叉搜索樹的核心方法。
節(jié)點(diǎn)類的成員變量有：
- key 關(guān)鍵字：相對比一般的二叉樹，二叉搜索樹可以明顯提高增刪查改的效率原因在于關(guān)鍵字，可以根據(jù)比較兩個關(guān)鍵字的大小進(jìn)行操作。
- value 值：作用則為存放值。
- left ：鏈接左節(jié)點(diǎn)。
- right：鏈接右節(jié)點(diǎn)。
節(jié)點(diǎn)類的構(gòu)造方法：
帶兩個參數(shù)的構(gòu)造方法：參數(shù)為 key 、value
帶四個參數(shù)的構(gòu)造方法：參數(shù)為 key 、value 、left 、right
代碼如下：
public class BinaryTree {
BinaryNode root = null;
static class BinaryNode {
int key;
Object value;
BinaryNode left;
BinaryNode right;
public BinaryNode(int kty, Object value) {
this.key = kty;
this.value = value;
}
public BinaryNode(int key, Object value, BinaryNode left, BinaryNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
}補(bǔ)充二叉搜索樹在增、刪、查、改的效率高的原因：
二叉搜索樹的高效性與其關(guān)鍵字的特性密切相關(guān)。二叉搜索樹的關(guān)鍵特性是，對于每個節(jié)點(diǎn)，其左子節(jié)點(diǎn)的值小于該節(jié)點(diǎn)的值，右子節(jié)點(diǎn)的值大于該節(jié)點(diǎn)的值。這種特性使得在二叉搜索樹中進(jìn)行搜索、插入和刪除操作時，可以通過比較關(guān)鍵字的大小來快速定位目標(biāo)節(jié)點(diǎn)，從而實(shí)現(xiàn)高效的操作。在平均情況下，這些操作的時間復(fù)雜度為 O(log n)，其中 n 為樹中節(jié)點(diǎn)的數(shù)量。因此，關(guān)鍵字的有序性是二叉搜索樹能夠?qū)崿F(xiàn)高效操作的關(guān)鍵原因之一。
3.0 實(shí)現(xiàn)二叉樹的核心接口
public interface BinarySearchTreeInterface {
/**
*查找 key 對應(yīng)的 value
*/
Object get(int key);
/**
* 查找最小關(guān)鍵字對應(yīng)值
*/
Object min();
/**
* 查找最大關(guān)鍵字對應(yīng)值
*/
Object max();
/**
* 存儲關(guān)鍵字與對應(yīng)值
*/
void put(int key, Object value);
/**
* 查找關(guān)鍵字的后驅(qū)
*/
Object successor(int key);
/**
* 查找關(guān)鍵字的前驅(qū)
*/
Object predecessor(int key);
/**
* 根據(jù)關(guān)鍵字刪除
*/
Object delete(int key);
}?3.1 實(shí)現(xiàn)二叉搜索樹 - 獲取值 get(int key)
實(shí)現(xiàn)思路為：從根節(jié)點(diǎn)開始，先判斷當(dāng)前的節(jié)點(diǎn) p.key 與 key 進(jìn)行比較，若 p.key > key，則向左子樹下潛 p = p.left ；若 p.key < key ，則向右子樹下潛 p = p.right ；若 p.key == key ，則找到到了關(guān)鍵字，返回該節(jié)點(diǎn)的值 p.value 。按這樣的規(guī)則一直循環(huán)下去，直到 p == null 退出循環(huán)，則說明沒有找到對應(yīng)的節(jié)點(diǎn)，則返回 null 。
代碼如下：
@Override
public Object get(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p != null) {
if (p.key > key) {
p = p.left;
}else if (p.key < key) {
p = p.right;
}else {
return p.value;
}
}
return null;
}若 root 為 null ，則不需要再進(jìn)行下去了，直接結(jié)束。
3.2 實(shí)現(xiàn)二叉搜索樹 - 獲取最小的關(guān)鍵字 min(BinaryNode node)
實(shí)現(xiàn)思路：在某一個樹中，需要得到最小的關(guān)鍵字，由根據(jù)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，最小的關(guān)鍵字在數(shù)的最左邊，簡單來說：一直向左子樹遍歷下去，直到 p.left == null 時，則該 p 節(jié)點(diǎn)就是最小的關(guān)鍵字了。然后找到了最小的節(jié)點(diǎn)，返回該節(jié)點(diǎn)的值即可。
代碼如下：
非遞歸實(shí)現(xiàn)：
@Override
public Object min() {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p.left != null) {
p = p.left;
}
return p.value;
}
//重載了一個方法，帶參數(shù)的方法。
public Object min(BinaryNode node) {
if (node == null) {
return null;
}
BinaryNode p = node;
while (p.left != null) {
p = p.left;
}
return p.value;
}遞歸實(shí)現(xiàn)：
//使用遞歸實(shí)現(xiàn)找最小關(guān)鍵字
public Object minRecursion() {
return doMin(root);
}
private Object doMin(BinaryNode node) {
if (node == null) {
return null;
}
if (node.left == null) {
return node.value;
}
return doMin(node.left);
}3.3 實(shí)現(xiàn)二叉搜索樹 - 獲取最大的關(guān)鍵字 max(BinaryNode node)
實(shí)現(xiàn)思路為：在某一個樹中，需要得到最大的關(guān)鍵字，由根據(jù)數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，最大的關(guān)鍵字在數(shù)的最右邊，簡單來說：一直向右子樹遍歷下去，直到 p.right == null 時，則該 p 節(jié)點(diǎn)就是最大的關(guān)鍵字了。然后找到了最大的節(jié)點(diǎn)，返回該節(jié)點(diǎn)的值即可。
代碼如下：
非遞歸實(shí)現(xiàn)：
@Override
public Object max() {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p.right != null) {
p = p.right;
}
return p.value;
}
//重載了一個帶參數(shù)的方法
public Object max(BinaryNode node) {
if (node == null) {
return null;
}
BinaryNode p = node;
while (p.right != null) {
p = p.right;
}
return p.value;
}遞歸實(shí)現(xiàn)：
//使用遞歸實(shí)現(xiàn)找最大關(guān)鍵字
public Object maxRecursion() {
return doMax(root);
}
private Object doMax(BinaryNode node) {
if (node == null) {
return null;
}
if (node.right == null) {
return node.value;
}
return doMax(node.right);
}3.4 實(shí)現(xiàn)二叉搜索樹 - 增、更新 put( int key, Object value)
實(shí)現(xiàn)思路為：在二叉搜索樹中先試著查找是否存在與 key 對應(yīng)的節(jié)點(diǎn) p.key 。若找到了，則為更新該值 p.value = value 即可。若找不到，則需要新增該關(guān)鍵字節(jié)點(diǎn)。
具體來分析如何新增關(guān)鍵字，先定義 BinaryNode parent 、 BinaryNode p，p 指針在去比較 key 之前，先讓 parent 指向 p 。最后循環(huán)結(jié)束后， p == null ，對于 parent 來說，此時正指著 p 節(jié)點(diǎn)的雙親節(jié)點(diǎn)。 接著創(chuàng)建一個新的節(jié)點(diǎn)，BinaryNode newNode = new BinaryNode(key, value) ，則此時還需要考慮的是，該新的節(jié)點(diǎn)該連接到 parent 的左孩子還是右孩子 ？需要比較 parent.key 與 newNode.key 的大小即可，若 parent.key > newNode.key，則鏈接到 parent.left 處；若 prent.key < newNode.key ，則連接到 parent.right 處。
代碼如下：
@Override
public void put(int key, Object value) {
if (root == null) {
root = new BinaryNode(key,value);
return;
}
BinaryNode p = root;
BinaryNode parent = null;
while (p != null) {
parent = p;
if (p.key > key) {
p = p.left;
} else if (p.key < key) {
p = p.right;
}else {
p.value = value;
return;
}
}
//該樹沒有該關(guān)鍵字，因此需要新建節(jié)點(diǎn)對象
BinaryNode newNode = new BinaryNode(key,value);
if (newNode.key < parent.key) {
parent.left = newNode;
}else {
parent.right = newNode;
}
}3.5 實(shí)現(xiàn)二叉搜索樹 - 查找關(guān)鍵字的后驅(qū)節(jié)點(diǎn) successor(int key)
具體實(shí)現(xiàn)思路為：先遍歷找到該關(guān)鍵字的節(jié)點(diǎn)，若找不到，則返回 null ；若找到了，判斷以下的兩種情況，第一種情況：該節(jié)點(diǎn)有右子樹，則該關(guān)鍵字的后驅(qū)為右子樹的最小關(guān)鍵字；第二種情況：該節(jié)點(diǎn)沒有右子樹，則該關(guān)鍵字的后驅(qū)為從右向左而來的祖宗節(jié)點(diǎn)。最后返回該后驅(qū)節(jié)點(diǎn)的值
代碼如下：
@Override
public Object successor(int key) {
if (root == null) {
return null;
}
//先找到該關(guān)鍵字節(jié)點(diǎn)
BinaryNode p = root;
BinaryNode sParent = null;
while (p != null) {
if (p.key > key) {
sParent = p;
p = p.left;
} else if (p.key < key) {
p = p.right;
}else {
break;
}
}
//沒有找到關(guān)鍵字的情況
if (p == null) {
return null;
}
//情況一:該節(jié)點(diǎn)存在右子樹,則該后繼為右子樹的最小關(guān)鍵字
if (p.right != null) {
return min(p.right);
}
//情況二:該節(jié)點(diǎn)不存在右子樹，那么該后繼就需要到祖宗從右向左的節(jié)點(diǎn)
if (sParent == null) {
//可能不存在后繼節(jié)點(diǎn),比如最大關(guān)鍵字的節(jié)點(diǎn)就沒有后繼節(jié)點(diǎn)了
return null;
}
return sParent.value;
}3.6 實(shí)現(xiàn)二叉搜索樹 - 查找關(guān)鍵字的前驅(qū)節(jié)點(diǎn) predecessor(int key)
具體實(shí)現(xiàn)思路為：先對該二叉樹進(jìn)行遍歷尋找 key 的節(jié)點(diǎn)，若遍歷結(jié)束還沒找到，則返回 null ；若找到了，需要判斷以下兩種情況：
第一種情況：該節(jié)點(diǎn)有左子樹，則該前驅(qū)節(jié)點(diǎn)為該左子樹的最大關(guān)鍵字節(jié)點(diǎn)。
第二種情況：該節(jié)點(diǎn)沒有左子樹，則該前驅(qū)節(jié)點(diǎn)為從左向右而來的祖宗節(jié)點(diǎn)。
最后返回該前驅(qū)節(jié)點(diǎn)的值。
代碼如下：
@Override
public Object predecessor(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
BinaryNode sParent = null;
while (p != null) {
if (p.key > key) {
p = p.left;
} else if (p.key < key) {
sParent = p;
p = p.right;
}else {
break;
}
}
if (p == null) {
return null;
}
//情況一:存在左子樹，則該前任就為左子樹的最大關(guān)鍵字節(jié)點(diǎn)
if (p.left != null) {
return max(p.left);
}
//情況二:不存在左子樹，則該前任為從祖宗自左向右而來的節(jié)點(diǎn)
if (sParent == null) {
return null;
}
return sParent.value;
}3.7 實(shí)現(xiàn)二叉搜索樹 - 刪除關(guān)鍵字節(jié)點(diǎn) delete(int key)
具體實(shí)現(xiàn)思路為：先遍歷二叉樹，查找該關(guān)鍵字節(jié)點(diǎn)。若遍歷結(jié)束了還沒有找到，則返回 null ；若找到了，則需要以下四種情況：
第一種情況：找到該刪除的節(jié)點(diǎn)只有左子樹。則直接讓該左子樹 "托付" 給刪除節(jié)點(diǎn)的雙親節(jié)點(diǎn)，這就刪除了該節(jié)點(diǎn)了。至于左子樹是鏈接到雙親節(jié)點(diǎn)的左邊還有右邊這個問題，根據(jù)該數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，由該刪除節(jié)點(diǎn)來決定。若刪除的節(jié)點(diǎn)之前是鏈接該雙親節(jié)點(diǎn)的左邊，則左子樹也是鏈接到該雙親節(jié)點(diǎn)的左邊；若刪除的節(jié)點(diǎn)之前是鏈接該雙親節(jié)點(diǎn)的右邊，則左子樹也是鏈接到該雙親節(jié)點(diǎn)的右邊。
第二種情況：找到該刪除的節(jié)點(diǎn)只有右子樹。則直接讓該右子樹 "托付" 給刪除節(jié)點(diǎn)的雙親節(jié)點(diǎn)，這就刪除了該節(jié)點(diǎn)了。至于右子樹是鏈接到雙親節(jié)點(diǎn)的左邊還有右邊這個問題，根據(jù)該數(shù)據(jù)結(jié)構(gòu)的特點(diǎn)，由該刪除節(jié)點(diǎn)來決定。若刪除的節(jié)點(diǎn)之前是鏈接該雙親節(jié)點(diǎn)的左邊，則右子樹也是鏈接到該雙親節(jié)點(diǎn)的左邊；若刪除的節(jié)點(diǎn)之前是鏈接該雙親節(jié)點(diǎn)的右邊，則右子樹也是鏈接到該雙親節(jié)點(diǎn)的右邊。
第三種情況：找到該刪除節(jié)點(diǎn)都沒有左右子樹。該情況可以歸并到以上兩種情況的任意一種處理均可。
第四種情況：找到該刪除節(jié)點(diǎn)都有左右子樹。分兩步：第一步，先找后繼節(jié)點(diǎn)來替換刪除節(jié)點(diǎn)，找該后繼節(jié)點(diǎn)直接到刪除節(jié)點(diǎn)的右子樹中找最小的關(guān)鍵字節(jié)點(diǎn)即可。第二步，需要先將后繼節(jié)點(diǎn)的右子樹處理好，需要將該右子樹交給替換節(jié)點(diǎn)的雙親節(jié)點(diǎn)鏈接。還需要判斷兩種情況：第一種情況，若刪除節(jié)點(diǎn)與替換節(jié)點(diǎn)是緊挨著的，對替換節(jié)點(diǎn)的右子樹無需要求，只對左子樹重新賦值；若刪除節(jié)點(diǎn)與替換節(jié)點(diǎn)不是緊挨著的關(guān)系，對替換節(jié)點(diǎn)的左右子樹都要重新賦值。
代碼如下：
@Override
public Object delete(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
BinaryNode parent = null;
while (p != null) {
if (p.key > key) {
parent = p;
p = p.left;
} else if (p.key < key) {
parent = p;
p = p.right;
}else {
break;
}
}
//沒有找到該關(guān)鍵字的節(jié)點(diǎn)
if (p == null) {
return null;
}
//情況一、二、三:只有左子樹或者右子樹或者都沒有
if (p.right == null) {
shift(parent,p,p.left);
} else if (p.left == null) {
shift(parent,p,p.right);
}else {
//情況四:有左右子樹
//替換節(jié)點(diǎn)采用刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)
//先看被刪的節(jié)點(diǎn)與替換的節(jié)點(diǎn)是否為緊挨在一起
BinaryNode s = p.right;
BinaryNode sParent = p;
while (s.left != null) {
sParent = s;
s = s.left;
}
if (sParent != p) {
//說明沒有緊挨在一起，則需要將替換節(jié)點(diǎn)的右子樹進(jìn)行處理
shift(sParent,s,s.right);
s.right = p.right;
}
shift(parent,p,s);
s.left = p.left;
}
return p.value;
}
private void shift(BinaryNode parent, BinaryNode delete, BinaryNode next) {
if (parent == null) {
root = next;
} else if (parent.left == delete) {
parent.left = next;
}else if (parent.right == delete){
parent.right = next;
}
}為了方便，將刪除節(jié)點(diǎn)與替換節(jié)點(diǎn)之間的替換操作單獨(dú)成一個方法出來。
遞歸實(shí)現(xiàn)刪除關(guān)鍵字 key 節(jié)點(diǎn)，同理，也是細(xì)分為以上描述的四種情況。
代碼如下：
//使用遞歸實(shí)現(xiàn)刪除關(guān)鍵字節(jié)點(diǎn)
public BinaryNode deleteRecursion(BinaryNode node , int key) {
if (node == null) {
return null;
}
if (node.key > key) {
node.left = deleteRecursion(node.left,key);
return node;
} else if (node.key < key) {
node.right = deleteRecursion(node.right,key);
return node;
}else {
if (node.right == null) {
return node.left;
} else if (node.left == null) {
return node.right;
}else {
BinaryNode s = node.right;
while (s.left != null) {
s = s.left;
}
s.right = deleteRecursion(node.right,s.key);
s.left = node.left;
return s;
}
}
}3.8 實(shí)現(xiàn)二叉搜索樹 - 查找范圍小于關(guān)鍵字的節(jié)點(diǎn)值 less(int key)
具體實(shí)現(xiàn)思路為：利用中序遍歷，來遍歷每一個節(jié)點(diǎn)的 key ，若小于 key 的節(jié)點(diǎn)，直接放到數(shù)組容器中；若大于 key 的，可以直接退出循環(huán)。最后返回該數(shù)組容器即可。
代碼如下：
//找 < key 的所有 value
public List<Object> less(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
BinaryNode p = root;
Stack<BinaryNode> stack = new Stack<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key < key) {
result.add(pop.value);
}else {
break;
}
p = pop.right;
}
}
return result;
}3.9 實(shí)現(xiàn)二叉搜索樹 - 查找范圍大于關(guān)鍵字的節(jié)點(diǎn)值 greater(int key)
具體實(shí)現(xiàn)思路：利用中序遍歷，來遍歷每一個節(jié)點(diǎn)的 key ，若大于 key 的節(jié)點(diǎn)，直接放到數(shù)組容器中。
代碼如下：
//找 > key 的所有 value
public List<Object> greater(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
}
p = pop.right;
}
}
return result;
}該方法的改進(jìn)：遍歷方向進(jìn)行調(diào)整，先從右子樹開始，再訪問根節(jié)點(diǎn)，最后才到左子樹。因此只要小于 key 的關(guān)鍵字節(jié)點(diǎn)，直接退出循環(huán)。
代碼如下：
//改進(jìn)思路:遍歷方向進(jìn)行調(diào)整，先從右子樹開始，再訪問根節(jié)點(diǎn)，最后才到左子樹
public List<Object> greater1(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null ) {
stack.push(p);
p = p.right;
}else {
BinaryNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
}else {
break;
}
p = pop.left;
}
}
return result;
}4.0 實(shí)現(xiàn)二叉搜索樹 - 查找范圍大于 k1 且小于 k2 關(guān)鍵字的節(jié)點(diǎn)值 between(int k1, int k2)
實(shí)現(xiàn)思路跟以上的思路沒有什么區(qū)別，唯一需要注意的是，當(dāng)前節(jié)點(diǎn)的 key > k2 則可以退出循環(huán)了。
代碼如下：
//找到 >= k1 且 =< k2 的所有value
public List<Object> between(int k1, int k2) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while(p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key >= k1 && pop.key <= k2) {
result.add(pop.value);
} else if (pop.key > k2) {
break;
}
p = pop.right;
}
}
return result;
}5.0 實(shí)現(xiàn)二叉搜索樹核心方法的完整代碼
實(shí)現(xiàn)接口代碼：
import java.util.ArrayList;
import java.util.List;
import java.util.Stack;
public class BinaryTree implements BinarySearchTreeInterface{
BinaryNode root = null;
static class BinaryNode {
int key;
Object value;
BinaryNode left;
BinaryNode right;
public BinaryNode(int kty, Object value) {
this.key = kty;
this.value = value;
}
public BinaryNode(int key, Object value, BinaryNode left, BinaryNode right) {
this.key = key;
this.value = value;
this.left = left;
this.right = right;
}
}
@Override
public Object get(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p != null) {
if (p.key > key) {
p = p.left;
}else if (p.key < key) {
p = p.right;
}else {
return p.value;
}
}
return null;
}
@Override
public Object min() {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p.left != null) {
p = p.left;
}
return p.value;
}
public Object min(BinaryNode node) {
if (node == null) {
return null;
}
BinaryNode p = node;
while (p.left != null) {
p = p.left;
}
return p.value;
}
//使用遞歸實(shí)現(xiàn)找最小關(guān)鍵字
public Object minRecursion() {
return doMin(root);
}
private Object doMin(BinaryNode node) {
if (node == null) {
return null;
}
if (node.left == null) {
return node.value;
}
return doMin(node.left);
}
@Override
public Object max() {
if (root == null) {
return null;
}
BinaryNode p = root;
while(p.right != null) {
p = p.right;
}
return p.value;
}
public Object max(BinaryNode node) {
if (node == null) {
return null;
}
BinaryNode p = node;
while (p.right != null) {
p = p.right;
}
return p.value;
}
//使用遞歸實(shí)現(xiàn)找最大關(guān)鍵字
public Object maxRecursion() {
return doMax(root);
}
private Object doMax(BinaryNode node) {
if (node == null) {
return null;
}
if (node.right == null) {
return node.value;
}
return doMax(node.right);
}
@Override
public void put(int key, Object value) {
if (root == null) {
root = new BinaryNode(key,value);
return;
}
BinaryNode p = root;
BinaryNode parent = null;
while (p != null) {
parent = p;
if (p.key > key) {
p = p.left;
} else if (p.key < key) {
p = p.right;
}else {
p.value = value;
return;
}
}
//該樹沒有該關(guān)鍵字，因此需要新建節(jié)點(diǎn)對象
BinaryNode newNode = new BinaryNode(key,value);
if (newNode.key < parent.key) {
parent.left = newNode;
}else {
parent.right = newNode;
}
}
@Override
public Object successor(int key) {
if (root == null) {
return null;
}
//先找到該關(guān)鍵字節(jié)點(diǎn)
BinaryNode p = root;
BinaryNode sParent = null;
while (p != null) {
if (p.key > key) {
sParent = p;
p = p.left;
} else if (p.key < key) {
p = p.right;
}else {
break;
}
}
//沒有找到關(guān)鍵字的情況
if (p == null) {
return null;
}
//情況一:該節(jié)點(diǎn)存在右子樹,則該后繼為右子樹的最小關(guān)鍵字
if (p.right != null) {
return min(p.right);
}
//情況二:該節(jié)點(diǎn)不存在右子樹，那么該后繼就需要到祖宗從右向左的節(jié)點(diǎn)
if (sParent == null) {
//可能不存在后繼節(jié)點(diǎn),比如最大關(guān)鍵字的節(jié)點(diǎn)就沒有后繼節(jié)點(diǎn)了
return null;
}
return sParent.value;
}
@Override
public Object predecessor(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
BinaryNode sParent = null;
while (p != null) {
if (p.key > key) {
p = p.left;
} else if (p.key < key) {
sParent = p;
p = p.right;
}else {
break;
}
}
if (p == null) {
return null;
}
//情況一:存在左子樹，則該前任就為左子樹的最大關(guān)鍵字節(jié)點(diǎn)
if (p.left != null) {
return max(p.left);
}
//情況二:不存在左子樹，則該前任為從祖宗自左向右而來的節(jié)點(diǎn)
if (sParent == null) {
return null;
}
return sParent.value;
}
@Override
public Object delete(int key) {
if (root == null) {
return null;
}
BinaryNode p = root;
BinaryNode parent = null;
while (p != null) {
if (p.key > key) {
parent = p;
p = p.left;
} else if (p.key < key) {
parent = p;
p = p.right;
}else {
break;
}
}
//沒有找到該關(guān)鍵字的節(jié)點(diǎn)
if (p == null) {
return null;
}
//情況一、二、三:只有左子樹或者右子樹或者都沒有
if (p.right == null) {
shift(parent,p,p.left);
} else if (p.left == null) {
shift(parent,p,p.right);
}else {
//情況四:有左右子樹
//替換節(jié)點(diǎn)采用刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)
//先看被刪的節(jié)點(diǎn)與替換的節(jié)點(diǎn)是否為緊挨在一起
BinaryNode s = p.right;
BinaryNode sParent = p;
while (s.left != null) {
sParent = s;
s = s.left;
}
if (sParent != p) {
//說明沒有緊挨在一起，則需要將替換節(jié)點(diǎn)的右子樹進(jìn)行處理
shift(sParent,s,s.right);
s.right = p.right;
}
shift(parent,p,s);
s.left = p.left;
}
return p.value;
}
private void shift(BinaryNode parent, BinaryNode delete, BinaryNode next) {
if (parent == null) {
root = next;
} else if (parent.left == delete) {
parent.left = next;
}else if (parent.right == delete){
parent.right = next;
}
}
//使用遞歸實(shí)現(xiàn)刪除關(guān)鍵字節(jié)點(diǎn)
public BinaryNode deleteRecursion(BinaryNode node , int key) {
if (node == null) {
return null;
}
if (node.key > key) {
node.left = deleteRecursion(node.left,key);
return node;
} else if (node.key < key) {
node.right = deleteRecursion(node.right,key);
return node;
}else {
if (node.right == null) {
return node.left;
} else if (node.left == null) {
return node.right;
}else {
BinaryNode s = node.right;
while (s.left != null) {
s = s.left;
}
s.right = deleteRecursion(node.right,s.key);
s.left = node.left;
return s;
}
}
}
//找 < key 的所有 value
public List<Object> less(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
BinaryNode p = root;
Stack<BinaryNode> stack = new Stack<>();
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key < key) {
result.add(pop.value);
}else {
break;
}
p = pop.right;
}
}
return result;
}
//找 > key 的所有 value
public List<Object> greater(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
}
p = pop.right;
}
}
return result;
}
//改進(jìn)思路:遍歷方向進(jìn)行調(diào)整，先從右子樹開始，再訪問根節(jié)點(diǎn)，最后才到左子樹
public List<Object> greater1(int key) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while (p != null || !stack.isEmpty()) {
if (p != null ) {
stack.push(p);
p = p.right;
}else {
BinaryNode pop = stack.pop();
if (pop.key > key) {
result.add(pop.value);
}else {
break;
}
p = pop.left;
}
}
return result;
}
//找到 >= k1 且 =< k2 的所有value
public List<Object> between(int k1, int k2) {
if (root == null) {
return null;
}
ArrayList<Object> result = new ArrayList<>();
Stack<BinaryNode> stack = new Stack<>();
BinaryNode p = root;
while(p != null || !stack.isEmpty()) {
if (p != null) {
stack.push(p);
p = p.left;
}else {
BinaryNode pop = stack.pop();
if (pop.key >= k1 && pop.key <= k2) {
result.add(pop.value);
} else if (pop.key > k2) {
break;
}
p = pop.right;
}
}
return result;
}
}總結(jié)
到此這篇關(guān)于Java數(shù)據(jù)結(jié)構(gòu)篇之實(shí)現(xiàn)二叉搜索樹的核心方法的文章就介紹到這了,更多相關(guān)Java實(shí)現(xiàn)二叉搜索樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
- Java數(shù)據(jù)結(jié)構(gòu)之紅黑樹的實(shí)現(xiàn)方法和原理詳解
- Java數(shù)據(jù)結(jié)構(gòu)中七種排序算法實(shí)現(xiàn)詳解
- Java數(shù)據(jù)結(jié)構(gòu)中關(guān)于AVL樹的實(shí)現(xiàn)方法詳解
- Java數(shù)據(jù)結(jié)構(gòu)和算法之鏈表詳解
- Java數(shù)據(jù)結(jié)構(gòu)與算法之二分查找詳解
- Java數(shù)據(jù)結(jié)構(gòu)中的HashMap和HashSet詳解
- Java常見的數(shù)據(jù)結(jié)構(gòu)之棧和隊(duì)列詳解
- java手動實(shí)現(xiàn)常見數(shù)據(jù)結(jié)構(gòu)的示例代碼
相關(guān)文章
Java實(shí)現(xiàn)復(fù)原IP地址的方法
這篇文章主要介紹了Java實(shí)現(xiàn)復(fù)原IP地址的方法，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)學(xué)習(xí)吧2020-02-02
SpringIOC容器Bean的作用域及生命周期實(shí)例
這篇文章主要為大家介紹了SpringIOC容器Bean的作用域及生命周期實(shí)例，有需要的朋友可以借鑒參考下，希望能夠有所幫助，祝大家多多進(jìn)步，早日升職加薪2022-05-05
最新IDEA?2022基于JVM極致優(yōu)化?IDEA啟動速度的方法
這篇文章主要介紹了IDEA?2022最新版?基于?JVM極致優(yōu)化?IDEA?啟動速度,需要的朋友可以參考下2022-08-08
Springboot如何設(shè)置過濾器及重復(fù)讀取request里的body
這篇文章主要介紹了Springboot如何設(shè)置過濾器及重復(fù)讀取request里的body，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2022-03-03
使用dom4j實(shí)現(xiàn)xml轉(zhuǎn)map與xml轉(zhuǎn)json字符串
這篇文章主要為大家詳細(xì)介紹了如何使用dom4j實(shí)現(xiàn)xml轉(zhuǎn)map與xml轉(zhuǎn)json字符串功能,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以了解下2024-11-11
spring定時任務(wù)(scheduler)的串行、并行執(zhí)行實(shí)現(xiàn)解析
這篇文章主要介紹了spring定時任務(wù)(scheduler)的串行、并行執(zhí)行實(shí)現(xiàn)解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-09-09
Springboot工具類FileCopyUtils使用教程
這篇文章主要介紹了Springboot內(nèi)置的工具類之FileCopyUtils的使用，文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2022-12-12
2022?最新?IntelliJ?IDEA?詳細(xì)配置步驟演示(推薦)
作為一名開發(fā)人員，第一肯定是選擇一款趁手的開發(fā)利器，本人使用?Java?偏多，這里推薦使用?IntelliJ?IDEA,?俗稱神級開發(fā)工具，具體的安裝過程就不過多贅述了，有需要了解的朋友可以參考下本文2022-09-09
這篇文章主要介紹了Spring 自動裝配的二義性實(shí)例解析,文中通過示例代碼介紹的非常詳細(xì)，對大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價值,需要的朋友可以參考下2019-11-11
IDEA導(dǎo)入外部項(xiàng)目報(bào)Error:java: 無效的目標(biāo)發(fā)行版: 11的解決方法
這篇文章主要介紹了IDEA導(dǎo)入外部項(xiàng)目報(bào)Error:java: 無效的目標(biāo)發(fā)行版: 11,本文給大家介紹的非常詳細(xì)，對大家的學(xué)習(xí)或工作具有一定的參考借鑒價值，需要的朋友可以參考下2020-09-09