1 概念
又稱二叉查找樹，簡稱BST。具有以下性質的二叉樹：
（1） 若左子樹非空，則左子樹上所有結點值均小于根結點的值
（2） 若右子樹非空，則右子樹上所有結點值均大于根結點的值
（3） 左，右子樹本身也分别是一棵二叉排序樹
也是一個遞歸的資料結構。下圖是一個二叉排序樹。
對其進行中序周遊得到一個遞增的有序序列，如上圖的中序序列為2,4,5,6,7,8,9,10,11,14。
2 二叉排序樹的插入
二叉排序樹是一種動态的集合，插入結點的過程為，結點值小于根結點值，插入到左子樹中，若大于根結點值，則插入到右子樹中。插入的新結點一定是某個葉結點。
/**
* 在二叉排序樹node中插入一個值為info的結點
* @param node 二叉排序樹
* @param info 待插入結點值
* @return
*/
public Node insert(Node node, Integer info){
if(node == null){
node = new Node();
node.data = info;
}
if(info < node.data){
node.lchild = insert(node.lchild, info);
} else if(info > node.data){
node.rchild = insert(node.rchild, info);
} else { }
return node;
} 3 二叉排序樹的查找
從根結點開始，若給定值等于根結點值，則查找成功；若小于根結點值，在左子樹中查找，否則在右子樹中查找。可分為遞歸和非遞歸實作。
3.1 遞歸實作
/**
* 二叉排序樹，查找，遞歸實作
* @param root
* @param inte
* @return -1 不存在 1 存在
*/
public int searchRecur(Node root, Integer inte){
if(root!= null){
if(inte == root.data ){
return 1;
} else if(inte < root.data){
return searchRecur(root.lchild, inte);
} else if(inte > root.data){
return searchRecur(root.rchild, inte);
}
}
return -1;
} 3.2 非遞歸實作
/**
* 查找, 非遞歸實作
* @return -1 不能存在 1 存在
*/
public int search(Node root, Integer inte){
while(root != null && inte != root.data){
if(inte < root.data){
root = root.lchild;
} else {
root = root.rchild;
}
}
return root == null ? -1 : 1;
} 4 二叉排序樹的構造
依次輸入資料元素，插入到合适的位置上，具體的過程是，每讀入一個元素，建立一個新結點，若新結點值小于根結點值，則插入到左子樹中，否則插入到右子樹中。
public class BST {
Node root;
int n=1; // 結點總數
private class Node{
Integer data;
Node lchild, rchild;
}
public BST(){
build(); // 遞歸構造
System.out.println("根結點：" + root.data);
btDepth();
}
/**
* 構造一棵二叉排序樹
*/
public void build(){
// Integer[] ins = new Integer[] { 8, 4, 9, 2, 7, 5, 6 };
Integer[] ins = new Integer[] { 8, 4, 2, 7, 5, 6, 16, 10, 9, 14, 15, 11, 12};
root = new Node();
root.data = ins[0];
for (int i = 1; i < ins.length; i++) {
insert(root, ins[i]);
n++;
}
}
} 5 二叉排序樹的删除
删除一個結點時，必須保證二叉排序樹的性質不會丢失。删除操作的實作過程按3種情況來處理：
（1）若删除的結點 n 是葉子結點，則直接删除，不會破壞二叉排序樹性質；
（2）若删除的結點 n 隻有一棵左子樹或者右子樹，則使用左或右子女替換；
（3）若删除的結點 n 左右子樹均不空，則令n的直接後繼（或直接前驅）替代n，然後删除這個直接後繼（或前驅）。
/**
* 先找到該結點及其雙親結點，然後根據規則删除
* @param root 根節點
* @param del 待删除結點值
* @return -1結點不存在 1删除成功
*/
public int delete(Node root, Integer del){
Node pre = null; // 待删除結點的雙親結點
/*
* 首先找到該結點
*/
while(root != null && del != root.data){
pre = root;
if(del < root.data){
root = root.lchild;
} else {
root = root.rchild;
}
}
if(root == null){ // 若不存在 直接傳回
return -1;
}
delete(root, pre);
return 1;
}
/**
* 删除結點有三種情況
* <ul>
* <li> 若删除的結點 n 是葉子結點，則直接删除；
* <li> 若删除的結點 n 隻有一棵左子樹或者右子樹，則使用左或右子女替換；
* <li> 若删除的結點 n 左右子樹均不空，則令n的直接後繼（或直接前驅）替代n，然後删除這個直接後繼（或前驅）
* <p> 這裡的直接前驅和後繼是針對中序周遊的順序而言
* <ul/>
* @param node 待删除結點
* @param pre 其雙親結點
*/
private void delete(Node node, Node pre) {
Node tmp = null;
if(node.lchild == null && node.rchild == null){ // 葉子結點
tmp = null;
} else if (node.lchild == null) { // 左孩子為空，直接用右孩子替代
tmp = node.rchild;
} else if (node.rchild == null) { // 右孩子為空，直接用左孩子替代
tmp = node.lchild;
} else { // 左右子樹均不為空, 使用中序周遊的直接後繼替代
Node preNode = null// 右子樹中序周遊的第一個結點的雙親結點
,lnode = node.rchild; // 查找其右子樹 中序周遊的第一個結點，其沒有左孩子
while(lnode.lchild != null){
preNode = lnode;
lnode = lnode.lchild;
}
node.data = lnode.data; // 交換值
preNode.lchild = lnode.rchild; // 直接删除
tmp = node;
}
if(pre.lchild == node){
pre.lchild = tmp;
} else {
pre.rchild = tmp;
}
} 6 二叉排序樹的查找效率分析
對于高度為H的二叉排序樹，其插入和删除的運作時間都是O(H)。但在最壞的情況下，即構造二叉排序樹的輸入序列是有序的，就會形成一個傾斜的單枝樹，此時二叉排序樹性能顯著變壞，樹的高度也增加為元素個數N。
分析之前了解一下平均查找長度的概念。
為确定記錄在查找表中的位置，與給定值進行比較的關鍵字的個數期望值稱為查找算法在查找成功時的平均查找長度（ASL）。對于含有n個元素的查找表，查找成功的平均查找長度為：
其中Pi為查找表中第i個元素的機率，Ci為找到第i個元素已經比較過的次數。
在查找表中找不到待查元素，但是找到待查元素應該在表中存在的位置的平均查找次數稱為查找不成功的平均查找長度。
其中元素旁邊的數字為查找成功時，比較的次數。
在等機率的情況下，圖2（a）的查找成功的平均查找長度為（機率乘以關鍵字所在層數之和）：
ASLa = (1+2+2+3+3+3+3+4+4+4)/10 = 2.9
而圖2（b）的查找成功的平均查找長度為
ASLb=(1+2+3+4+5+6+7+8+9+10)/10=5.5
查找失敗的平均長度：圖a中那些虛線框的元素表示不存在的結點，即是查找失敗的點，其查找路徑為從根節點到其父節點的結點序列，是以查找失敗的平均長度為：
ASLa=(5*3+6*4)/11=3.5
由上可知，二叉排序樹查找算法的平均查找長度，主要取決于樹的高度，與二叉樹的形态有關。若二叉排序樹是一個隻有右（左）孩子的單枝樹（類似于有序單連結清單），其平均查找長度和單連結清單相同，為O(n)；若左右子樹的高度差不超過1，即是平衡二叉樹，其平均查找長度為O(log2n)。
二叉排序樹與二分查找相似，就平均性能而言，它倆差不多，但二分查找的判定樹唯一，而二叉排序樹不唯一，不同的輸入順序，可能得到不同的二叉排序樹。如上圖。
針對維護表的有序性，二叉排序樹無需移動結點，隻需修改指針完成插入和删除，平均執行時間為O(log2n)。二分查找的對象是有序順序表，插入和删除代價為O(n)。是以，若是靜态查找表，宜用順序表存儲結構，用二分查找；若是動态查找表，則選擇二叉排序樹作為其邏輯結構。
作 者：創心coder
出 處：http://www.cnblogs.com/cxcoder/
QQ群：361982568
訂閱号：cxcoder
文章不足之處，還請諒解！本文會不斷完善更新，轉載請保留出處。如果幫到了您，煩請點贊，以資鼓勵。