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