溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章給大家分享的是有關Java如何實現二叉排序樹的內容。小編覺得挺實用的，因此分享給大家做個參考，一起跟隨小編過來看看吧。
對于常見查找算法，比如順序查找、二分查找、插入查找、斐波那契查找還不清楚的，可以看這篇文章：常見查找算法詳解以及Java代碼的實現。
假設查找的數據集是普通的順序存儲，那么插入操作就是將記錄放在表的末端，給表記錄數加一即可，刪除操作可以是刪除后，后面的記錄向前移，也可以是要刪除的元素與最后一個元素互換，表記錄數減一，反正整個數據集也沒有什么順序，這樣的效率也不錯。應該說，插入和刪除對于順序存儲結構來說，效率是可以接受的，但這樣的表由于無序造成查找的效率很低。
如果查找的數據集是有序線性表，并且是順序存儲的，查找可以用折半、插值、斐波那契等查找算法來實現，可惜，因為有序，在插入和刪除操作上，為了維持順序，需要移動大量元素，就需要耗費大量的時間。
有沒有一種即可以使得插入和刪除效率不錯，又可以比較高效率地實現查找的算法呢？這就是二叉排序樹。
二叉排序樹（Binary Sort Tree），又稱為二叉查找樹/二叉搜索樹（binary search tree）。它是具有下列性質的二叉樹：
若它的左子樹不空，則左子樹上所有節點的值均小于它的根結構的值；
若它的右子樹不空，則右子樹上所有節點的值均大于它的根節點的值；
它的左、右子樹也分別為二叉排序樹；
二叉排序樹也可以是一個空樹。
構造一棵二叉排序樹的目的，其主要目的并不是為了排序，而是為了提高查找和插入刪除關鍵字的速度，用以提升數據結構的綜合能力。不管怎么說，在一個有序數據集上的查找，速度總是要快于無序的數據集的，而二叉排序樹這種非線性的結構，也有利于插入和刪除的實現。
首先，最簡單的節點對象還是需要一個數據域和兩個引用域。
另外還需要一個比較器的引用，因為需要對元素進行排序，自然需要比較元素的大小，如果外部傳遞了比較器，那么就使用用戶指定的比較器進行比較，否則，數據類型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;
}
}查找的方法很簡單：
若根節點的關鍵字值等于查找的關鍵字，成功，返回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;
}
}有了二叉排序樹的查找函數，那么所謂的二叉排序樹的插入，其實也就是將關鍵字放到樹中的合適位置而已，插入操作就好像在調用查找的操作，如果找到了那么什么都不做，返回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會發現樹結構不如預期。
很簡單，最左邊的節點一定是最小的，最右邊的節點一定是最大的。因此查找最小的節點只需要向左遞歸查找，查找最大的節點只需要向右遞歸查找。
/**
* 查找最小的節點
*
* @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);
}對于二叉排序樹的刪除，就不是那么容易，我們不能因為刪除了節點，而讓這棵樹變得不滿足二叉排序樹的特性，所以刪除需要考慮多種情況。一共有三種情況需要考慮：
如果查找到的將要被刪除的節點沒有子節點，那么很簡單，直接刪除父節點對于該節點的引用即可，如下圖的紅色節點：
例如，刪除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());
}
}總之，二叉排序樹是以鏈接的方式存儲，保持了鏈接存儲結構在執行插入或刪除操作時不用移動元素的優點，只要找到合適的插入和刪除位置后，僅需修改鏈接指針即可。
插入刪除的時間性能比較好。而對于二叉排序樹的查找，走的就是從根節點到要查找的節點的路徑，其比較次數等于給定值的節點在二叉排序樹的層數。極端情況，最少為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如何實現二叉排序樹”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，讓大家可以學到更多知識，如果覺得文章不錯，可以把它分享出去讓更多的人看到吧！
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
