Java實現(xiàn)二分查找樹及其相關(guān)操作
二分查找樹（Binary Search Tree）的基本操作有搜索、求最大值、求最小值、求前驅(qū)、求后繼、插入及刪除。
對二分查找樹的進行基本操作所花費的時間與樹的高度成比例。例如有n個節(jié)點的完全二叉樹，對它進行的基本操作的時間復雜度為O(logn)。然而，如果樹是一個有n個節(jié)點的線性的鏈，則在這種情況下的時間復雜度為O(n)。
1、什么是二分查找樹
二分查找樹是一種有組織的二叉樹。我們可以通過鏈接節(jié)點表示這樣一棵樹。每個節(jié)點包含鍵（key），數(shù)據(jù)（data），左子節(jié)點（left），右子節(jié)點（right），父節(jié)點（parent）這五種屬性。
如果一個節(jié)點沒有父節(jié)點或某個子結(jié)點，則其對應的屬性的值為null。
創(chuàng)建一個Node.java文件，用如下代碼表示節(jié)點：
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)建一個BinarySearchTree.java文件，用如下代碼表示二分查找樹：
public class BinarySearchTree {
public Node root;
}
接下來，會逐步補充代碼。
對于存儲在二分查找樹中的鍵，必須滿足下面這個條件（二分查找樹特點）：
對于二叉樹中的任一節(jié)點n，如果left是n左子樹中的任何一個節(jié)點，有l(wèi)eft.key <= n.key；如果right是n右子樹中的任一節(jié)點，則有n.key<=right.key。
如果我們中序遍歷二分查找樹，能升序打印出所有的鍵（key）。
可在BinarySearchTree.java文件中加上如下代碼實現(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、查詢二分查找樹
2.1、搜索
在二分查找樹中搜索鍵為key的結(jié)點，如果找到，則返回該結(jié)點，否則，返回null。可利用二分查找樹的特性來查找。
可在BinarySearchTree.java文件中加上如下代碼實現(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é)點，可根據(jù)二叉樹的特點，從根結(jié)點開始，遍歷跟蹤其左子節(jié)點，直到最后一個。
可在Node.java文件中加上如下代碼實現(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é)點，可根據(jù)二叉樹的特點，從根結(jié)點開始，遍歷跟蹤其右子節(jié)點，直到最后一個。
可在Node.java文件中加上如下代碼實現(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ū)與后繼
給定一個二分查找樹中的節(jié)點，有時我們需要發(fā)現(xiàn)它在樹中所有結(jié)點按鍵升序排序的情況下的直接后繼（后面第一個）。
如果樹中所有的鍵是不同的，結(jié)點n的直接后繼是大于n.key的最小結(jié)點。
如果該結(jié)點有右節(jié)點，則其直接后繼是其右子樹鍵最小的那個結(jié)點。如果該結(jié)點則判斷該結(jié)點是其父節(jié)點的左子節(jié)點還是其右子節(jié)點。
如果是左子節(jié)點，則返回其父節(jié)點。如果是右子節(jié)點，判斷其父節(jié)點的其父節(jié)點的父節(jié)點的左子節(jié)點還是右子節(jié)點，以此類推。
如果找不到，則返回null。
可在Node.java文件中加上如下實現(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;
}
一個節(jié)點的直接前繼是指樹中所有結(jié)點按鍵升序排序的情況下，該節(jié)點的前面第一個。求直接前繼的與求直接后繼是對稱的。
可在Node.java文件中加上如下實現(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、插入與刪除
插入與刪除會導致二分查找樹發(fā)生改變，但必須保持其特點。
3.1、插入
在樹中找到一個鍵（key）最接近要插入結(jié)點鍵（key）的結(jié)點，且有可以插入的位置，然后插入合適的位置。
可在BinarySearchTree.java文件中加上如下實現(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é)點后，我門要保持二分查找樹的特點。
如果要刪除節(jié)點沒有任何子節(jié)點，直接可以刪除它，不用做任何處理。
如果要刪除節(jié)點只有一個左子樹，可以用左子樹的根節(jié)點代替要刪除節(jié)點，也可以用左子樹中鍵（key）最大的節(jié)點來代替要刪除節(jié)點。
如果要刪除結(jié)點只有一個右子樹，可以用右子樹的根節(jié)點代替要刪除節(jié)點，也可以用右子樹中鍵（key）最小的結(jié)點來代替要刪除結(jié)點。
如果要刪除結(jié)點既有左子樹，又有右子樹，可以用左子樹中鍵（key）最大的結(jié)點代替要刪除結(jié)點，也可以用右子樹中鍵最小的結(jié)點代替要刪除結(jié)點。
假設要從二分查找樹tree中刪除節(jié)點node，一種刪除方法的具體步驟如下：
- 如果node沒有左子節(jié)點，然后我們可以用node的右子節(jié)node.right點代替node，node.right可能是或可能不是null。
- 如果node只有左子節(jié)點node.left，則我們用node.left代替node。
- 如果node有左子節(jié)點node.left和右子節(jié)點node.right。我么要發(fā)現(xiàn)node的直接后繼s（node右子樹中鍵最小的結(jié)點，它沒有左子節(jié)點），s在node右子樹中，然后用s代替node。這里要考慮下面兩種情況：
如果s是node的右子節(jié)點，可以用s代替node。
否則，用s的右子節(jié)點代替s，然后再用s代替node。
由于我們需要在二分查找樹中替換子樹的方法，可以先寫一個替換子樹的方法。
可在BinarySearchTree.java文件中加上如下實現(xiàn)代碼：
/**
* 用子樹node2代替代替子樹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;
}
接下來解釋刪除節(jié)點操作的代碼實現(xiàn)。
可在BinarySearchTree.java文件中加上如下實現(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;
}
}
/**
* 用子樹node2代替代替子樹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實現(xiàn)二分查找樹及其相關(guān)操作的文章就介紹到這了,更多相關(guān)java二分查找樹內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！
相關(guān)文章
Java Volatile應用單例模式實現(xiàn)過程解析
這篇文章主要介紹了Java Volatile應用單例模式實現(xiàn)過程解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-11-11
SpringBoot整合Mybatis Plus實現(xiàn)基本CRUD的示例代碼
Mybatis Plus是在Mybatis的基礎上的增強，使得我們對一些基本的CRUD使用起來更方便，本文主要介紹了SpringBoot整合Mybatis Plus實現(xiàn)基本CRUD的示例代碼，具有一定的參考價值，感興趣的可以了解一下2023-05-05
Java編寫時間工具類ZTDateTimeUtil的示例代碼
這篇文章主要為大家詳細介紹了如何利用Java編寫時間工具類ZTDateTimeUtil,文中的示例代碼講解詳細,有需要的小伙伴可以跟隨小編一起學習一下2023-11-11
有些用戶有定制化需求,需要添加新的模塊功能,因此需要平臺主體功能迭代的同時,非主體功能和定制化功能插件化,本文給大家介紹maven模塊化開發(fā)部署實現(xiàn)方案,感興趣的朋友一起看看吧2024-01-01
SpringBoot 如何根據(jù)不同profile選擇不同配置
這篇文章主要介紹了SpringBoot 如何根據(jù)不同profile選擇不同配置的操作方式，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
這篇文章主要介紹了Java Lock接口實現(xiàn)原理及實例解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-04-04
這篇文章主要為大家詳細介紹了java實現(xiàn)簡易外賣訂餐系統(tǒng)，文中示例代碼介紹的非常詳細，具有一定的參考價值，感興趣的小伙伴們可以參考一下2021-10-10
Java的Exception異常機制,為什么會突然聊到異常？其實不是突然,而是我已經(jīng)準備了很久,但苦于沒有好的例子來講解,從表象到底層實現(xiàn),今天就帶大家詳細了解Exception異常,需要的朋友可以參考下2021-05-05
這篇文章主要介紹了java中求高精度除法,要求保留N位小數(shù)的實現(xiàn)，具有很好的參考價值，希望對大家有所幫助。如有錯誤或未考慮完全的地方，望不吝賜教2021-08-08
這篇文章主要為大家詳細介紹了Java中字符串的基本操作，例如遍歷、統(tǒng)計次數(shù)，拼接和反轉(zhuǎn)等以及String的常用方法，感興趣的可以了解一下2022-08-08