查看高亮文檔請點(diǎn)擊:
[https://www.zybuluo.com/huangyichun/note/739561]
定義:二叉查找樹是一棵二叉樹罩引，且每個節(jié)點(diǎn)的值都大于左子樹的值惦积，小于右子樹的值。
如下圖所示:
**
其中數(shù)字代表二叉查找樹的鍵趁猴，字母代表二叉查找樹的值**
image.png-46.7kB
我們可以通過二叉樹的中序遍歷二叉查找樹得到一個有序的數(shù)組。
數(shù)據(jù)表示：設(shè)計一個二叉查找樹類彪见，在類中嵌套一個私有類表示二叉查找樹的一個節(jié)點(diǎn)儡司，每個節(jié)點(diǎn)都有一個鍵和一個值，一個左鏈接和一個右鏈接余指，和一個節(jié)點(diǎn)計數(shù)器捕犬。左鏈接指向一棵小于該節(jié)點(diǎn)的二叉排序樹，右鏈接指向一棵大于該節(jié)點(diǎn)的二叉排序樹酵镜。
/**
* 二叉查找樹實(shí)現(xiàn)
*/
public class BST <Key extends Comparable<Key>, Value> {
private Node root; //根節(jié)點(diǎn)
private class Node{
private Key key; //鍵
private Value val; //值
private Node left, right; //左右子樹的鏈接
private int N; //以該節(jié)點(diǎn)為根的子樹中的節(jié)點(diǎn)總數(shù)
public Node(Key key, Value val, int N) {
this.key = key;
this.val = val;
this.N = N;
}
}
public void printfBST(){
printfBST(root);
}
/**
* 中序打印二叉查找樹
* @param node
*/
private void printfBST(Node node){
if(node == null)
return;
printfBST(node.left);
System.out.print(node.key+" ");
printfBST(node.right);
}
/**
* 從根節(jié)點(diǎn)出發(fā)碉碉，查找樹中排名為K的鍵，即正好有k個小于它的鍵
* @param k
* @return
*/
public Key select(int k){
return select(root, k).key;
}
/**
* 刪除最小鍵值的節(jié)點(diǎn)
*/
public void deleteMin(){
root = deleteMin(root);
}
/**
* 刪除鍵值為key的節(jié)點(diǎn)
* @param key
*/
public void delete(Key key){
root = delete(root,key);
}
/**
* 以Node為根節(jié)點(diǎn)刪除某個鍵為key的節(jié)點(diǎn)
* 1.首先找到值為Key的節(jié)點(diǎn)
* 2.如果node沒有右子樹淮韭，返回node的左子樹誉裆，
* 如果node沒有左子樹，返回node的右子樹
* 3.如果node左右子樹都存在缸濒，則在node的右子樹中找到最小的一個
* 節(jié)點(diǎn)，替代node
* @param node
* @param key
* @return
*/
private Node delete(Node node , Key key){
if(node == null)
return null;
int cmp = key.compareTo(node.key);
if(cmp < 0)
node.left = delete(node.left, key);
else if(cmp > 0)
node.right = delete(node.right, key);
else {
if(node.right == null) return node.left;
if(node.left == null) return node.right;
Node t = node;
node = min(node.right);
node.right = deleteMin(t.right);
node.left = t.left;
}
node.N = size(node.left) + size(node.right) + 1;
return node;
}
/**
* 以node為根節(jié)點(diǎn)刪除最小的節(jié)點(diǎn)
* @param node
* @return
*/
private Node deleteMin(Node node){
if(node.left == null)
return node.right;
node.left = deleteMin(node.left); //刪除最小節(jié)點(diǎn)
node.N = size(node.left) + size(node.right) + 1;//更新節(jié)點(diǎn)數(shù)
return node;
}
/**
* 從Node節(jié)點(diǎn)出發(fā)粱腻，查找樹中排名為K的鍵庇配，即正好有k個小于它的鍵
* @param node
* @param k
* @return
*/
private Node select(Node node, int k){
if(node == null)
return null;
int t = size(node.left);//左子樹個數(shù)
if(t > k) return select(node.left,k);
else if(t < k) return select(node.right, k-t-1);//右子樹中查找
else return node;
}
/**
* 從根節(jié)點(diǎn)開始查找Key
* 如果存在返回，不存在找到第一個小于該key的鍵
* @param key
* @return
*/
public Key floor(Key key){
Node node = floor(root, key);
if(node == null) return null;
return node.key;
}
/**
* 從node節(jié)點(diǎn)開始查找Key
* 如果存在返回绍些，不存在找到第一個小于該key的鍵
* 即向下取整
* @param node
* @param key
* @return
*/
private Node floor(Node node, Key key){
if(node == null)
return null;
int cmp = key.compareTo(node.key);
if(cmp == 0) return node;
else if(cmp < 0) return floor(node.left, key);
Node t = floor(node.right, key);//查找右子樹中是否有小于Key的節(jié)點(diǎn)
if(t != null) return t;
else return node;
}
/**
* 查找根節(jié)點(diǎn)最大的鍵
* @return
*/
public Key max(){
return max(root).key;
}
/**
*查找以node節(jié)點(diǎn)為根節(jié)點(diǎn)的最大鍵
* 如果左子樹為空捞慌，則當(dāng)前節(jié)點(diǎn)為最大值
* 否則最小值就是左子樹的最大值
* @param node
* @return
*/
private Node max(Node node){
if(node.right == null)
return node;
return max(node.right);
}
/**
* 查找根節(jié)點(diǎn)最小的鍵
* @return
*/
public Key min(){
return min(root).key;
}
/**
* 查找以node節(jié)點(diǎn)為根節(jié)點(diǎn)的最小鍵
* 如果左子樹為空，則當(dāng)前節(jié)點(diǎn)為最小值
* 否則最小值就是左子樹的最小值
* @param node
* @return
*/
private Node min(Node node){
if(node.left == null) return node;
return min(node.left);
}
/**
* 查找key存在則修改更新它的值柬批，否則創(chuàng)建一個新的節(jié)點(diǎn)
* @param key
* @param value
*/
public void put(Key key, Value value){
root = put(root, key, value);
}
/**
* 如果Key存在于以node為根節(jié)點(diǎn)的子樹中啸澡，則更新它的值
* 否則將以key和Value為鍵值對的新節(jié)點(diǎn)插入到該子樹中
* @param node
* @param key
* @param value
* @return
*/
private Node put(Node node, Key key, Value value){
if(node == null)
return new Node(key, value, 1);
int cmp = key.compareTo(node.key);
if(cmp < 0) node.left = put(node.left, key, value);
else if(cmp > 0) node.right = put(node.right, key, value);
else node.val = value;
node.N = size(node.left) + size(node.right) + 1;//更新節(jié)點(diǎn)數(shù)
return node;
}
/**
* 獲取Key對應(yīng)的Value
* @param key
* @return
*/
public Value get(Key key){
return get(root, key);
}
/**
* 在以node為根節(jié)點(diǎn)的子樹中查找并返回Key所對應(yīng)的值
* @param node
* @param key
* @return
*/
private Value get(Node node, Key key){
if(node == null)
return null;
int cmp = key.compareTo(node.key);
if(cmp < 0) return get(node.left, key);
else if(cmp > 0) return get(node.right, key);
else return node.val;
}
/**
* 獲取二叉查找樹節(jié)點(diǎn)個數(shù)
* 滿足 size(x) = size(x.left) + size(x.right) + 1；
* 對于空鏈接size(x)返回0
* @return 返回節(jié)點(diǎn)個數(shù)
*/
public int size(){
return size(root);
}
private int size(Node node){
if(node == null)
return 0;
else
return node.N;
}
}
構(gòu)建上圖的二叉查找樹氮帐，對于里面的方法進(jìn)行測試:
/**
* Created by huangyichun on 2017/5/1.
*/
public class Test {
public static void main(String[] args) {
BST<Integer,Character> bst = new BST<Integer, Character>();
bst.put(15,'A');
bst.put(13,'B');
bst.put(11,'D');
bst.put(8,'H');
bst.put(14,'E');
bst.put(20,'C');
bst.put(17,'F');
bst.put(11,'G');
bst.printfBST();
System.out.println();
System.out.println("最大鍵:" + bst.max());//打印最大鍵
System.out.println("最小鍵:" + bst.min());//打印最小鍵
System.out.println("Key= 15, value=" + bst.get(15));
System.out.println("節(jié)點(diǎn)個數(shù)為:" + bst.size());
bst.delete(13);//刪除13這個節(jié)點(diǎn)
bst.printfBST();
// bst.deleteMin();
// bst.printfBST();
}
}
輸出結(jié)果為:
8 11 13 14 15 17 20
最大鍵:20
最小鍵:8
Key= 15, value=A
節(jié)點(diǎn)個數(shù)為:7
8 11 14 15 17 20
