Java實(shí)現(xiàn)二分查找樹(shù)及其相關(guān)操作
二分查找樹(shù)（Binary Search Tree）的基本操作有搜索、求最大值、求最小值、求前驅(qū)、求后繼、插入及刪除。
對(duì)二分查找樹(shù)的進(jìn)行基本操作所花費(fèi)的時(shí)間與樹(shù)的高度成比例。例如有n個(gè)節(jié)點(diǎn)的完全二叉樹(shù)，對(duì)它進(jìn)行的基本操作的時(shí)間復(fù)雜度為O(logn)。然而，如果樹(shù)是一個(gè)有n個(gè)節(jié)點(diǎn)的線性的鏈，則在這種情況下的時(shí)間復(fù)雜度為O(n)。
1、什么是二分查找樹(shù)
二分查找樹(shù)是一種有組織的二叉樹(shù)。我們可以通過(guò)鏈接節(jié)點(diǎn)表示這樣一棵樹(shù)。每個(gè)節(jié)點(diǎn)包含鍵（key），數(shù)據(jù)（data），左子節(jié)點(diǎn)（left），右子節(jié)點(diǎn)（right），父節(jié)點(diǎn)（parent）這五種屬性。
如果一個(gè)節(jié)點(diǎn)沒(méi)有父節(jié)點(diǎn)或某個(gè)子結(jié)點(diǎn)，則其對(duì)應(yīng)的屬性的值為null。
創(chuàng)建一個(gè)Node.java文件，用如下代碼表示節(jié)點(diǎn)：
public class Node {
public int key;
public int data;
public Node left;
public Node right;
public Node parent;
public Node(){}
public Node(int key) {
this.key = key;
}
}
創(chuàng)建一個(gè)BinarySearchTree.java文件，用如下代碼表示二分查找樹(shù)：
public class BinarySearchTree {
public Node root;
}
接下來(lái)，會(huì)逐步補(bǔ)充代碼。
對(duì)于存儲(chǔ)在二分查找樹(shù)中的鍵，必須滿足下面這個(gè)條件（二分查找樹(shù)特點(diǎn)）：
對(duì)于二叉樹(shù)中的任一節(jié)點(diǎn)n，如果left是n左子樹(shù)中的任何一個(gè)節(jié)點(diǎn)，有l(wèi)eft.key <= n.key；如果right是n右子樹(shù)中的任一節(jié)點(diǎn)，則有n.key<=right.key。
如果我們中序遍歷二分查找樹(shù)，能升序打印出所有的鍵（key）。
可在BinarySearchTree.java文件中加上如下代碼實(shí)現(xiàn)中序遍歷：
private void innerWalk(Node node) {
if(node != null) {
innerWalk(node.left);
System.out.print(node.key + " ");
innerWalk(node.right);
}
}
public void innerWalk() {
this.innerWalk(this.root);
System.out.println();
}
2、查詢二分查找樹(shù)
2.1、搜索
在二分查找樹(shù)中搜索鍵為key的結(jié)點(diǎn)，如果找到，則返回該結(jié)點(diǎn)，否則，返回null?？衫枚植檎覙?shù)的特性來(lái)查找。
可在BinarySearchTree.java文件中加上如下代碼實(shí)現(xiàn)搜索：
public Node search(int key) {
Node pointer = this.root;
while (pointer != null && pointer.key != key) {
pointer = key < pointer.key ? pointer.left : pointer.right;
}
return pointer;
}
2.2、最小值與最大值
求鍵最小的節(jié)點(diǎn)，可根據(jù)二叉樹(shù)的特點(diǎn)，從根結(jié)點(diǎn)開(kāi)始，遍歷跟蹤其左子節(jié)點(diǎn)，直到最后一個(gè)。
可在Node.java文件中加上如下代碼實(shí)現(xiàn)：
public Node minimum() {
Node pointer = this;
while(pointer.left != null){
pointer = pointer.left;
}
return pointer;
}
在BinarySearchTree.java文件中加上如下代碼：
public Node minimum() {
return this.root.minimum();
}
求鍵最大的節(jié)點(diǎn)，可根據(jù)二叉樹(shù)的特點(diǎn)，從根結(jié)點(diǎn)開(kāi)始，遍歷跟蹤其右子節(jié)點(diǎn)，直到最后一個(gè)。
可在Node.java文件中加上如下代碼實(shí)現(xiàn)：
public Node maximum() {
Node pointer = this;
while(pointer.right != null) {
pointer = pointer.right;
}
return pointer;
}
在BinarySearchTree.java文件中加上如下代碼：
public Node minimum() {
return this.root.maximum();
}
2.3、前驅(qū)與后繼
給定一個(gè)二分查找樹(shù)中的節(jié)點(diǎn)，有時(shí)我們需要發(fā)現(xiàn)它在樹(shù)中所有結(jié)點(diǎn)按鍵升序排序的情況下的直接后繼（后面第一個(gè)）。
如果樹(shù)中所有的鍵是不同的，結(jié)點(diǎn)n的直接后繼是大于n.key的最小結(jié)點(diǎn)。
如果該結(jié)點(diǎn)有右節(jié)點(diǎn)，則其直接后繼是其右子樹(shù)鍵最小的那個(gè)結(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)還是右子節(jié)點(diǎn)，以此類推。
如果找不到，則返回null。
可在Node.java文件中加上如下實(shí)現(xiàn)代碼：
public Node successor() {
Node pointer = this;
if (pointer.right != null)
return pointer.right.minimum();
Node parentPointer = pointer.parent;
while (parentPointer != null && parentPointer.right == pointer) {
pointer = parentPointer;
parentPointer = parentPointer.parent;
}
return pointer;
}
一個(gè)節(jié)點(diǎn)的直接前繼是指樹(shù)中所有結(jié)點(diǎn)按鍵升序排序的情況下，該節(jié)點(diǎn)的前面第一個(gè)。求直接前繼的與求直接后繼是對(duì)稱的。
可在Node.java文件中加上如下實(shí)現(xiàn)代碼：
public Node predecessor() {
Node pointer = this;
if (pointer.left != null)
return pointer.left.maximum();
Node parentPointer = pointer.parent;
while (parentPointer != null && parentPointer.left == pointer) {
pointer = parentPointer;
parentPointer = parentPointer.parent;
}
return pointer;
}
3、插入與刪除
插入與刪除會(huì)導(dǎo)致二分查找樹(shù)發(fā)生改變，但必須保持其特點(diǎn)。
3.1、插入
在樹(shù)中找到一個(gè)鍵（key）最接近要插入結(jié)點(diǎn)鍵（key）的結(jié)點(diǎn)，且有可以插入的位置，然后插入合適的位置。
可在BinarySearchTree.java文件中加上如下實(shí)現(xiàn)代碼：
public void insert(Node node) {
Node pointer = this.root;
Node parentPointer = null;
while (pointer != null) {
parentPointer = pointer;
pointer = node.key < pointer.key ? pointer.left : pointer.right;
}
node.parent = parentPointer;
if (parentPointer == null)
this.root = node;
else if (node.key < parentPointer.key) {
parentPointer.left = node;
} else {
parentPointer.right = node;
}
}
3.2、刪除
刪除節(jié)點(diǎn)后，我門(mén)要保持二分查找樹(shù)的特點(diǎn)。
如果要?jiǎng)h除節(jié)點(diǎn)沒(méi)有任何子節(jié)點(diǎn)，直接可以刪除它，不用做任何處理。
如果要?jiǎng)h除節(jié)點(diǎn)只有一個(gè)左子樹(shù)，可以用左子樹(shù)的根節(jié)點(diǎn)代替要?jiǎng)h除節(jié)點(diǎn)，也可以用左子樹(shù)中鍵（key）最大的節(jié)點(diǎn)來(lái)代替要?jiǎng)h除節(jié)點(diǎn)。
如果要?jiǎng)h除結(jié)點(diǎn)只有一個(gè)右子樹(shù)，可以用右子樹(shù)的根節(jié)點(diǎn)代替要?jiǎng)h除節(jié)點(diǎn)，也可以用右子樹(shù)中鍵（key）最小的結(jié)點(diǎn)來(lái)代替要?jiǎng)h除結(jié)點(diǎn)。
如果要?jiǎng)h除結(jié)點(diǎn)既有左子樹(shù)，又有右子樹(shù)，可以用左子樹(shù)中鍵（key）最大的結(jié)點(diǎn)代替要?jiǎng)h除結(jié)點(diǎn)，也可以用右子樹(shù)中鍵最小的結(jié)點(diǎn)代替要?jiǎng)h除結(jié)點(diǎn)。
假設(shè)要從二分查找樹(shù)tree中刪除節(jié)點(diǎn)node，一種刪除方法的具體步驟如下：
- 如果node沒(méi)有左子節(jié)點(diǎn)，然后我們可以用node的右子節(jié)node.right點(diǎn)代替node，node.right可能是或可能不是null。
- 如果node只有左子節(jié)點(diǎn)node.left，則我們用node.left代替node。
- 如果node有左子節(jié)點(diǎn)node.left和右子節(jié)點(diǎn)node.right。我么要發(fā)現(xiàn)node的直接后繼s（node右子樹(shù)中鍵最小的結(jié)點(diǎn)，它沒(méi)有左子節(jié)點(diǎn)），s在node右子樹(shù)中，然后用s代替node。這里要考慮下面兩種情況：
如果s是node的右子節(jié)點(diǎn)，可以用s代替node。
否則，用s的右子節(jié)點(diǎn)代替s，然后再用s代替node。
由于我們需要在二分查找樹(shù)中替換子樹(shù)的方法，可以先寫(xiě)一個(gè)替換子樹(shù)的方法。
可在BinarySearchTree.java文件中加上如下實(shí)現(xiàn)代碼：
/**
* 用子樹(shù)node2代替代替子樹(shù)node1
*
* @param node1
* @param node2
*/
private void transplant(Node node1, Node node2) {
if (node1.parent == null) {
this.root = node2;
} else if (node1.parent.left == node1) {
node1.parent.left = node2;
} else {
node1.parent.right = node2;
}
if (node2 != null)
node2.parent = node1.parent;
node1.parent = null;
}
接下來(lái)解釋刪除節(jié)點(diǎn)操作的代碼實(shí)現(xiàn)。
可在BinarySearchTree.java文件中加上如下實(shí)現(xiàn)代碼：
public void delete(Node node) {
if (node.left == null) {
this.transplant(node, node.right);
} else if (node.right == null) {
this.transplant(node, node.left);
} else {
Node successor = node.successor();
if (successor.parent != node) {
this.transplant(successor, successor.right);
successor.right = node.right;
successor.right.parent = successor;
}
this.transplant(node, successor);
successor.left = node.left;
successor.left.parent = successor;
}
}
4、完整代碼
Node.java文件
public class Node {
public int key;
public int data;
public Node left;
public Node right;
public Node parent;
public Node() {
}
public Node(int key) {
this.key = key;
}
public Node minimum() {
Node pointer = this;
while (pointer.left != null)
pointer = pointer.left;
return pointer;
}
public Node maximum() {
Node pointer = this;
while (pointer.right != null)
pointer = pointer.right;
return pointer;
}
public Node successor() {
Node pointer = this;
if (pointer.right != null)
return pointer.right.minimum();
Node parentPointer = pointer.parent;
while (parentPointer != null && parentPointer.right == pointer) {
pointer = parentPointer;
parentPointer = parentPointer.parent;
}
return pointer;
}
public Node predecessor() {
Node pointer = this;
if (pointer.left != null)
return pointer.left.maximum();
Node parentPointer = pointer.parent;
while (parentPointer != null && parentPointer.left == pointer) {
pointer = parentPointer;
parentPointer = parentPointer.parent;
}
return pointer;
}
}
BinarySearchTree.java文件
public class BinarySearchTree {
public Node root;
private void innerWalk(Node node) {
if (node != null) {
innerWalk(node.left);
System.out.print(node.key + " ");
innerWalk(node.right);
}
}
public void innerWalk() {
this.innerWalk(this.root);
System.out.println();
}
public Node search(int key) {
Node pointer = this.root;
while (pointer != null && pointer.key != key) {
pointer = key < pointer.key ? pointer.left : pointer.right;
}
return pointer;
}
public Node minimum() {
return this.root.minimum();
}
public Node maximum() {
return this.root.maximum();
}
public void insert(Node node) {
Node pointer = this.root;
Node parentPointer = null;
while (pointer != null) {
parentPointer = pointer;
pointer = node.key < pointer.key ? pointer.left : pointer.right;
}
node.parent = parentPointer;
if (parentPointer == null)
this.root = node;
else if (node.key < parentPointer.key) {
parentPointer.left = node;
} else {
parentPointer.right = node;
}
}
/**
* 用子樹(shù)node2代替代替子樹(shù)node1
*
* @param node1
* @param node2
*/
private void transplant(Node node1, Node node2) {
if (node1.parent == null) {
this.root = node2;
} else if (node1.parent.left == node1) {
node1.parent.left = node2;
} else {
node1.parent.right = node2;
}
if (node2 != null)
node2.parent = node1.parent;
node1.parent = null;
}
public void delete(Node node) {
if (node.left == null) {
this.transplant(node, node.right);
} else if (node.right == null) {
this.transplant(node, node.left);
} else {
Node successor = node.successor();
if (successor.parent != node) {
this.transplant(successor, successor.right);
successor.right = node.right;
successor.right.parent = successor;
}
this.transplant(node, successor);
successor.left = node.left;
successor.left.parent = successor;
}
}
}
5、演示
演示代碼：
public class Test01 {
public static void main(String[] args) {
Node n1 = new Node(1);
Node n2 = new Node(2);
Node n3 = new Node(3);
Node n4 = new Node(4);
Node n5 = new Node(5);
BinarySearchTree bst = new BinarySearchTree();
bst.insert(n3);
bst.insert(n4);
bst.insert(n2);
bst.insert(n1);
bst.insert(n5);
System.out.println("bst.minimum().key: " + bst.minimum().key);
System.out.println("bst.maximum().key: " + bst.maximum().key);
System.out.println("n3.successor().key: " + n3.successor().key);
System.out.println("n3.predecessor().key: " + n3.predecessor().key);
System.out.println("bst.search(4).key: " + bst.search(4).key);
System.out.print("tree: ");
bst.innerWalk();
System.out.print("delete n3: ");
bst.delete(n3);
bst.innerWalk();
System.out.print("delete n2: ");
bst.delete(n2);
bst.innerWalk();
System.out.print("delete n1: ");
bst.delete(n1);
bst.innerWalk();
System.out.print("delete n4: ");
bst.delete(n4);
bst.innerWalk();
System.out.print("delete n5: ");
bst.delete(n5);
bst.innerWalk();
}
}
結(jié)果：
bst.minimum().key: 1
bst.maximum().key: 5
n3.successor().key: 4
n3.predecessor().key: 2
bst.search(4).key: 4
tree: 1 2 3 4 5
delete n3: 1 2 4 5
delete n2: 1 4 5
delete n1: 4 5
delete n4: 5
delete n5:
到此這篇關(guān)于Java實(shí)現(xiàn)二分查找樹(shù)及其相關(guān)操作的文章就介紹到這了,更多相關(guān)java二分查找樹(shù)內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
springboot-mybatis/JPA流式查詢的多種實(shí)現(xiàn)方式
這篇文章主要介紹了springboot-mybatis/JPA流式查詢,本文給大家分享三種方式，每種方式結(jié)合示例代碼給大家講解的非常詳細(xì)，需要的朋友可以參考下2022-12-12
這篇文章主要介紹了PowerMockito的基本使用，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07
這篇文章主要介紹了MyBatis的 config.xml標(biāo)簽的相關(guān)資料,非常不錯(cuò)，具有參考借鑒價(jià)值，需要的朋友可以參考下2016-12-12
偵聽(tīng)消息隊(duì)列的Message Listener類示例詳解
Spring AMQP 是基于 Spring 框架的AMQP消息解決方案,提供模板化的發(fā)送和接收消息的抽象層,提供基于消息驅(qū)動(dòng)的 POJO的消息監(jiān)聽(tīng)等,簡(jiǎn)化了我們對(duì)于RabbitMQ相關(guān)程序的開(kāi)發(fā),本文給大家介紹偵聽(tīng)消息隊(duì)列的Message Listener類,感興趣的朋友一起看看吧2023-12-12
Spring?Cloud?Gateway編碼實(shí)現(xiàn)任意地址跳轉(zhuǎn)的示例
本文主要介紹了Spring?Cloud?Gateway編碼實(shí)現(xiàn)任意地址跳轉(zhuǎn)的示例，文中通過(guò)示例代碼介紹的非常詳細(xì)，具有一定的參考價(jià)值，感興趣的小伙伴們可以參考一下2021-12-12
使用自定義Json注解實(shí)現(xiàn)輸出日志字段脫敏
這篇文章主要介紹了使用自定義Json注解實(shí)現(xiàn)輸出日志字段脫敏，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-12-12
Java Quartz觸發(fā)器CronTriggerBean配置用法詳解
這篇文章主要介紹了Java Quartz觸發(fā)器CronTriggerBean配置用法詳解,本篇文章通過(guò)簡(jiǎn)要的案例,講解了該項(xiàng)技術(shù)的了解與使用,以下就是詳細(xì)內(nèi)容,需要的朋友可以參考下2021-08-08
springboot項(xiàng)目攔截前端請(qǐng)求中的特殊字符串(解決方案)
springboot項(xiàng)目中,需要對(duì)前端請(qǐng)求數(shù)據(jù)進(jìn)行過(guò)濾,攔截特殊字符,本文通過(guò)實(shí)例代碼給大家分享完美解決方案,感興趣的朋友一起看看吧2023-10-10
這篇文章主要介紹了Maven發(fā)布Jar包中文亂碼解決方法，文中通過(guò)示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧2020-03-03
解決spring boot網(wǎng)關(guān)gateway導(dǎo)致的坑,無(wú)法下載文件問(wèn)題
這篇文章主要介紹了解決spring boot網(wǎng)關(guān)gateway導(dǎo)致的坑，無(wú)法下載文件的問(wèn)題，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。如有錯(cuò)誤或未考慮完全的地方，望不吝賜教2021-07-07