手把手教你用java實現(xiàn)二分查找樹及其相關操作
點擊上方藍色字體，選擇“標星公眾號”
優(yōu)質文章，第一時間送達
二分查找樹（Binary Search Tree）的基本操作有搜索、求最大值、求最小值、求前驅、求后繼、插入及刪除。
對二分查找樹的進行基本操作所花費的時間與樹的高度成比例。例如有n個節(jié)點的完全二叉樹，對它進行的基本操作的時間復雜度為O(logn)。然而，如果樹是一個有n個節(jié)點的線性的鏈，則在這種情況下的時間復雜度為O(n)。
1、什么是二分查找樹
二分查找樹是一種有組織的二叉樹。我們可以通過鏈接節(jié)點表示這樣一棵樹。每個節(jié)點包含鍵（key），數(shù)據(jù)（data），左子節(jié)點（left），右子節(jié)點（right），父節(jié)點（parent）這五種屬性。
如果一個節(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的結點，如果找到，則返回該結點，否則，返回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é)點，直到最后一個。
可在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é)點，直到最后一個。
可在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、前驅與后繼
給定一個二分查找樹中的節(jié)點，有時我們需要發(fā)現(xiàn)它在樹中所有結點按鍵升序排序的情況下的直接后繼（后面第一個）。
如果樹中所有的鍵是不同的，結點n的直接后繼是大于n.key的最小結點。
如果該結點有右節(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é)點的前面第一個。求直接前驅的與求直接后繼是對稱的。
可在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）最接近要插入結點鍵（key）的結點，且有可以插入的位置，然后插入合適的位置。
可在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é)點，也可以用右子樹中鍵（key）最小的結點來代替要刪除結點。
如果要刪除結點既有左子樹，又有右子樹，可以用左子樹中鍵（key）最大的結點代替要刪除結點，也可以用右子樹中鍵最小的結點代替要刪除結點。
假設要從二分查找樹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é)點），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();
}
}
結果：
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:
作者 | 胡不慌
來源 | cnblogs.com/hubuhuang/p/15061017.html
