本來國慶該出去轉轉的，可是在杭州朋友不多。現在的公司規模又太大，沒上一家公司凝聚力強，想找同僚出來聚聚，後來發現有心無力。是以國慶還是敲代碼吧。不過此刻剛寫完二叉樹，發現已到淩晨2點，注釋也不全。改天再完善吧。之是以有勇氣貼出來，是覺得對得起自己的這番苦心。并且，實作二叉搜尋樹一般需要實作的API我也盡可能補全了。有幾個重要方法的注釋其實我寫的也蠻詳細的，估計看方法注釋也就能懂了，用不着我過多贅述。本篇雖然名為遞歸法實作BST，實際上非遞歸法的前序，中序，後序周遊也都收入其中了。若本實作有什麼不對的地方，歡迎大家批評指正。
import java.util.LinkedList;
import java.util.NoSuchElementException;
import java.util.Queue;
import java.util.Stack;
public class BST<K extends Comparable<K>, V> {
private Node root;
/**
* 該私有内部類用于構造二叉查找樹的節點
*
* @author lhever
*/
private class Node {
private K key;
private V value;
private Node left;
private Node right;
private int N;
public Node(K key, V value, int n) {
this.key = key;
this.value = value;
this.N = n;
}
/**
* eclipse自動生成
*/
@Override
public int hashCode() {
final int prime = ;
int result = ;
result = prime * result + getOuterType().hashCode();
result = prime * result + N;
result = prime * result + ((key == null) ? : key.hashCode());
result = prime * result + ((left == null) ? : left.hashCode());
result = prime * result + ((right == null) ? : right.hashCode());
result = prime * result + ((value == null) ? : value.hashCode());
return result;
}
/**
* eclipse自動生成，在這裡的二叉樹實作下，用于比較兩個節點是否相等是完全可以的，why?大家自己思考咯
*/
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (!getOuterType().equals(other.getOuterType()))
return false;
if (N != other.N)
return false;
if (key == null) {
if (other.key != null)
return false;
} else if (!key.equals(other.key))
return false;
if (left == null) {
if (other.left != null)
return false;
} else if (!left.equals(other.left))
return false;
if (right == null) {
if (other.right != null)
return false;
} else if (!right.equals(other.right))
return false;
if (value == null) {
if (other.value != null)
return false;
} else if (!value.equals(other.value))
return false;
return true;
}
private BST getOuterType() {
return BST.this;
}
}
public BST() {
}
private int size(Node node) {
if (node == null) {
return ;
} else {
return node.N;
}
}
public boolean isEmpty() {
return size() == ;
}
public int size() {
return size(root);
}
/**
* 查找方法， 傳回與置頂鍵關聯的值
*
* @param key
* @return
*/
public V get(K key) {
return get(root, key);
}
private V get(Node node, K key) {
if (node == null) {
return null;
}
int cmp = key.compareTo(node.key);
if (cmp < ) {
return get(node.left, key);
} else if (cmp > ) {
return get(node.right, key);
} else {
return node.value;
}
}
/**
* 判斷是否包含key指定的鍵
* @param key
* @return
*/
public boolean contains(K key) {
if (key == null) {
throw new NullPointerException("參數不能為null");
}
return get(key) != null;
}
/**
* 插入鍵值對
* @param key
* @param value
*/
public void put(K key, V value) {
if (key == null) {
throw new NullPointerException("參數不能為null");
}
if (value == null) {
delete(key);
return;
}
root = put(root, key, value);
assert check();
}
/**
* 将指定的鍵值對插入二叉樹中。
*
* @param node
* @param key
* @param value
* @return
*/
private Node put(Node node, K key, V value) {
if (node == null) {
return new Node(key, value, );
}
int cmp = key.compareTo(node.key);
if (cmp < ) {
node.left = put(node.left, key, value);
} else if (cmp > ) {
node.right = put(node.right, key, value);
} else {
node.value = value;
}
node.N = size(node.left) + + size(node.right);
return node;
}
/**
* 查找最小的鍵
* @return
*/
public K min() {
if (isEmpty()) {
throw new NoSuchElementException("二叉搜尋樹為空");
}
return min(root).key;
}
private Node min(Node node) {
if (node.left == null) {
return node;
} else {
return min(node.left);
}
}
/**
* 查找最大的鍵
* @return
*/
public K max() {
if (isEmpty()) {
throw new NoSuchElementException("二叉搜尋樹為空");
}
return max(root).key;
}
private Node max(Node node) {
if (node.right == null) {
return node;
} else {
return max(node.right);
}
}
public void deleteMin() {
if (isEmpty()) {
throw new NoSuchElementException("二叉搜尋樹為空, 删除失敗");
}
root = deleteMin(root);
assert check();
}
/**
* 删除以參數node為根節點的二叉搜尋樹的最小節點，并傳回删除最小節點後的二叉搜尋樹。
*
* @param node
* @return
*/
private Node deleteMin(Node node) {
/*
* 左節點為空，則樹中最小節點就是根節點，删除後的二叉樹由根節點的右子樹構成
*/
if (node.left == null) {
return node.right;
}
node.left = deleteMin(node.left);
node.N = size(node.left) + + size(node.right);
return node;
}
public void deleteMax() {
if (isEmpty()) {
throw new NoSuchElementException("二叉搜尋樹為空, 删除失敗");
}
root = deleteMax(root);
assert check();
}
/**
* 删除以參數node為根節點的二叉搜尋樹的最大節點，并傳回删除最大節點後的二叉搜尋樹。
*
* @param node
* @return
*/
private Node deleteMax(Node node) {
/*
* 又節點為空，則樹中最大節點就是根節點，删除後的二叉樹由根節點的左子樹構成
*/
if (node.right == null) {
return node.left;
}
node.right = deleteMax(node.right);
node.N = size(node.left) + + size(node.right);
return node;
}
public void delete(K key) {
if (key == null) {
throw new NullPointerException("參數不能為null");
}
root = delete(root, key);
assert check();
}
private Node delete(Node node, K key) {
if (node == null) {
return null;
}
int cmp = key.compareTo(node.key);
if (cmp < ) {
node.left = delete(node.left, key);
} else if (cmp > ) {
node.right = delete(node.right, key);
} else {
if (node.left == null) {
return node.right;
}
;
if (node.right == null) {
return node.left;
}
Node temp = node;
node = min(temp.right);
node.right = deleteMin(temp.right);
node.left = temp.left;
}
node.N = size(node.left) + + size(node.right);
return node;
}
/**
* 向下取整，這個方法的執行過程可以這樣來了解（具體實作不是這樣的，此處幫助了解）：二叉搜尋樹中的鍵值對是鍵有序的， 該方法首先将樹中的所有節點
* 按照鍵的大小排序，排好序之後，假設參數指定的key代表一個節點（該節點在樹中可能存在也可能不存在），是以我們也按排序規則将參數key指定的鍵插入
* 之前已經排号序的序列中， 如果key的确是樹中的某個節點，則這個虛拟的key與真實的某個節點重合。如果key不存在于樹中，則這個虛拟的key會按大小
* 處于排好序的序列中的 某個位置。該方法傳回的是小于或者等于參數指定的key，并且真實存在于樹中的那個key。是以，該方法的名稱與大多數程式設計語言中
* 提供的整數向下取整的方法語義有諸多相似之處
* @param key
* @return
*/
public K floor(K key) {
if (key == null) {
throw new NullPointerException("參數不能為null");
}
if (isEmpty()) {
throw new NoSuchElementException("二叉搜尋樹為空");
}
Node x = floor(root, key);
if (x == null) {
return null;
} else {
return x.key;
}
}
private Node floor(Node node, K key) {
if (node == null)
return null;
int cmp = key.compareTo(node.key);
if (cmp == ) {
return node;
}
if (cmp < ) {
return floor(node.left, key);
}
Node temp = floor(node.right, key);
if (temp != null) {
return temp;
} else {
return node;
}
}
/**
* 向上取整。參照floor()方法的注釋來了解
* @param key
* @return
*/
public K ceiling(K key) {
if (key == null) {
throw new NullPointerException("參數不能為null");
}
if (isEmpty()) {
throw new NoSuchElementException("二叉搜尋樹為空");
}
Node node = ceiling(root, key);
if (node == null) {
return null;
} else {
return node.key;
}
}
private Node ceiling(Node node, K key) {
if (node == null) {
return null;
}
int cmp = key.compareTo(node.key);
if (cmp == ) {
return node;
}
if (cmp < ) {
Node temp = ceiling(node.left, key);
if (temp != null) {
return temp;
} else {
return node;
}
}
return ceiling(node.right, key);
}
/*
* 二叉搜尋樹中的鍵值對是鍵有序的， 該方法傳回将樹中的所有節點按鍵的大小排序後， 鍵的大小排在第k位的節點.
* 并且: 0 <= k < size() -1
*/
public K select(int k) {
if (k < || k >= size()) {
throw new IllegalArgumentException();
}
Node x = select(root, k);
return x.key;
}
/**
* 二叉搜尋樹中的鍵值對是鍵有序的， 該方法傳回将樹中的所有節點按鍵的大小排序後， 鍵的大小排在第k位的節點.
*
* @param x
* @param k
* @return
*/
private Node select(Node node, int k) {
if (node == null) {
return null;
}
int t = size(node.left);
/*
* 如果目前節點的左子樹的大小比k大， 則鍵的排名為k的節點一定在左子樹中
*/
if (t > k) {
return select(node.left, k);
}
/*
* 如果目前節點的左子樹大小比k小，則排名為k的節點一定在右子樹中，并且在右子樹中的排名為k-t-1。
* 因為k指代的是在整棵樹中的排名，排名從0開始。左子樹中鍵最大的節點排名為t-1(左子樹的大小為t)，目前節點排為t,
* 是以左子樹加目前節點的節點總數是t+1， 排名為k的節點一定是在右子樹中排名為k-(t+1)(也即 k-t-1)的節點,該節點其
* 實就是在右子樹中大小為k-t-1的子樹的根節點
*/
else if (t < k) {
return select(node.right, k - t - );
}
/*
* 因為k指代的是在整棵樹中的排名，排名從0開始。左子樹中鍵最大的節點排名為t-1(左子樹的大小為t)，
* 目前節點比左子樹中的任何節點都大，是以恰好排名為t。是以此處傳回目前節點
*/
else {
return node;
}
}
public int rank(K key) {
if (key == null) {
throw new NullPointerException("參數不能為null");
}
return rank(key, root);
}
/**
* 二叉搜尋樹中的鍵值對是鍵有序的， 該方法首先将樹中的所有節點按鍵的大小排序， 然後傳回參數指定的鍵在排好序的節點序列中的序号。
* 若鍵不存在于樹種，一律傳回0
*
* @param key
* @param node
* @return
*/
private int rank(K key, Node node) {
if (node == null) {
return ;
}
int cmp = key.compareTo(node.key);
if (cmp < ) {
return rank(key, node.left);
} else if (cmp > ) {
return + size(node.left) + rank(key, node.right);
} else {
return size(node.left);
}
}
public Iterable<K> keys() {
return keys(min(), max());
}
/**
* 傳回鍵的大小在low和high兩個參數指定的範圍内的鍵
* @param low
* @param high
* @return
*/
public Iterable<K> keys(K low, K high) {
if (low == null) {
throw new NullPointerException("low為空null");
}
if (high == null) {
throw new NullPointerException("high為null");
}
Queue<K> queue = new LinkedList<K>();
keys(root, queue, low, high);
return queue;
}
private void keys(Node node, Queue<K> queue, K low, K high) {
if (node == null) {
return;
}
int cmplo = low.compareTo(node.key);
int cmphi = high.compareTo(node.key);
if (cmplo < ) {
keys(node.left, queue, low, high);
}
if (cmplo <= && cmphi >= ) {
queue.add(node.key);
}
if (cmphi > ) {
keys(node.right, queue, low, high);
}
}
/**
* 傳回大小在low和high兩個參數指定的範圍内的鍵的總數
* @param low
* @param high
* @return
*/
public int size(K low, K high) {
if (low == null) {
throw new NullPointerException("low為null");
}
if (high == null) {
throw new NullPointerException("high為null");
}
if (low.compareTo(high) > ) {
return ;
}
if (contains(high)) {
return rank(high) - rank(low) + ;
} else {
return rank(high) - rank(low);
}
}
/**
* 傳回二叉搜尋樹的高度
*
* @return
*/
public int height() {
return height(root);
}
private int height(Node x) {
if (x == null)
return -;
return + Math.max(height(x.left), height(x.right));
}
/**
* 傳回樹中所有節點的疊代器，周遊所有節點的方式是層序周遊。
*
* @return
*/
public Iterable<K> levelOrder() {
Queue<K> keys = new LinkedList<K>();
Queue<Node> queue = new LinkedList<Node>();
queue.add(root);
while (!queue.isEmpty()) {
Node node = queue.remove();
if (node == null) {
continue;
}
keys.add(node.key);
queue.add(node.left);
queue.add(node.right);
}
return keys;
}
private boolean check() {
if (!isBST()) {
System.out.println("經檢查不符合二叉樹定義");
}
if (!checkSizeConsistent()) {
System.out.println("size檢查異常");
}
if (!checkRankConsistent()) {
System.out.println("秩檢查異常");
}
return isBST() && checkSizeConsistent() && checkRankConsistent();
}
/**
* 判斷是否滿足二叉查找樹的定義（左子樹的節點比目前節點都小， 右子樹中的節點比目前節點都大）
*
* @return
*/
private boolean isBST() {
return isBST(root, null, null);
}
private boolean isBST(Node node, K min, K max) {
if (node == null) {
return true;
}
// 不可能比最小節點小
if (min != null && node.key.compareTo(min) <= ) {
return false;
}
// 不可能比最大節點大
if (max != null && node.key.compareTo(max) >= ) {
return false;
}
/*
* 切分後比較
*/
return isBST(node.left, min, node.key) && isBST(node.right, node.key, max);
}
private boolean checkSizeConsistent() {
return checkSizeConsistent(root);
}
/**
* 判斷任意節點大小是不是等于： （左節點大小 + 1 + 右節點大小）
*
* @param node
* @return
*/
private boolean checkSizeConsistent(Node node) {
if (node == null) {
return true;
}
if (node.N != size(node.left) + size(node.right) + ) {
return false;
}
return checkSizeConsistent(node.left) && checkSizeConsistent(node.right);
}
/**
* 檢查各個節點的鍵的實際排名（秩）是否與我們通過方法計算出來的一緻
*
* @return
*/
private boolean checkRankConsistent() {
for (int i = ; i < size(); i++)
if (i != rank(select(i))) {
return false;
}
for (K key : keys()) {
if (key.compareTo(select(rank(key))) != )
return false;
}
return true;
}
/**
* 列印出節點的内容和值
*
* @param node
*/
public void visit(Node node) {
StringBuffer buff = new StringBuffer();
if (node != null) {
buff.append(" " + node.key + "[");
String left = node.left != null ? node.left.key + "" : "null";
String right = node.right != null ? node.right.key + "" : "null";
buff.append(left)
.append(" : ")
.append(right)
.append("] ");
}
System.out.print(buff.toString());
}
/** 遞歸實作前序周遊 */
private void recursivePreorder(Node node) {
if (node != null) {
visit(node);
recursivePreorder(node.left);
recursivePreorder(node.right);
}
}
public void recursivePreorder() {
recursivePreorder(root);
}
/** 遞歸實作中序周遊 */
private void recursiveInorder(Node node) {
if (node != null) {
recursiveInorder(node.left);
visit(node);
recursiveInorder(node.right);
}
}
public void recursiveInorder() {
recursiveInorder(root);
}
/** 遞歸實作後序周遊 */
private void recursivePostorder(Node node) {
if (node != null) {
recursivePostorder(node.left);
recursivePostorder(node.right);
visit(node);
}
}
public void recursivePostorder() {
recursivePostorder(root);
}
/** 非遞歸實作前序周遊 */
private void preorder(Node node) {
Stack<Node> stack = new Stack<Node>();
if (node != null) {
stack.push(node);
while (!stack.empty()) {
node = stack.pop();
visit(node);
if (node.right != null) {
stack.push(node.right);
}
if (node.left != null) {
stack.push(node.left);
}
}
}
}
public void preorder() {
preorder(root);
}
/**
* 非遞歸實作後序周遊
*
* 後序周遊的非遞歸算法是三種順序中最複雜的，原因在于，後序周遊是先通路左、右子樹,再通路根節點，
* 而在非遞歸算法中，利用棧回退到時，并不知道是從左子樹回退到根節點，還是從右子樹回退到根節點，
* 如果從左子樹回退到根節點，取出的根節點應該放回去，然後去通路右子樹，而如果從右子樹回退到根節點，此時的确輪到通路
* 根節點了。這個過程相比前序和後序，必須得在壓棧時添加資訊（此處的實作利用參數q記錄已經通路過的節點，如果右節點已經通路過
* ， 則可以通路棧中彈出的根節點，如果右節點還沒有通路過，則再次将彈出的根節點壓回棧中，轉而通路右節點，待通路右節點結束再彈出根節點進行通路），
* 以便在退棧時可以知道是從左子樹傳回， 還是從右子樹傳回進而決定下一步的操作。
**/
private void postorder(Node p) {
Node q = p;
Stack<Node> stack = new Stack<Node>();
while (p != null) {
// 左子樹入棧
for (; p.left != null; p = p.left) {
stack.push(p);
}
// 目前節點無右子或右子已經輸出
while (p != null && (p.right == null || p.right == q)) {
visit(p);
q = p;// 記錄上一個已輸出節點
if (stack.empty()) {
return;
}
p = stack.pop();
}
// 處理右子
stack.push(p);
p = p.right;
}
}
public void postorder() {
postorder(root);
}
/** 非遞歸實作中序周遊 */
private void inorder(Node p) {
Stack<Node> stack = new Stack<Node>();
while (p != null) {
while (p != null) {
if (p.right != null) {
stack.push(p.right);// 目前節點右子入棧
}
stack.push(p);// 目前節點入棧
p = p.left;
}
p = stack.pop();
while (!stack.empty() && p.right == null) {
visit(p);
p = stack.pop();
}
visit(p);
if (!stack.empty()) {
p = stack.pop();
} else {
p = null;
}
}
}
public void inorder() {
inorder(root);
}
public static void main(String[] args) {
BST<String, Integer> st = new BST<String, Integer>();
st.put("China", );
st.put("America", );
st.put("Japan", );
st.put("Russian", );
st.put("Poland", );
st.put("India", );
for (String s : st.levelOrder()) {
System.out.println(s + " ---> " + st.get(s));
}
for (String s : st.keys()) {
System.out.println(s + " " + st.get(s));
}
/**
* H
* / \
* / \
* D L
* / \ / \
* / \ I X
* B G
* / \ / \
* A C F 無
* / \
* E 無
*/
BST<String, String> st1 = new BST<String, String>();
st1.put("H", "H0");
st1.put("D", "D0");
st1.put("B", "B0");
st1.put("G", "G0");
st1.put("A", "A0");
st1.put("C", "C0");
st1.put("F", "F0");
st1.put("E", "E0");
st1.put("L", "L0");
st1.put("I", "I0");
st1.put("X", "X0");
st1.recursivePreorder();
System.out.println();
st1.recursiveInorder();
System.out.println();
st1.recursivePostorder();
System.out.println();
System.out.println("--------------------------------------------------------------------");
st1.preorder();
System.out.println();
st1.postorder();
System.out.println();
st1.inorder();
}
}
![查找算法之二分查找查找算法之二分查找[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)