java二叉查找樹實現：

二叉查找樹，上圖：比根節點小者在其左邊，比根節點大者在其右邊。

抽象數據結構，上代碼：

/**


二叉查找樹數據結構(非線程安全)：
范型類型須實現Comparable接口，用于比較操作
*/
public class BinarySearchTree<T extends Comparable<T>> { 
    private Node<T> root; // tree root
    private int count;  // tree element counts

    /*
      內部節點類
     */
    private class Node<E>{
        E value; //元素對象
        Node<E> parent; //父節點
        Node<E> left; //左孩子節點
        Node<E> right; //右孩子節點
        public Node(E value, Node<E> parent, Node<E> left, Node<E> right) {
            this.value = value;
            this.parent = parent;
            this.left = left;
            this.right = right;
        }
    }
}</pre> 
一些基本操作實現： 


插入(insert): 依次比較根元素，小者放左邊，大者放右邊： 
</ul>

/**


插入元素
@param t 待插入元素
@return 插入成功返回true, 反之返回false
*/
public boolean insert(T t){
    if (root == null){ //若為空樹
        root = new Node<T>(t, null, null, null);
        return true;
    }
    Node<T> newNode = new Node<T>(t, null, null, null);
    Node<T> pointer = root;
    while(true){
 if (newNode.value.compareTo(pointer.value) > 0){
     if (pointer.right == null){ //插入右邊
 newNode.parent = pointer;
 pointer.right = newNode;
 count++;
 return true;

     } else{
 pointer = pointer.right;

     }
 } else if (newNode.value.compareTo(pointer.value) < 0){
     if (pointer.left == null){ //插入左邊
 newNode.parent = pointer;
 pointer.left = newNode;
 count++;
 return true;

     } else{
 pointer = pointer.left;

     }
 } else { //相等了
     return false;
 }
    }
}</pre> 

查找(get): 

/**
查找元素
@param t 待查找元素
@return 對應元素或null
*/
public T get(T t) {
    Node<T> n = getN(t);
    return n == null? null : n.value;
}

/*
  查找節點

@param t 待查找元素
@return 元素對應節點或null
*/
private Node<T> getN(T t) {
    Node<T> cur = root;
    while (cur != null){
        if (cur.value.compareTo(t) < 0){ //右邊子樹找
            cur = cur.right;
        } else if(cur.value.compareTo(t) > 0){ //左邊子樹找
            cur = cur.left;
        } else{ //找到該節點
            break;
        }
    }
    return cur;
}</pre> 

查找最大，最小元素： 

/**
獲取某節點為根的樹的最小元素
*/
public T min(Node<T> n){
    Node<T> min = minN(n);
    return min == null ? null : min.value;
}

/**

獲取某節點為根的樹的最小節點
@param n 樹根節點
@return 該子樹最小節點
*/
private Node<T> minN(Node<T> n){
    Node<T> min = n;
    while (min != null && min.left != null){
        min = min.left;
    }
    return min;
}</pre>
/**
獲取某節點為根的樹的最大元素
@return 最大元素, 沒有返回null
*/
public T max(Node<T> n){
    Node<T> max = maxN(n);
    return max == null ? null : max.value;
}

/*
  獲取某節點為根的樹的最大節點
 */
private Node<T> maxN(Node<T> n){
    Node<T> max = n;
    while (max != null && max.right != null){
        max = max.right;
    }
    return max;
}</pre> 

遍歷樹(中序遍歷): 
</ul>

/**


中序遍歷
*/
public void leftRootRight(){
    printLRR(root);
}

/**

中序遍歷打印元素
*/
private void printLRR(Node<T> node) {
    if (node != null){
        printLRR(node.left);
        System.out.println(node.value);
        printLRR(node.right);
    }
}</pre> 

獲取前驅(prev)元素： 

        主要有兩種情況： 
           1.該節點左子樹不為空：其前驅節點為其左子樹的最大元素: 
            
           2.該節點左子樹為空: 其前驅節點為其祖先節點(遞歸)，且該祖先節點的右孩子也為其祖先節點(就是一直往其parent找，出現左拐后的那個祖先節點)： 
 






代碼實現： 
/**
獲取元素前驅(中序遍歷)
@param t 指定元素
@return 元素前驅，沒有返回null
*/
public T prev(T t){
 //先找到該元素
 Node<T> cur = getN(t);
 if (cur != null){
 return locatePrev(cur);

 }
 return null;
}

/**

定位到前驅節點
@param cur 當前節點
@return 前驅節點，沒有返回null
*/
private T locatePrev(Node<T> cur) {
 Node<T> prev = locatePrevN(cur); 
 return prev == null ? null : prev.value;
}

/**

定位到前驅節點
@param cur 當前節點
@return 當前節點的前驅節點
*/
private Node<T> locatePrevN(Node<T> cur){
 if (cur != null){
 //1.如果該節點左子樹不會空，則其前驅為其左子樹的最大元素
 if (cur.left != null) return maxN(cur.left);
 //2.該節點左子樹為空, 則其前驅為：其祖先節點(遞歸), 且該祖先節點的右孩子也是其祖先節點
 //  通俗的說，一直忘上找找到左拐后那個節點;
 Node<T> p = cur.parent;
 while(p != null && cur == p.left){
     cur = p;
     p = p.parent;
 }
 return p == null ? null: p;

 }
 return null;
}</pre> 

獲取后繼節點，也分兩種情況： 

      1.該節點右子樹不為空，其后繼節點為其右子樹的最小元素： 
         
       2.該節點右子樹為空，其后繼節點為其祖先節點(遞歸)，且此祖先節點的左孩子也是該節點的祖先節點，就是說一直往上找其祖先節點，直到出現右拐后的那個祖先節點： 
        
實現代碼： 
/**
獲取元素后繼元素(中序遍歷)
@param t 指定元素
@return 后繼元素，沒有返回null
*/
public T next(T t){
 //先找到該元素
 Node<T> cur = getN(t);
 if (cur != null){
 return locateNext(cur);

 }
 return null;
}

/**

定位當前節點的后繼元素
@param cur 當前節點
@return 其后繼元素
*/
private T locateNext(Node<T> cur) {
 Node<T> next = locateNextN(cur);
 return next == null ? null : next.value;
}

/**

定位到當前節點的后繼節點
@param cur 當前節點
@return 當前節點的后繼節點
*/
private Node<T> locateNextN(Node<T> cur) {
 if (cur == null) return null;
 //1.若其右子樹不為空，那么其后繼節點就是其右子樹的最小元素
 if (cur.right != null) return minN(cur.right);
 //2.若為空，應該為其祖先節點(遞歸)，且該祖先節點的左孩子也是其祖先節點
 //  通俗的說，一直忘上找，找到右拐后那個節點;
 Node<T> p = cur.parent;
 while (p != null && cur == p.right){
 cur = p;
 p = p.parent;

 }
 return p;
}</pre> 

刪除(remove), 可分為三種情況： 

      1.該節點為葉子節點，直接刪除： 
       
      2.該節點有一個孩子，將其孩子接上其父節點： 
           
      3.該節點有2個孩子，先刪除其右子樹的最小元素(該元素最多只會有一個孩子)，將這個最小元素去替換要刪除的節點： 
       
實現代碼： 
/**
移除某元素 
@param t 待刪除元素
@return 刪除成功返回true, 反之false
*/
public boolean remove(T t){
 //找到該節點
 Node<T> cur = getN(t);
 if (cur != null){
 if (doRemove(cur)){
     count--;
     return true;
 }

 }
 return false;
}

/**

執行刪除操作
*/
private boolean doRemove(Node<T> cur) {
 //該節點是否是其父節點的右孩子
 boolean isRightChild = cur.parent.right == cur;
 //1.該節點為葉子節點, 直接將其父節點對應(左或右)孩子置空
 if (cur.left == null && cur.right == null){
 if (isRightChild) //該節點為父節點的右孩子
     cur.parent.right = null;
 else                    //該節點為父節點的左孩子
     cur.parent.left = null;
 return true;

 } else if(cur.left != null && cur.right != null){
 //2.該節點有2個孩子, 我們采取將其后繼節點x刪除(x節點最多只會有一個孩子)，并用x替換該節點
 //找到其后繼節點
 Node<T> nextNode = locateNextN(cur);
 doRemove(nextNode);
 cur.value = nextNode.value;
 return true;

 } else{ //3.該節點有1個孩子, 直接將其父節點對應(左或右)孩子接到其非空孩子
 Node<T> needLinkedNode = null;
 if (cur.left == null && cur.right != null){ //該節點有右孩子
     needLinkedNode = cur.right; 
 } else if(cur.left != null && cur.right == null){ //該節點有左孩子
     needLinkedNode = cur.left;
 }
 if (isRightChild) 
     cur.parent.right = needLinkedNode;
 else 
     cur.parent.left = needLinkedNode;
 return true;

 }
}</pre>