Java數據結構之二叉排序樹的實現
1 二叉排序樹的概述
本文沒有介紹一些基礎知識。對於常見查找算法，比如順序查找、二分查找、插入查找、斐波那契查找還不清楚的，可以看這篇文章：常見查找算法詳解以及Java代碼的實現。
假設查找的數據集是普通的順序存儲，那麼插入操作就是將記錄放在表的末端，給表記錄數加一即可，刪除操作可以是刪除後，後面的記錄向前移，也可以是要刪除的元素與最後一個元素互換，表記錄數減一，反正整個數據集也沒有什麼順序，這樣的效率也不錯。應該說，插入和刪除對於順序存儲結構來說，效率是可以接受的，但這樣的表由於無序造成查找的效率很低。
如果查找的數據集是有序線性表，並且是順序存儲的，查找可以用折半、插值、斐波那契等查找算法來實現，可惜，因為有序，在插入和刪除操作上，為瞭維持順序，需要移動大量元素，就需要耗費大量的時間。
有沒有一種即可以使得插入和刪除效率不錯，又可以比較高效率地實現查找的算法呢？這就是二叉排序樹。
二叉排序樹（Binary Sort Tree），又稱為二叉查找樹/二叉搜索樹（binary search tree）。它是具有下列性質的二叉樹：
- 若它的左子樹不空，則左子樹上所有節點的值均小於它的根結構的值；
- 若它的右子樹不空，則右子樹上所有節點的值均大於它的根節點的值；
- 它的左、右子樹也分別為二叉排序樹；
- 二叉排序樹也可以是一個空樹。
構造一棵二叉排序樹的目的，其主要目的並不是為瞭排序，而是為瞭提高查找和插入刪除關鍵字的速度，用以提升數據結構的綜合能力。不管怎麼說，在一個有序數據集上的查找，速度總是要快於無序的數據集的，而二叉排序樹這種非線性的結構，也有利於插入和刪除的實現。
2 二叉排序樹的構建
2.1 類架構
首先，最簡單的節點對象還是需要一個數據域和兩個引用域。
另外還需要一個比較器的引用，因為需要對元素進行排序，自然需要比較元素的大小，如果外部傳遞瞭比較器，那麼就使用用戶指定的比較器進行比較，否則，數據類型E必須是Comparable接口的子類，否則因為不能比較而報錯。
另外，還需要提供中序遍歷的方法，該遍歷方法對於二叉排序樹的結果將會順序展示。
public class BinarySearchTree<E> {
/**
* 外部保存根節點的引用
*/
private BinaryTreeNode<E> root;
/**
* 自定義比較器
*/
private Comparator<? super E> cmp;
/**
* 樹節點的數量
*/
private int size;
/**
* 內部節點對象
*
* @param <E> 數據類型
*/
public static class BinaryTreeNode<E> {
//數據域
E data;
//左子節點
BinaryTreeNode<E> left;
//右子節點
BinaryTreeNode<E> right;
public BinaryTreeNode(E data) {
this.data = data;
}
@Override
public String toString() {
return data.toString();
}
}
/**
* 指定比較器
*
* @param cmp 比較器
*/
public BinarySearchTree(Comparator<? super E> cmp) {
this.cmp = cmp;
}
/**
* 空構造器
*/
public BinarySearchTree() {
}
/**
* 是否是空樹
*
* @return true 是 ;false 否
*/
public boolean isEmpty() {
return size == 0;
}
/**
* 返回節點數
*
* @return 節點數
*/
public int size() {
return size;
}
/**
* 對元素進行比較大小的方法,如果傳遞瞭自定義比較器,則使用自定義比較器,否則則需要數據類型實現Comparable接口
*
* @param e1 被比較的第一個對象
* @param e2 被比較的第二個對象
* @return 0 相等 ;小於0 e1 < e2 ;大於0 e1 > e2
*/
private int compare(E e1, E e2) {
if (cmp != null) {
return cmp.compare(e1, e2);
} else {
return ((Comparable<E>) e1).compareTo(e2);
}
}
/**
* 保存遍歷出來的節點數據
*/
List<BinaryTreeNode<E>> str = new ArrayList<>();
/**
* 中序遍歷,提供給外部使用的api
*
* @return 遍歷的數據
*/
public String toInorderTraversalString() {
//如果是空樹,直接返回空
if (isEmpty()) {
return null;
}
//從根節點開始遞歸
inorderTraversal(root);
//獲取遍歷結果
String s = str.toString();
str.clear();
return s;
}
/**
* 中序遍歷 內部使用的遞歸遍歷方法,借用瞭棧的結構
*
* @param root 節點,從根節點開始
*/
private void inorderTraversal(BinaryTreeNode<E> root) {
BinaryTreeNode<E> left = getLeft(root);
if (left != null) {
//如果左子節點不為null,則繼續遞歸遍歷該左子節點
inorderTraversal(left);
}
//添加數據節點
str.add(root);
//獲取節點的右子節點
BinaryTreeNode<E> right = getRight(root);
if (right != null) {
//如果右子節點不為null,則繼續遞歸遍歷該右子節點
inorderTraversal(right);
}
}
/**
* 獲取左子節點
*
* @param parent 父節點引用
* @return 左子節點或者null--表示沒有左子節點
*/
public BinaryTreeNode<E> getLeft(BinaryTreeNode<E> parent) {
return parent == null ? null : parent.left;
}
/**
* 獲取右子節點
*
* @param parent 父節點引用
* @return 右子節點或者null--表示沒有右子節點
*/
public BinaryTreeNode<E> getRight(BinaryTreeNode<E> parent) {
return parent == null ? null : parent.right;
}
/**
* 獲取根節點
*
* @return 根節點 ;或者null--表示空樹
*/
public BinaryTreeNode<E> getRoot() {
return root;
}
}
2.2 查找的方法
查找的方法很簡單：
- 若根節點的關鍵字值等於查找的關鍵字，成功，返回true；
- 否則，若小於根節點的關鍵字值，遞歸查左子樹；
- 若大於根節點的關鍵字值，遞歸查右子樹；
- 最終查找到葉子節點還是沒有數據，那麼查找失敗，則返回false。
/**
* 查找,開放給外部使用的api
*/
public boolean contains(E e) {
return contains(e, root);
}
/**
* 查找,內部調用的方法,從根節點開始查找
*
* @param e 要查找的元素
* @param root 節點
* @return false 不存在 true 存在
*/
private boolean contains(E e, BinaryTreeNode<E> root) {
/*null校驗*/
if (root == null) {
return false;
}
/*調用比較的方法*/
int i = compare(e, root.data);
/*如果大於0，則說明e>root.date 繼續查詢右子樹*/
if (i > 0) {
return contains(e, root.right);
/*如果小於0，則說明e<root.date 繼續查詢左子樹*/
} else if (i < 0) {
return contains(e, root.left);
} else {
/*如果等於0，則說明e=root.date 即查詢成功*/
return true;
}
}
2.3 插入的方法
有瞭二叉排序樹的查找函數，那麼所謂的二叉排序樹的插入，其實也就是將關鍵字放到樹中的合適位置而已，插入操作就好像在調用查找的操作，如果找到瞭那麼什麼都不做，返回false，如果沒找到，則將要插入的元素插入到遍歷的路徑的最後一點上：
- 若二叉樹為空。則單獨生成根節點，返回true。
- 執行查找算法，找出被插節點的父親節點。
- 判斷被插節點是其父親節點的左、右兒子。將被插節點作為葉子節點插入，返回true。如果原節點存在那麼什麼都不做，返回false。註意：新插入的節點總是葉子節點。
/**
* 插入,開放給外部使用的api
*
* @param e 要插入的元素
*/
public void insert(E e) {
//返回root,但此時新的節點可能已經被插入進去瞭
root = insert(e, root);
}
/**
* 插入,開放給外部使用的api
*
* @param es 要插入的元素的數組,註意,數組元素的順序存儲的位置將會影響二叉排序樹的生成
*/
public void insert(E[] es) {
//返回root,但此時新的節點可能已經被插入進去瞭
for (E e : es) {
root = insert(e, root);
}
}
/**
* 插入,內部調用的方法,先從根節點開始遞歸查找要插入的位置,然後插入
*
* @param e 要插入的數據
* @param root 節點
* @return 原節點或者新插入的節點
*/
private BinaryTreeNode<E> insert(E e, BinaryTreeNode<E> root) {
/*沒有查找到,那麼直接構建新的節點返回,將會在上一層方法中被賦值給其父節點的某個引用,這個插入的位置肯定是該遍歷路徑上的最後一點
* 即插入的元素節點肯定是屬於葉子節點*/
if (root == null) {
size++;
return new BinaryTreeNode<>(e);
}
/*調用比較的方法*/
int i = compare(e, root.data);
/*如果大於0，則說明e>root.date 繼續查詢右子樹*/
if (i > 0) {
//重新賦值
root.right = insert(e, root.right);
/*如果小於0，則說明e<root.date 繼續查詢左子樹*/
} else if (i < 0) {
//重新賦值
root.left = insert(e, root.left);
} else {
/*如果等於0，則說明e=root.date 即存在節點 什麼都不做*/
}
//沒查詢到最底層,則返回該節點
return root;
}
2.3.1 測試
現在我們想要構建如下一顆排序二叉樹：
首先要插入根節點47，然後是第二層的節點16、73，然後是第三層的節點1、24、59、88，然後是第四層的節點20、35、62、77。每一層內部節點的順序可以不一致，但是每一層之間的大順序一定要保持一致，否則雖然中序遍歷輸出的時候能夠正常輸出，但是樹的結構不能保證。
public class BinarySearchTreeTest {
BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
@Test
public void insert() {
//首先要插入根節點47，然後是第二層的節點16,73，然後是第三層的節點1,24,59,88，然後是第四層的節點20,35,62,77。
// 每一層內部節點的順序可以不一致，但是每一層之間的打順序一定要保持一致，否則雖然中序遍歷輸出的時候能夠正常輸出,但是樹的結構不能保證。
Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};
binarySearchTree.insert(es);
//中序遍歷輸出
System.out.println(binarySearchTree.toInorderTraversalString());
//查找某個數據是否存在
System.out.println(binarySearchTree.contains(1));
System.out.println(binarySearchTree.contains(2));
}
}
在System.out處打上斷點，Debug，可以看到樹結構和我們預想的一致，如果改變層間的大順序，那麼使用Debug會發現樹結構不如預期。
2.4 查找最大值和最小值
很簡單，最左邊的節點一定是最小的，最右邊的節點一定是最大的。因此查找最小的節點隻需要向左遞歸查找，查找最大的節點隻需要向右遞歸查找。
/**
* 查找最小的節點
*
* @param root 根節點
* @return 最小的節點
*/
private BinaryTreeNode<E> findMin(BinaryTreeNode<E> root) {
if (root == null) {
return null;
/*如果該節點沒有左右子節點，那麼該節點就是最小的節點，返回*/
} else if (root.left == null) {
return root;
}
/*如果該節點存在左子節點，那麼繼續向左遞歸查找*/
return findMin(root.left);
}
/**
* 查找最大的節點
*
* @param root 根節點
* @return 最大的節點
*/
private BinaryTreeNode<E> findMax(BinaryTreeNode<E> root) {
if (root == null) {
return null;
/*如果該節點沒有右子節點，那麼該節點就是最大的節點，返回*/
} else if (root.right == null) {
return root;
}
/*如果該節點存在右子節點，那麼繼續向右遞歸查找*/
return findMax(root.right);
}
2.5 刪除的方法
對於二叉排序樹的刪除，就不是那麼容易，我們不能因為刪除瞭節點，而讓這棵樹變得不滿足二叉排序樹的特性，所以刪除需要考慮多種情況。一共有三種情況需要考慮：
如果查找到的將要被刪除的節點沒有子節點，那麼很簡單，直接刪除父節點對於該節點的引用即可，如下圖的紅色節點：
例如，刪除20之後：
如果查找到的將要被刪除的節點具有一個子節點，那麼也很簡單，直接繞過該節點將原本父節點對於該節點的引用指向該節點的子節點即可，如下圖的紅色節點：
例如，刪除59之後：
如果查找到的將要被刪除的節點具有兩個子節點，那麼就比較麻煩瞭，如下圖的紅色節點：
比如我們需要刪除73，那麼我們就必須要找出一個已存在的能夠替代73的節點，然後刪除該節點。實際上該73節點的左子樹的最大節點62和右子樹的最小節點77都能夠替代73節點，即它們正好是二叉排序樹中比它小或比它大的最接近73的兩個數。
一般我們選擇一種方式即可，我們這次使用右子樹的最小節點替代要刪除的節點，使用77替代73之後的結構如下：
完整的代碼如下：
/**
* 刪除,開放給外部使用的api
*
* @param e 要刪除的元素
*/
public void delete(E e) {
//返回root,但此時可能有一個節點已經被刪除瞭
root = delete(e, root);
}
/**
* 刪除,內部調用的方法,刪除分為三種情況: 1、該節點沒有子節點 2、該字節僅有一個子節點 3、該節點具有兩個子節點
*
* @param e 要刪除的數據
* @param root 根節點
* @return 該節點
*/
private BinaryTreeNode<E> delete(E e, BinaryTreeNode<E> root) {
/*沒有查找到,那麼什麼都不做*/
if (root == null) {
return null;
}
/*調用比較的方法*/
int i = compare(e, root.data);
/*如果大於0，則說明e>root.date 繼續查詢右子樹*/
if (i > 0) {
//從新賦值
root.right = delete(e, root.right);
/*如果小於0，則說明e<root.date 繼續查詢左子樹*/
} else if (i < 0) {
//從新賦值
root.left = delete(e, root.left);
} else {
/*如果等於0，則說明e=root.date 即查詢成功 開始執行刪除*/
/*如果兩個子節點都不為null*/
if (root.left != null && root.right != null) {
/*方法1、遞歸查找最小的節點，然後遞歸刪除 該方法不推薦使用*/
//root.data = findMin(root.right).data;
//root.right = delete(root.data, root.right);
/*方法2、遞歸查找並刪除最小的節點 推薦*/
root.data = findAndDeleteMin(root.right, root);
size--;
} else {
/*如果一個子節點不為null，則返回該子節點；或者兩個子節點都為null，則返回null
* 此時該root節點已經被"繞過瞭"*/
root = (root.left != null) ? root.left : root.right;
size--;
}
}
//沒查詢到最底層,則返回該節點
return root;
}
/**
* 查找最小的節點並刪除
* 最小的節點肯定不存在兩個子節點,有可能沒有子節點,有可能存在右子節點
*
* @param root 節點
* @param parent 節點的父節點
* @return 被刪除的最小的節點
*/
private E findAndDeleteMin(BinaryTreeNode<E> root, BinaryTreeNode<E> parent) {
//如果節點為null，返回
if (root == null) {
return null;
/*如果節點的左子節點為null,那麼該節點就是最小的節點*/
/*1、該最小節點肯定沒有左子節點，因為左子節點比父節點小，但是可能有右子節點*/
/*2、此時該節點可能作為某個節點的左子節點，也可能作為原父節點的右子節點（即右子樹是一顆右斜樹），這裡需要分開討論*/
} else if (root.left == null) {
//如果該節點是父節點的右子節點,說明還沒進行遞歸或者第一次遞歸就找到瞭最小節點.
//那麼此時,應該讓該節點的父節點的右子節點指向該節點的右子節點,並返回該節點的數據，該節點由於沒有瞭強引用，會被GC刪除
if (root == parent.right) {
parent.right = root.right;
} else {
//如果該節點不是父節點的右子節點，說明進行瞭多次遞歸。
//那麼此時,應該讓該節點的父節點的左子節點指向該節點的右子節點,並返回該節點的數據，該節點由於沒有瞭強引用，會被GC刪除
parent.left = root.right;
}
//返回最小節點的數據
return root.data;
}
//遞歸調用,註意此時是往左查找
return findAndDeleteMin(root.left, root);
}
2.5.1 測試
public class BinarySearchTreeTest {
BinarySearchTree<Integer> binarySearchTree = new BinarySearchTree<>();
@Test
public void test() {
//首先要插入根節點47，然後是第二層的節點16,73，然後是第三層的節點1,24,59,88，然後是第四層的節點20,35,62,77。
// 每一層內部節點的順序可以不一致，但是每一層之間的打順序一定要保持一致，否則雖然中序遍歷輸出的時候能夠正常輸出,但是樹的結構不能保證。
Integer[] es = new Integer[]{47, 16, 73, 1, 24, 59, 88, 20, 35, 62, 77};
binarySearchTree.insert(es);
//中序遍歷輸出
System.out.println(binarySearchTree.toInorderTraversalString());
//查找是否存在
System.out.println(binarySearchTree.contains(1));
System.out.println(binarySearchTree.contains(2));
//移除
binarySearchTree.delete(73);
//中序遍歷輸出
System.out.println(binarySearchTree.toInorderTraversalString());
}
}
3 二叉排序樹的總結
總之，二叉排序樹是以鏈接的方式存儲，保持瞭鏈接存儲結構在執行插入或刪除操作時不用移動元素的優點，隻要找到合適的插入和刪除位置後，僅需修改鏈接指針即可。
插入刪除的時間性能比較好。而對於二叉排序樹的查找，走的就是從根節點到要查找的節點的路徑，其比較次數等於給定值的節點在二叉排序樹的層數。極端情況，最少為1次，即根節點就是要找的節點，最多也不會超過樹的深度。也就是說，二叉排序樹的查找性能取決於二叉排序樹的形狀。可問題就在於，二叉排序樹的形狀是不確定的。
例如{47, 16, 73, 1, 24, 59, 88}這樣的數組，我們可以構建下圖左的二叉排序樹。但如果數組元素的次序是從小到大有序，如{1, 16, 24, 47, 59, 73, 88}，則二叉排序樹就成瞭極端的右斜樹，註意它依然是一棵二叉排序樹，如下圖右。此時，同樣是查找節點88，左圖隻需要3次比較，而右圖就需要7次比較才可以得到結果，二者差異很大。
也就是說，我們希望二叉排序樹是比較平衡的，即其深度與完全二叉樹相同，均為|log2n+1|(|x|表示不大於x的最大整數)，那麼查找的時間復雜也就為O(logn)，近似於折半查找，事實上，上圖的左圖也不夠平衡，明顯的左重右輕。而極端情況下的右圖,則完全退化成為鏈表，查找的時間復雜度為O(n)，這等同於順序查找。
因此，如果我們希望對一個集合按二叉排序樹查找，最好是把它構建成一棵平衡的二叉排序樹，防止極端情況的發生。這樣我們就引申出另一個問題，如何讓二叉排序樹平衡的問題。關於這個問題，在後續的平衡二叉樹（AVL樹)的部分將會詳細解釋！
以上就是Java數據結構之二叉排序樹的實現的詳細內容，更多關於Java二叉排序樹的資料請關註WalkonNet其它相關文章！