二叉查找樹的定義：
二叉查找樹（Binary Search Tree）浩峡，是指一棵空樹或者具有下列性質(zhì)的二叉樹
- 若任意節(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)
*/
class BinaryTreeNode {
public int value;
public BinaryTreeNode left;
public BinaryTreeNode right;
public BinaryTreeNode(int value) {
this.value = value;
}
public BinaryTreeNode(int value, BinaryTreeNode left, BinaryTreeNode right) {
this.value = value;
this.left = left;
this.right = right;
}
//...
}
package com.hm.structure;
/**
* Created by dmw on 2018/12/27.
* Desc: 二叉查找樹
* 二叉查找樹的定義：
* 二叉查找樹（英語：Binary Search Tree）恼策，是指一棵空樹或者具有下列性質(zhì)的二叉樹
* 1. 若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有節(jié)點(diǎn)的值均小于它的根節(jié)點(diǎn)的值拼窥；
* 2. 若任意節(jié)點(diǎn)的右子樹不空戏蔑，則右子樹上所有節(jié)點(diǎn)的值均大于它的根節(jié)點(diǎn)的值；
* 3. 任意節(jié)點(diǎn)的左鲁纠、右子樹也分別為二叉查找樹；
* 4. 沒有鍵值相等的節(jié)點(diǎn)鳍寂。
* <p>
*/
public class BinarySearchTree {
public BinaryTreeNode root;
public BinarySearchTree() {
}
public BinarySearchTree(BinaryTreeNode root) {
this.root = root;
}
public BinaryTreeNode insert(int key) {
BinaryTreeNode newNode = new BinaryTreeNode(key);
BinaryTreeNode current = root;
BinaryTreeNode parent;
//如果根節(jié)點(diǎn)為空
if (current == null) {
root = newNode;
return newNode;
}
while (true) {
parent = current;
if (key < current.value) {
current = current.left;
if (current == null) {
parent.left = newNode;
return newNode;
}
} else {
current = current.right;
if (current == null) {
parent.right = newNode;
return newNode;
}
}
}
}
public BinaryTreeNode search(int key) {
BinaryTreeNode current = root;
while (current != null && key != current.value) {
if (key < current.value) {
current = current.left;
} else {
current = current.right;
}
}
return current;
}
public BinaryTreeNode delete(int key) {
BinaryTreeNode parent = root;
BinaryTreeNode current = root;
//標(biāo)記當(dāng)前節(jié)點(diǎn)是父節(jié)點(diǎn)的左節(jié)點(diǎn)還是右節(jié)點(diǎn)
boolean isLeftChild = false;
// 找到刪除節(jié)點(diǎn)及是否在左子樹
while (current.value != key) {
parent = current;
if (current.value > key) {
isLeftChild = true;
current = current.left;
} else {
isLeftChild = false;
current = current.right;
}
//如果要刪除的節(jié)點(diǎn)為null改含，直接返回
if (current == null) {
return current;
}
}
// 如果刪除節(jié)點(diǎn)左節(jié)點(diǎn)為空 , 右節(jié)點(diǎn)也為空
if (current.left == null && current.right == null) {
if (current == root) {
root = null;
}
if (isLeftChild) {
parent.left = null;
} else {
parent.right = null;
}
} else if (current.right == null) {// 如果要刪除的節(jié)點(diǎn)只有左節(jié)點(diǎn)
if (current == root) {
root = root.left;
} else if (isLeftChild) {
parent.left = current.left;
} else {
parent.right = current.left;
}
} else if (current.left == null) {// 如果要刪除的節(jié)點(diǎn)只有右節(jié)點(diǎn)
if (current == root) {
root = current.right;
} else if (isLeftChild) {
parent.left = current.right;
} else {
parent.right = current.right;
}
} else {
// 如果刪除節(jié)點(diǎn)左右子節(jié)點(diǎn)都不為空,則先找到待刪除節(jié)點(diǎn)的中序遍歷的后繼節(jié)點(diǎn)，
//用該后繼節(jié)點(diǎn)的值替換待刪除的節(jié)點(diǎn)的值迄汛，然后刪除后繼節(jié)點(diǎn)捍壤。
BinaryTreeNode successor = getDeleteSuccessor(current);
if (current == root) {
root = successor;
} else if (isLeftChild) {
parent.left = successor;
} else {
parent.right = successor;
}
//將要刪除節(jié)點(diǎn)的左子節(jié)點(diǎn)賦值給后繼節(jié)點(diǎn)的左子節(jié)點(diǎn)
successor.left = current.left;
}
//將刪除節(jié)點(diǎn)的子節(jié)點(diǎn)都置為null
current.left = null;
current.right = null;
return current;
}
public void printTree(BinaryTreeNode root) {
if (root != null) {
printTree(root.left);
System.out.print("" + root.value + " ");
printTree(root.right);
}
}
/**
* 獲取刪除節(jié)點(diǎn)的后繼者，刪除節(jié)點(diǎn)的后繼者是在其右子樹中最小的節(jié)點(diǎn)
*
* @param deleteNode
* @return
*/
private BinaryTreeNode getDeleteSuccessor(BinaryTreeNode deleteNode) {
//要刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)
BinaryTreeNode successor = null;
BinaryTreeNode successorParent = null;
BinaryTreeNode current = deleteNode.right;
while (current != null) {
successorParent = successor;
successor = current;
current = current.left;
}
if (successor != deleteNode.right) {
successorParent.left = successor.right;
successor.right = deleteNode.right;
}
return successor;
}
public static void main(String[] args) {
//BinaryTreeNode root = new BinaryTreeNode(8);
BinarySearchTree treeTest = new BinarySearchTree();
treeTest.insert(8);
treeTest.insert(6);
treeTest.insert(10);
treeTest.insert(5);
treeTest.insert(7);
treeTest.insert(9);
treeTest.insert(20);
treeTest.insert(12);
treeTest.insert(14);
treeTest.insert(13);
treeTest.printTree(treeTest.root);
/*BinaryTreeNode deletedNode = treeTest.delete(10);
System.out.println(deletedNode.value);*/
}
}
插入和刪除都比較簡單鞍爱，下面我們演示一個刪除節(jié)點(diǎn)的操作
如下所示的一個二叉樹
BinarySearchTree0
我們想要刪除value為10的節(jié)點(diǎn)
BinarySearchTree1
因?yàn)橐獎h除節(jié)點(diǎn)左右子節(jié)點(diǎn)都不為空,則先找到待刪除節(jié)點(diǎn)的中序遍歷的后繼節(jié)點(diǎn)鹃觉，要刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)是在其右子樹中最小的節(jié)點(diǎn)。就是圖中value為12的節(jié)點(diǎn)睹逃。
/**
* 獲取刪除節(jié)點(diǎn)的后繼者盗扇，刪除節(jié)點(diǎn)的后繼者是在其右子樹中最小的節(jié)點(diǎn)
*
* @param deleteNode
* @return
*/
private BinaryTreeNode getDeleteSuccessor(BinaryTreeNode deleteNode) {
//要刪除節(jié)點(diǎn)的后繼節(jié)點(diǎn)
BinaryTreeNode successor = null;
BinaryTreeNode successorParent = null;
BinaryTreeNode current = deleteNode.right;
while (current != null) {
successorParent = successor;
successor = current;
current = current.left;
}
//找到后繼節(jié)點(diǎn)是12，不是要刪除節(jié)點(diǎn)的右子節(jié)點(diǎn)
if (successor != deleteNode.right) {
//步驟1
successorParent.left = successor.right;
//步驟2
successor.right = deleteNode.right;
}
return successor;
}
BinarySearchTree2
-
步驟1后圖譜如下
BinarySearchTree3 -
步驟2后圖譜如下
BinarySearchTree4
最后的調(diào)整階段
if (current == root) {
root = successor;
} else if (isLeftChild) {
parent.left = successor;
} else {
//進(jìn)入此分支
parent.right = successor;
}
//將要刪除節(jié)點(diǎn)的左子節(jié)點(diǎn)賦值給后繼節(jié)點(diǎn)的左子節(jié)點(diǎn)
successor.left = current.left;
調(diào)整后就刪除成功了沉填，結(jié)果如下圖所示
BinarySearchTree5
參考鏈接：
圖解：二叉搜索樹算法
