定義
二叉搜索樹(Binary Search Tree,BST),也稱為二叉排序樹或二叉查找樹。
相較于普通的二叉樹勇劣，非空的二叉搜索樹有如下性質(zhì)：
- 非空左子樹的所有鍵值小于其根結(jié)點(diǎn)的鍵值随夸；
- 非空右子樹的所有鍵值大于其根結(jié)點(diǎn)的鍵值默刚；
- 左右子樹均為二叉搜索樹；
- 樹中沒有鍵值相等的結(jié)點(diǎn)逃魄。
可以看到，二叉搜索樹的性質(zhì)很鮮明澜搅，這也使得二叉樹也有了實(shí)際意義伍俘。
二叉搜索樹的常用操作
對(duì)于二叉搜索樹，除了常規(guī)的4種遍歷之外勉躺，還有如下一些關(guān)鍵的操作值得我們?nèi)リP(guān)注癌瘾。
二叉樹的存儲(chǔ)結(jié)構(gòu)實(shí)現(xiàn)
對(duì)于二叉樹，我們還是習(xí)慣的選擇采用鏈?zhǔn)酱鎯?chǔ)結(jié)構(gòu)實(shí)現(xiàn)饵溅。
二叉樹結(jié)點(diǎn)定義
二叉搜索樹最大的特點(diǎn)妨退，就是他的元素是可以比較大小的。這一點(diǎn)是需要注意的地方。
/**
* Created by engineer on 2017/10/26.
* <p>
* 二叉搜索樹樹結(jié)點(diǎn)定義
*/
public class TreeNode<T extends Comparable<T>> {
// 數(shù)據(jù)域
private T data;
// 左子樹
public TreeNode<T> leftChild;
// 右子樹
public TreeNode<T> rightChild;
public TreeNode(T data) {
this(null, data, null);
}
public TreeNode(TreeNode leftChild, T data, TreeNode rightChild) {
this.leftChild = leftChild;
this.data = data;
this.rightChild = rightChild;
}
public T getData() {
return data;
}
public TreeNode<T> getLeftChild() {
return leftChild;
}
public TreeNode<T> getRightChild() {
return rightChild;
}
public void setData(T data) {
this.data = data;
}
}
二叉搜索樹插入
有了根節(jié)點(diǎn)咬荷，我們就可以根據(jù)二叉樹的性質(zhì)冠句，從根節(jié)點(diǎn)出發(fā)，構(gòu)建出一顆二叉樹幸乒。
/**
* 樹中插入元素
*
* @param value
*/
void insert(T value) {
if (value == null) {
return;
}
root = insert(root, value);
}
private TreeNode<T> insert(TreeNode<T> node, T value) {
if (node == null) {
// 樹為空,則創(chuàng)建根節(jié)點(diǎn)
return new TreeNode<>(value);
} else {
if (compare(node, value) < 0) { // 插入值比根節(jié)點(diǎn)小懦底，在左子樹繼續(xù)創(chuàng)建二叉搜索樹
node.leftChild = insert(node.getLeftChild(), value);
} else if (compare(node, value) > 0) { // 插入值比根節(jié)點(diǎn)大，在右子樹繼續(xù)創(chuàng)建二叉搜索樹
node.rightChild = insert(node.getRightChild(), value);
}
}
return node;
}
private int compare(TreeNode<T> node, T value) {
return value.compareTo(node.getData());
}
根據(jù)二叉搜索樹的特性罕扎，我們很容易使用遞歸實(shí)現(xiàn)二叉樹的插入操作聚唐；總的來說，就是每次插入一個(gè)結(jié)點(diǎn)腔召，從根節(jié)點(diǎn)出發(fā)作比較杆查，小的就往左子樹插，大的就往右子樹插臀蛛。這和二叉搜索樹的定義時(shí)完全一致的亲桦。
我們可以簡(jiǎn)單測(cè)試一下，這個(gè)insert方法的正確性掺栅。
測(cè)試二叉搜索樹插入操作
public class BinarySearchTreeTest {
private static Integer[] arrays = new Integer[]{10, 8, 3, 12, 9, 4, 5, 7, 1,11, 17};
public static void main(String[] args) {
BinarySearchTree<Integer> mSearchTree = new BinarySearchTree<>();
for (Integer data : arrays) {
mSearchTree.insert(data);
}
// 打印二叉樹的三種遍歷順序
mSearchTree.printTree();
}
}
關(guān)于樹的遍歷已在上文中詳細(xì)分析烙肺，此處不再做深入探討
這里定義了一個(gè)隨機(jī)數(shù)組，這個(gè)將這個(gè)數(shù)組的按序插入到樹中氧卧，并按照樹的三種遍歷結(jié)構(gòu)打印樹桃笙。按照這個(gè)數(shù)組我們將構(gòu)建出如下所示的一顆二叉搜索樹：
看一下程序輸出的遍歷結(jié)果。
前序遍歷：10 8 3 1 4 5 7 9 12 11 17
中序遍歷：1 3 4 5 7 8 9 10 11 12 17
后序遍歷：1 7 5 4 3 9 8 11 17 12 10
可以看到沙绝，遍歷結(jié)果和我們畫出來二叉樹是一致的搏明，因此可以驗(yàn)證插入方法是正確的。
查找
通過插入操作闪檬，我們已經(jīng)實(shí)現(xiàn)了一顆二叉搜索樹星著，下面就來看看如何從樹中查找元素。
- 查找最大值與最小值
根據(jù)二叉搜索樹的特點(diǎn)粗悯，我們知道在一顆二叉搜索樹上虚循，最小的值一定在最最左邊的結(jié)點(diǎn)上，而最大值一定在最最右邊的結(jié)點(diǎn)上样傍。因此横缔，查找二叉樹最值就變得非常容易了。
/**
* 查找最大值
*
* @return
*/
public T findMax() {
if (isEmpty()) return null;
return findMax(root);
}
/**
* 從特定結(jié)點(diǎn)開始尋找最大值
*
* @param node
* @return
*/
private T findMax(TreeNode<T> node) {
TreeNode<T> temp = node;
while (temp.getRightChild() != null) {
temp = temp.getRightChild();
}
return temp.getData();
}
/**
* 查找最小值
*
* @return
*/
public T findMin() {
if (isEmpty()) return null;
return findMin(root);
}
/**
* 從特定結(jié)點(diǎn)開始尋找最小值
*
* @param node
* @return
*/
private T findMin(TreeNode<T> node) {
TreeNode<T> temp = node;
while (temp.getLeftChild() != null) {
temp = temp.getLeftChild();
}
return temp.getData();
}
可以看到衫哥，算法實(shí)現(xiàn)非常簡(jiǎn)單茎刚，就是不斷后移結(jié)點(diǎn)找到?jīng)]有子樹的結(jié)點(diǎn)，就是最邊界位置的結(jié)點(diǎn)了撤逢。
- 查找特定值
在二叉搜索樹中膛锭，怎樣快速找到一個(gè)值為特定元素的結(jié)點(diǎn)呢粮坞？想想我們是怎樣實(shí)現(xiàn)結(jié)點(diǎn)插入的？這個(gè)問題就很簡(jiǎn)單了初狰。
遞歸實(shí)現(xiàn)莫杈，查找特定結(jié)點(diǎn)
**
/**
* find 特定值 遞歸實(shí)現(xiàn)
*
* @param value
* @return
*/
public TreeNode<T> find(T value) {
if (isEmpty()) {
return null;
} else {
return find(root, value);
}
}
private TreeNode<T> find(TreeNode<T> node, T value) {
if (node == null) {
// 當(dāng)查找一個(gè)不在樹中元素時(shí)，拋出異常
throw new RuntimeException("the value must not in the tree");
}
if (compare(node, value) < 0) {
// 小于根節(jié)點(diǎn)時(shí)跷究，從去左子樹找
return find(node.getLeftChild(), value);
} else if (compare(node, value) > 0) {
// 大于根節(jié)點(diǎn)時(shí)姓迅，從右子樹找
return find(node.getRightChild(), value);
} else {
// 剛好等于，找到了
return node;
// 剩下還有一種情況俊马，就是不等于丁存，也就是所查找的元素不在樹中
}
}
查找的實(shí)現(xiàn)思路，總體上和插入是一致的柴我；無非就是做不同的操作解寝；這里需要注意的是，為了程序的健壯性艘儒，我們還得考慮如果查找的元素不在樹中這種情況聋伦。
迭代實(shí)現(xiàn)，查找特定值
有了前面查找最大值界睁、最小值的經(jīng)驗(yàn)觉增，我們也可以考慮使用迭代算法實(shí)現(xiàn)查找指定元素的算法。
/**
* 查找特定值-非遞歸實(shí)現(xiàn)
*
* @param value
* @return 結(jié)點(diǎn)
*/
public TreeNode<T> findIter(T value) {
TreeNode<T> current = root;
while (current != null) {
if (compare(current, value) < 0) {
current = current.getLeftChild();
} else if (compare(current, value) > 0) {
current = current.getRightChild();
} else {
return current;
}
}
// current為null,說明所查找的元素不在tree里
return null;
}
這里同樣測(cè)試一下翻斟，查找方法的正確性：
System.out.printf("\nfind value %d in mSearchTree \n", 12);
TreeNode mTreeNode = mSearchTree.find(12);
TreeNode mTreeNode_1 = mSearchTree.findIter(12);
System.out.println("遞歸實(shí)現(xiàn)結(jié)點(diǎn) = :" + mTreeNode + ", value=" + mTreeNode.getData());
System.out.println("非遞歸實(shí)現(xiàn)結(jié)點(diǎn)= :" + mTreeNode_1 + ", value=" + mTreeNode_1.getData());
System.out.println("\nfind the max value in mSearchTree = " + mSearchTree.findMax());
System.out.println("find the min value in mSearchTree = " + mSearchTree.findMin());
輸出：
find value 12 in mSearchTree
遞歸實(shí)現(xiàn)結(jié)點(diǎn) = :com.avaj.datastruct.tree.bst.TreeNode@4b67cf4d, value=12
非遞歸實(shí)現(xiàn)結(jié)點(diǎn)= :com.avaj.datastruct.tree.bst.TreeNode@4b67cf4d, value=12
find the max value in mSearchTree = 17
find the min value in mSearchTree = 1
我們分別用遞歸和迭代兩種方式去查找 12逾礁，可以看到兩次找到是同一個(gè)對(duì)象，這個(gè)對(duì)象的值為12访惜；找到的最大值和最小值也是正確的嘹履；因此查找功能的實(shí)現(xiàn)是正確的。
刪除結(jié)點(diǎn)
從二叉搜索樹中债热，刪除一個(gè)結(jié)點(diǎn)可以算是最復(fù)雜的操作了砾嫉，主要是因?yàn)樗獎(jiǎng)h除的結(jié)點(diǎn)，所處的位置被刪除后窒篱，依然需要保持整棵樹依然為二叉樹焕刮，因此需要就不同的情況就像分析。
就拿我們上面創(chuàng)建的這顆二叉樹來說墙杯，如果要?jiǎng)h除的結(jié)點(diǎn)是1,7,11,17 這樣的葉子結(jié)點(diǎn)济锄，就很容易了；讓其父結(jié)點(diǎn)指向?yàn)閚ull即可霍转；而如果是4,5 這樣包含一顆子樹的結(jié)點(diǎn)，換個(gè)角度來說一汽，這其實(shí)就是單向鏈表避消，從單向鏈表中間位置刪除一個(gè)結(jié)點(diǎn)也比較容易低滩；最麻煩的就是如果要?jiǎng)h除的結(jié)點(diǎn)是10,8,3,12 這類結(jié)點(diǎn)包含左右子樹，我們就需要從左子樹中找一個(gè)最大值岩喷，或者是右子樹中的最小值來替代這個(gè)值恕沫。總結(jié)一下刪除結(jié)點(diǎn)的操作：
- 葉子結(jié)點(diǎn)：直接刪除纱意，其父結(jié)點(diǎn)指向null
- 包含一個(gè)孩子的結(jié)點(diǎn) ：父結(jié)點(diǎn)指向要?jiǎng)h除結(jié)點(diǎn)的自結(jié)點(diǎn)（相當(dāng)于鏈表中間刪除一個(gè)元素）婶溯；
- 包含左右子樹的結(jié)點(diǎn)：右子樹最小值或左子樹最大值替換此結(jié)點(diǎn)
結(jié)合以上分析，得出從二叉搜索樹中刪除結(jié)點(diǎn)的實(shí)現(xiàn)偷霉。
/**
* 從樹中刪除值為value 的特定結(jié)點(diǎn)
*
* @param value
*/
public void delete(T value) {
if (value == null || isEmpty()) {
return;
}
root = delete(root, value);
}
private TreeNode<T> delete(TreeNode<T> node, T value) {
// 結(jié)點(diǎn)為空迄委，要出刪除的元素不在樹中
if (node == null) {
return node;
}
if (compare(node, value) < 0) { // 去左子樹刪除
node.leftChild = delete(node.getLeftChild(), value);
} else if (compare(node, value) > 0) { // 去右子樹刪除
node.rightChild = delete(node.getRightChild(), value);
} else { // 要?jiǎng)h除的就是當(dāng)前結(jié)點(diǎn)
if (node.getLeftChild() != null && node.getRightChild() != null) {// 被刪除的結(jié)點(diǎn)，包含左右子樹
T temp = findMin(node.getRightChild()); // 得到右子樹的最小值
node.setData(temp); //右子樹最小值替換當(dāng)前結(jié)點(diǎn)
node.rightChild = delete(node.getRightChild(), temp); // 從右子樹刪除這個(gè)最小值的結(jié)點(diǎn)
} else {// 被刪除的結(jié)點(diǎn)类少，包含一個(gè)子樹或沒有子樹
if (node.getLeftChild() != null) {
node = node.getLeftChild();
} else {
node = node.getRightChild();
}
}
}
return node;
}
這里選擇使用右子樹的最小值替換叙身，是因?yàn)閯h除這個(gè)最小值的結(jié)點(diǎn)會(huì)比較容易，因?yàn)樗欢ㄊ遣粫?huì)是一個(gè)包含左右子樹的結(jié)點(diǎn)硫狞。
同樣信轿，這里測(cè)試一下刪除結(jié)點(diǎn)的功能：
// 刪除只帶一個(gè)子樹的結(jié)點(diǎn)
mSearchTree.delete(4);
mSearchTree.printTree();
System.out.println();
// 刪除帶左右子樹的根節(jié)點(diǎn)
mSearchTree.delete(10);
mSearchTree.printTree();
輸出：
前序遍歷：10 8 3 1 5 7 9 12 11 17
中序遍歷：1 3 5 7 8 9 10 11 12 17
后序遍歷：1 7 5 3 9 8 11 17 12 10
前序遍歷：11 8 3 1 5 7 9 12 17
中序遍歷：1 3 5 7 8 9 11 12 17
后序遍歷：1 7 5 3 9 8 17 12 11
通過和我們一開始畫出來的樹相比較，發(fā)現(xiàn)是對(duì)應(yīng)的残吩。
二叉搜索樹的高度
最后财忽，再來看看如何計(jì)算一顆二叉搜素樹的度。
public int getTreeHeight() {
if (isEmpty()) {
return 0;
}
return getTreeHeight(root);
}
private int getTreeHeight(TreeNode<T> node) {
if (node == null) {
return 0;
}
int leftHeight = getTreeHeight(node.getLeftChild());
int rightHeight = getTreeHeight(node.getRightChild());
int max = leftHeight > rightHeight ? leftHeight : rightHeight;
// 得到左右子樹中較大的返回.
return max + 1;
}
順便來算一算泣侮，到最后我們創(chuàng)建的樹即彪，經(jīng)過插入刪除操作高度變成了多少。
System.out.println("\n\nTree's height =" + mSearchTree.getTreeHeight());
輸出：
Tree's height =5
可以看到旁瘫，由于結(jié)點(diǎn)4被刪除祖凫，樹由原來的6層變成了5層，結(jié)果是正確的酬凳！
好了惠况，二叉搜索樹的分析就是這些了！文中所有源碼地址.
