插入操作：
與根節(jié)點比較相等則覆蓋其值县袱，若小于則與左節(jié)點比較浑娜，若大與則與右節(jié)點比較，若根節(jié)點為空則插入這個位置即可式散。遞歸重復(fù)即可筋遭。
查找操作
與根節(jié)點比較相等，若根節(jié)點為空暴拄，則返回false漓滔，若大于根節(jié)點則與右節(jié)點比較
若小于則與左節(jié)點比較，若等于則返回節(jié)點的值乖篷，以此遞歸即可响驴。
遍歷
深度優(yōu)先遍歷：
中序遍歷出來的是排序好的隊列
后序遍歷是用來刪除節(jié)點用的
廣度優(yōu)先遍歷
以上的算法實現(xiàn)
package bobo.algo;
// 二分搜索樹
// 由于Key需要能夠進行比較，所以需要extends Comparable
public class BST, Value> {
// 樹中的節(jié)點為私有的類, 外界不需要了解二分搜索樹節(jié)點的具體實現(xiàn)
? ? private class Node {
private Key key;
? ? ? ? private Value value;
? ? ? ? private Node left, right;
? ? ? ? public Node(Key key, Value value) {
this.key = key;
? ? ? ? ? ? this.value = value;
? ? ? ? ? ? left = right =null;
? ? ? ? }
}
private Node root;? // 根節(jié)點
? ? private int count;? // 樹種的節(jié)點個數(shù)
? ? // 構(gòu)造函數(shù), 默認構(gòu)造一棵空二分搜索樹
? ? public BST() {
root =null;
? ? ? ? count =0;
? ? }
// 返回二分搜索樹的節(jié)點個數(shù)
? ? public int size() {
return count;
? ? }
// 返回二分搜索樹是否為空
? ? public boolean isEmpty() {
return count ==0;
? ? }
// 向二分搜索樹中插入一個新的(key, value)數(shù)據(jù)對
? ? public void insert(Key key, Value value){
root = insert(root, key, value);
? ? }
// 查看二分搜索樹中是否存在鍵key
? ? public boolean contain(Key key){
return contain(root, key);
? ? }
// 在二分搜索樹中搜索鍵key所對應(yīng)的值撕蔼。如果這個值不存在, 則返回null
? ? public Value search(Key key){
return search( root, key );
? ? }
// 二分搜索樹的前序遍歷
? ? public void preOrder(){
preOrder(root);
? ? }
// 二分搜索樹的中序遍歷
? ? public void inOrder(){
inOrder(root);
? ? }
// 二分搜索樹的后序遍歷
? ? public void postOrder(){
postOrder(root);
? ? }
//********************
? ? //* 二分搜索樹的輔助函數(shù)
? ? //********************
? ? // 向以node為根的二分搜索樹中, 插入節(jié)點(key, value), 使用遞歸算法
? ? // 返回插入新節(jié)點后的二分搜索樹的根
? ? private Node insert(Node node, Key key, Value value){
if( node ==null ){
count ++;
? ? ? ? ? ? return new Node(key, value);
? ? ? ? }
if( key.compareTo(node.key) ==0 )
node.value = value;
? ? ? ? else if( key.compareTo(node.key) <0 )
node.left = insert( node.left, key, value);
? ? ? ? else? ? // key > node->key
? ? ? ? ? ? node.right = insert( node.right, key, value);
? ? ? ? return node;
? ? }
// 查看以node為根的二分搜索樹中是否包含鍵值為key的節(jié)點, 使用遞歸算法
? ? private boolean contain(Node node, Key key){
if( node ==null )
return false;
? ? ? ? if( key.compareTo(node.key) ==0 )
return true;
? ? ? ? else if( key.compareTo(node.key) <0 )
return contain( node.left, key );
? ? ? ? else // key > node->key
? ? ? ? ? ? return contain( node.right, key );
? ? }
// 在以node為根的二分搜索樹中查找key所對應(yīng)的value, 遞歸算法
? ? // 若value不存在, 則返回NULL
? ? private Value search(Node node, Key key){
if( node ==null )
return null;
? ? ? ? if( key.compareTo(node.key) ==0 )
return node.value;
? ? ? ? else if( key.compareTo(node.key) <0 )
return search( node.left, key );
? ? ? ? else // key > node->key
? ? ? ? ? ? return search( node.right, key );
? ? }
// 對以node為根的二叉搜索樹進行前序遍歷, 遞歸算法
? ? private void preOrder(Node node){
if( node !=null ){
System.out.println(node.key);
? ? ? ? ? ? preOrder(node.left);
? ? ? ? ? ? preOrder(node.right);
? ? ? ? }
}
// 對以node為根的二叉搜索樹進行中序遍歷, 遞歸算法
? ? private void inOrder(Node node){
if( node !=null ){
inOrder(node.left);
? ? ? ? ? ? System.out.println(node.key);
? ? ? ? ? ? inOrder(node.right);
? ? ? ? }
}
// 對以node為根的二叉搜索樹進行后序遍歷, 遞歸算法
? ? private void postOrder(Node node){
if( node !=null ){
postOrder(node.left);
? ? ? ? ? ? postOrder(node.right);
? ? ? ? ? ? System.out.println(node.key);
? ? ? ? }
}
// 測試二分搜索樹
? ? public static void main(String[] args) {
int N =1000000;
? ? ? ? // 創(chuàng)建一個數(shù)組豁鲤，包含[0...N)的所有元素
? ? ? ? Integer[] arr =new Integer[N];
? ? ? ? for(int i =0 ; i < N; i ++)
arr[i] =new Integer(i);
? ? ? ? // 打亂數(shù)組順序
? ? ? ? for(int i =0 ; i < N; i ++){
int pos = (int) (Math.random() * (i+1));
? ? ? ? ? ? Integer t = arr[pos];
? ? ? ? ? ? arr[pos] = arr[i];
? ? ? ? ? ? arr[i] = t;
? ? ? ? }
// 由于我們實現(xiàn)的二分搜索樹不是平衡二叉樹秽誊，
? ? ? ? // 所以如果按照順序插入一組數(shù)據(jù)，我們的二分搜索樹會退化成為一個鏈表
? ? ? ? // 平衡二叉樹的實現(xiàn)琳骡，我們在這個課程中沒有涉及锅论，
? ? ? ? // 有興趣的同學可以查看資料自學諸如紅黑樹的實現(xiàn)
? ? ? ? // 以后有機會，我會在別的課程里向大家介紹平衡二叉樹的實現(xiàn)的：）
? ? ? ? // 我們測試用的的二分搜索樹的鍵類型為Integer楣号，值類型為String
? ? ? ? // 鍵值的對應(yīng)關(guān)系為每個整型對應(yīng)代表這個整型的字符串
? ? ? ? BST bst =new BST();
? ? ? ? for(int i =0 ; i < N; i ++)
bst.insert(new Integer(arr[i]), Integer.toString(arr[i]));
? ? ? ? // 對[0...2*N)的所有整型測試在二分搜索樹中查找
? ? ? ? // 若i在[0...N)之間最易，則能查找到整型所對應(yīng)的字符串
? ? ? ? // 若i在[N...2*N)之間，則結(jié)果為null
? ? ? ? for(int i =0 ; i <2*N; i ++){
String res = bst.search(new Integer(i));
? ? ? ? ? ? if( i < N )
assert res.equals(Integer.toString(i));
else
? ? ? ? ? ? ? ? assert res ==null;
? ? ? ? }
}
}
廣度優(yōu)先遍歷就是先建造一個隊列（先進先出）
首先將根節(jié)點加入隊列炫狱，移除根節(jié)點（遍歷）的同時加入左右節(jié)點藻懒，遍歷左節(jié)點將左節(jié)點的左右子節(jié)點加入到隊列，再遍歷右節(jié)點同時將右節(jié)點的左右子節(jié)點加入隊列视译，以此類推嬉荆。
// 二分搜索樹的層序遍歷
public void levelOrder(){
// 我們使用LinkedList來作為我們的隊列
? ? Queue q =new LinkedList();
? ? q.add(root);
? ? while( !q.isEmpty() ){
Node node = q.remove();
? ? ? ? System.out.println(node.key);
? ? ? ? if( node.left !=null )
q.add( node.left );
? ? ? ? if( node.right !=null )
q.add( node.right );
? ? }
}
刪除二分搜索樹的最小值和最大值
先找到最小值，最小值一定是最左邊的節(jié)點憎亚，一直遍歷左子樹员寇，最后一個非空即為最小節(jié)點，要防止的是其還有右子節(jié)點第美，如果沒有右子節(jié)點直接刪除即可蝶锋，有的話將其右節(jié)點放在它原來的位置即可。刪除最大節(jié)點要防止其有左節(jié)點什往，若有的話扳缕，將其左節(jié)點放在原來它的位置即可，若無别威，則直接刪除即可躯舔。
// 返回刪除節(jié)點后新的二分搜索樹的根
private Node removeMin(Node node){
if( node.left ==null ){
Node rightNode = node.right;
? ? ? ? node.right =null;
? ? ? ? count --;
? ? ? ? return rightNode;
? ? }
node.left = removeMin(node.left);
? ? return node;
}
// 刪除掉以node為根的二分搜索樹中的最大節(jié)點
// 返回刪除節(jié)點后新的二分搜索樹的根
private Node removeMax(Node node){
if( node.right ==null ){
Node leftNode = node.left;
? ? ? ? node.left =null;
? ? ? ? count --;
? ? ? ? return leftNode;
? ? }
node.right = removeMax(node.right);
? ? return node;
}
刪除隨便一個節(jié)點
找出右子樹中最小的數(shù)，替換原來的位置省古。
// 刪除掉以node為根的二分搜索樹中鍵值為key的節(jié)點, 遞歸算法
// 返回刪除節(jié)點后新的二分搜索樹的根
Node remove(Node node, Key key){
if( node ==null )
return null;
? ? if( key.compareTo(node.key) <0 ){
node.left = remove( node.left, key );
? ? ? ? return node;
? ? }
else if( key.compareTo(node.key) >0 ){
node.right = remove( node.right, key );
? ? ? ? return node;
? ? }
else{// key == node->key
? ? ? ? // 待刪除節(jié)點左子樹為空的情況
? ? ? ? if( node.left ==null ){
Node rightNode = node.right;
? ? ? ? ? ? node.right =null;
? ? ? ? ? ? count --;
? ? ? ? ? ? return rightNode;
? ? ? ? }
// 待刪除節(jié)點右子樹為空的情況
? ? ? ? if( node.right ==null ){
Node leftNode = node.left;
? ? ? ? ? ? node.left =null;
? ? ? ? ? ? count--;
? ? ? ? ? ? return leftNode;
? ? ? ? }
// 待刪除節(jié)點左右子樹均不為空的情況
? ? ? ? // 找到比待刪除節(jié)點大的最小節(jié)點, 即待刪除節(jié)點右子樹的最小節(jié)點
? ? ? ? // 用這個節(jié)點頂替待刪除節(jié)點的位置
? ? ? ? Node successor =new Node(minimum(node.right));
? ? ? ? count ++;
? ? ? ? successor.right = removeMin(node.right);
? ? ? ? successor.left = node.left;
? ? ? ? node.left = node.right =null;
? ? ? ? count --;
? ? ? ? return successor;
? ? }
}
二叉搜索樹在極端的情況下如0123456789下變成鏈表粥庄，所以采用平衡樹解決這個問題即可如紅黑樹
