溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
這篇文章將為大家詳細講解有關Java如何實現二分搜索樹，小編覺得挺實用的，因此分享給大家做個參考，希望大家閱讀完這篇文章后可以有所收獲。
a.是個二叉樹(每個節點最多有兩個子節點)
b.對于這棵樹中的節點的節點值
左子樹中的所有節點值 < 根節點 < 右子樹的所有節點值
二分搜索樹中一般不考慮值相等的情況(元素不重復)JDK中的搜索樹就不存在相同的值(TreeMap-key)
最大特點:也是判斷是否是搜索樹的方法
對該樹進行中序遍歷，就可以得到一個升序集合0 1 2 3 4 5 6 7 8 9
在一個有序區間上進行二分查找的時間復雜度? logn不斷將集合/2/2 / 2 ==1為止logN
logN =》聯想到"樹"
當刪除58時，此節點左右子樹都不為空
Hibbard Deletion 1962
在BST中刪除一個左右子樹都存在的節點
找到當前以58為根節點的前驅或者后繼節點作為刪除后的新節點
前驅:在以58為根的BST中最后一個小于58的節點->53
后繼:在以58為根的BST中第一個大于58的節點->59
當我們使用后繼節點時，先連removeMin(root.right),在連root.left
TreeNode successor = findMin(root.right); successor.right = removeMin(root.right); successor.left = root.left;
import java.util.NoSuchElementException;
/**
* 基于整型的
* 普通的二分搜索樹
*/
public class BST {
private class TreeNode{
private int val;
private TreeNode left;
private TreeNode right;
public TreeNode(int val) {
this.val = val;
}
}
private int size;
private TreeNode root;
/**
* 向以root為根的BST中插入一個新的結點val
* @param val
*/
public void add(int val){
root = add(root,val);
}
private TreeNode add(TreeNode root, int val) {
if(root == null){
//創建一個新節點
TreeNode newNode = new TreeNode(val);
size++;
return newNode;
}
//左子樹插入
if(val < root.val){
root.left = add(root.left,val);
}
//右子樹插入
if(val > root.val){
root.right = add(root.right,val);
}
return root;
}
/**
* 判斷當前以root為根的BST中是否包含了val
* @param val
* @return
*/
public boolean contains(int val){
return contains(root,val);
}
private boolean contains(TreeNode root, int val) {
if(root == null){
return false;
}
if(val == root.val){
//找到了
return true;
}else if(val < root.val){
//遞歸左子樹查找
return contains(root.left,val);
}else{
//遞歸右子樹查找
return contains(root.right,val);
}
}
/**
* 找到最小值
* @return
*/
public int findMin(){
//判空
if(root == null){
//拋出一個空指針異常
throw new NoSuchElementException("root is empty! cannot find min");
}
TreeNode minNode = findMin(root);
return minNode.val;
}
private TreeNode findMin(TreeNode root) {
//當此節點左子樹為空，說明此節點是最小值
if(root.left == null){
return root;
}
//遞歸訪問左子樹
return findMin(root.left);
}
/**
* 找到最大值
* @return
*/
public int findMax(){
//判空
if(root == null){
throw new NoSuchElementException("root is empty! cannot find max");
}
TreeNode maxNode = findMax(root);
return maxNode.val;
}
private TreeNode findMax(TreeNode root) {
//當此節點右子樹為空，說明此節點是最大值
if(root.right == null){
return root;
}
//遞歸訪問右子樹
return findMax(root.right);
}
/**
* 在當前BST中刪除最小值節點，返回刪除的最小值
* @return
*/
public int removeMin(){
int min =findMin();
root = removeMin(root);
return min;
}
private TreeNode removeMin(TreeNode root) {
if(root.left == null){
TreeNode right = root.right;
//找到最小值，刪除節點
root = root.left = null;
size--;
return right;
}
root.left = removeMin(root.left);
return root;
}
/**
* 在當前BST中刪除最大值節點，返回刪除的最大值
* @return
*/
public int removeMax(){
int max = findMax();
root = removeMax(root);
return max;
}
//在當前以root為根的BST中刪除最小值所在的節點，返回刪除后的樹根
private TreeNode removeMax(TreeNode root) {
if(root.right == null){
TreeNode right = root.right;
//找到最大值，刪除節點
root = root.right = null;
size--;
return right;
}
root.right = findMax(root.right);
return root;
}
/**
* 在當前以root為根節點的BST中刪除值為val的節點
* 返回刪除后的新的根節點
* @return
*/
public void removeValue(int value){
root = removeValue(root,value);
}
private TreeNode removeValue(TreeNode root, int value) {
if(root == null){
throw new NoSuchElementException("root is empty! cannot find remove");
}else if(value < root.val){
root.left = removeValue(root.left,value);
return root;
}else if(value > root.val){
root.right = removeValue(root.right,value);
return root;
}else {
//此時value == root.value
if(root.left == null){
//刪除最小數
TreeNode right = root.right;
root = root.right = null;
size--;
return right;
}
if(root.right == null){
//刪除最大數
TreeNode left = root.left;
root = root.left =null;
size--;
return left;
}
//找到當前該刪除節點的前驅或者后繼節點作為刪除后的新節點
//當我們使用后繼節點時，先連removeMin(root.right),在連root.left
TreeNode successor = findMin(root.right);
successor.right = removeMin(root.right);
successor.left = root.left;
return successor;
}
}
@Override
public String toString() {
StringBuilder sb = new StringBuilder();
generateBSTString(root,0,sb);
return sb.toString();
}
//直觀打印，可以看到樹的深度
private void generateBSTString(TreeNode root, int height, StringBuilder sb) {
if(root == null){
sb.append(generateHeightString(height)).append("NULL\n");
return;
}
sb.append(generateHeightString(height)).append(root.val).append("\n");
generateBSTString(root.left,height+1,sb);
generateBSTString(root.right,height+1,sb);
}
private String generateHeightString(int height) {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < height; i++) {
sb.append("--");
}
return sb.toString();
}
}關于“Java如何實現二分搜索樹”這篇文章就分享到這里了，希望以上內容可以對大家有一定的幫助，使各位可以學到更多知識，如果覺得文章不錯，請把它分享出去讓更多的人看到。
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
