java-二元查找樹(BST)演算法的範例程式碼分享
二元查找樹(Binary Search Tree)是一種能將鍊錶插入的靈活性和有序數組查找的高效性結合起來的演算法。以下是實作BST各種方法的乾貨純程式碼。
二元尋找樹(BST)定義
#二元排序樹或是一棵空樹,或者是具有下列性質的二元樹:
若左子樹不空,則左子樹上所有結點的值均小於或等於它的根結點的值
#若右子樹不空,則右子樹上所有結點的值均大於或等於它的根結點的值
- ##左、右子樹也
分別為二元排序樹
基本結點實作public class BST<K extends Comparable<K>, V> {
private Node root;
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;
}
}
public int size() {
return size(root);
}
private int size(Node x) {
if (x == null)
return 0;
else
return x.N;
}
}
登入後複製
public class BST<K extends Comparable<K>, V> { private Node root; 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; } } public int size() { return size(root); } private int size(Node x) { if (x == null) return 0; else return x.N; } }
查找鍵取得值— getpublic V get(K key) {
return get(root, key);
}
private V get(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp == 0)
return root.value;
else if (comp < 0)
return get(root.left, key);
else
return get(root.right, key);
}
登入後複製
public V get(K key) { return get(root, key); } private V get(Node root, K key) { if (root == null) return null; int comp = key.compareTo(root.key); if (comp == 0) return root.value; else if (comp < 0) return get(root.left, key); else return get(root.right, key); }
修改值/插入新值-put public void put(K key, V value) {
root = put(root, key, value);
}
private Node put(Node root, K key, V value) {
if (root == null)
return new Node(key, value, 1);
int comp = key.compareTo(root.key);
if (comp == 0)
root.value = value;
else if (comp < 0)
root.left = put(root.left, key, value);
else
root.right = put(root.right, key, value);
root.N = size(root.left) + size(root.right) + 1;
return root;
}
登入後複製
public void put(K key, V value) { root = put(root, key, value); } private Node put(Node root, K key, V value) { if (root == null) return new Node(key, value, 1); int comp = key.compareTo(root.key); if (comp == 0) root.value = value; else if (comp < 0) root.left = put(root.left, key, value); else root.right = put(root.right, key, value); root.N = size(root.left) + size(root.right) + 1; return root; }
最大值/最小值-min/max public K min() {
return min(root).key;
}
private Node min(Node root) {
if (root.left == null)
return root;
return min(root.left);
}
登入後複製 public K max() {
return max(root).key;
}
private Node max(Node root2) {
if (root.right == null)
return root;
return max(root.right);
}
登入後複製
public K min() { return min(root).key; } private Node min(Node root) { if (root.left == null) return root; return min(root.left); }
public K max() { return max(root).key; } private Node max(Node root2) { if (root.right == null) return root; return max(root.right); }
向上/向下取整-floor/ceiling# public K floor(K key) {
Node x = floor(root, key);
if (x == null)
return null;
return x.key;
}
private Node floor(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp < 0)
return floor(root.left, key);
else if (comp > 0 && root.right != null
&& key.compareTo(min(root.right).key) >= 0)
return floor(root.right, key);
else
return root;
}
登入後複製 public K ceiling(K key) {
Node x = ceiling(root, key);
if (x == null)
return null;
return x.key;
}
private Node ceiling(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp > 0)
return ceiling(root.right, key);
else if (comp < 0 && root.left != null
&& key.compareTo(max(root.left).key) >= 0)
return ceiling(root.left, key);
else
return root;
}
登入後複製
public K floor(K key) { Node x = floor(root, key); if (x == null) return null; return x.key; } private Node floor(Node root, K key) { if (root == null) return null; int comp = key.compareTo(root.key); if (comp < 0) return floor(root.left, key); else if (comp > 0 && root.right != null && key.compareTo(min(root.right).key) >= 0) return floor(root.right, key); else return root; }
public K ceiling(K key) { Node x = ceiling(root, key); if (x == null) return null; return x.key; } private Node ceiling(Node root, K key) { if (root == null) return null; int comp = key.compareTo(root.key); if (comp > 0) return ceiling(root.right, key); else if (comp < 0 && root.left != null && key.compareTo(max(root.left).key) >= 0) return ceiling(root.left, key); else return root; }
選擇-select public K select(int k) {
//找出BST中序号为k的键
return select(root, k);
}
private K select(Node root, int k) {
if (root == null)
return null;
int comp = k - size(root.left);
if (comp < 0)
return select(root.left, k);
else if (comp > 0)
return select(root.right, k - (size(root.left) + 1));
else
return root.key;
}
登入後複製
public K select(int k) { //找出BST中序号为k的键 return select(root, k); } private K select(Node root, int k) { if (root == null) return null; int comp = k - size(root.left); if (comp < 0) return select(root.left, k); else if (comp > 0) return select(root.right, k - (size(root.left) + 1)); else return root.key; }
排名——rank public int rank(K key) {
//找出BST中键为key的序号是多少
return rank(root, key);
}
private int rank(Node root, K key) {
if (root == null)
return 0;
int comp = key.compareTo(root.key);
if (comp == 0)
return size(root.left);
else if (comp < 0)
return rank(root.left, key);
else
return 1 + size(root.left) + rank(root.right, key);
}
登入後複製
public int rank(K key) { //找出BST中键为key的序号是多少 return rank(root, key); } private int rank(Node root, K key) { if (root == null) return 0; int comp = key.compareTo(root.key); if (comp == 0) return size(root.left); else if (comp < 0) return rank(root.left, key); else return 1 + size(root.left) + rank(root.right, key); }
刪除最小/最大鍵——deleteMin/deleteMax public void deleteMin() {
root = deleteMin(root);
}
private Node deleteMin(Node root) {
if (root.left == null)
return root.right;
root.left = deleteMin(root.left);
root.N = size(root.left) + size(root.right) + 1;
return root;
}
登入後複製 public void deleteMax() {
root = deleteMax(root);
}
private Node deleteMax(Node root) {
if (root.right == null)
return root.left;
root.right = deleteMax(root.right);
root.N = size(root.left) + size(root.right) + 1;
return root;
}
登入後複製
public void deleteMin() { root = deleteMin(root); } private Node deleteMin(Node root) { if (root.left == null) return root.right; root.left = deleteMin(root.left); root.N = size(root.left) + size(root.right) + 1; return root; }
public void deleteMax() { root = deleteMax(root); } private Node deleteMax(Node root) { if (root.right == null) return root.left; root.right = deleteMax(root.right); root.N = size(root.left) + size(root.right) + 1; return root; }
刪除任意鍵——delete public void delete(K key) {
root = delete(root, key);
}
private Node delete(Node root, K key) {
if (root == null)
return null;
int comp = key.compareTo(root.key);
if (comp == 0) {
if (root.right == null)
return root = root.left;
if (root.left == null)
return root = root.right;
Node t = root;
root = min(t.right);
root.left = t.left;
root.right = deleteMin(t.right);
} else if (comp < 0)
root.left = delete(root.left, key);
else
root.right = delete(root.right, key);
root.N = size(root.left) + size(root.right) + 1;
return root;
}
登入後複製
public void delete(K key) { root = delete(root, key); } private Node delete(Node root, K key) { if (root == null) return null; int comp = key.compareTo(root.key); if (comp == 0) { if (root.right == null) return root = root.left; if (root.left == null) return root = root.right; Node t = root; root = min(t.right); root.left = t.left; root.right = deleteMin(t.right); } else if (comp < 0) root.left = delete(root.left, key); else root.right = delete(root.right, key); root.N = size(root.left) + size(root.right) + 1; return root; }
中序列印樹-print public void print() {
print(root);
}
private void print(Node root) {
if (root == null)
return;
print(root.left);
System.out.println(root.key);
print(root.right);
}
登入後複製
public void print() { print(root); } private void print(Node root) { if (root == null) return; print(root.left); System.out.println(root.key); print(root.right); }
以上是java-二元查找樹(BST)演算法的範例程式碼分享的詳細內容。更多資訊請關注PHP中文網其他相關文章!

熱AI工具

Undresser.AI Undress
人工智慧驅動的應用程序,用於創建逼真的裸體照片

AI Clothes Remover
用於從照片中去除衣服的線上人工智慧工具。

Undress AI Tool
免費脫衣圖片

Clothoff.io
AI脫衣器

Video Face Swap
使用我們完全免費的人工智慧換臉工具,輕鬆在任何影片中換臉!

熱門文章

熱工具

記事本++7.3.1
好用且免費的程式碼編輯器

SublimeText3漢化版
中文版,非常好用

禪工作室 13.0.1
強大的PHP整合開發環境

Dreamweaver CS6
視覺化網頁開發工具

SublimeText3 Mac版
神級程式碼編輯軟體(SublimeText3)

Java 8引入了Stream API,提供了一種強大且表達力豐富的處理數據集合的方式。然而,使用Stream時,一個常見問題是:如何從forEach操作中中斷或返回? 傳統循環允許提前中斷或返回,但Stream的forEach方法並不直接支持這種方式。本文將解釋原因,並探討在Stream處理系統中實現提前終止的替代方法。 延伸閱讀: Java Stream API改進 理解Stream forEach forEach方法是一個終端操作,它對Stream中的每個元素執行一個操作。它的設計意圖是處

PHP是一種廣泛應用於服務器端的腳本語言,特別適合web開發。 1.PHP可以嵌入HTML,處理HTTP請求和響應,支持多種數據庫。 2.PHP用於生成動態網頁內容,處理表單數據,訪問數據庫等,具有強大的社區支持和開源資源。 3.PHP是解釋型語言,執行過程包括詞法分析、語法分析、編譯和執行。 4.PHP可以與MySQL結合用於用戶註冊系統等高級應用。 5.調試PHP時,可使用error_reporting()和var_dump()等函數。 6.優化PHP代碼可通過緩存機制、優化數據庫查詢和使用內置函數。 7

PHP和Python各有優勢,選擇應基於項目需求。 1.PHP適合web開發,語法簡單,執行效率高。 2.Python適用於數據科學和機器學習,語法簡潔,庫豐富。

膠囊是一種三維幾何圖形,由一個圓柱體和兩端各一個半球體組成。膠囊的體積可以通過將圓柱體的體積和兩端半球體的體積相加來計算。本教程將討論如何使用不同的方法在Java中計算給定膠囊的體積。 膠囊體積公式 膠囊體積的公式如下: 膠囊體積 = 圓柱體體積 兩個半球體體積 其中, r: 半球體的半徑。 h: 圓柱體的高度(不包括半球體)。 例子 1 輸入 半徑 = 5 單位 高度 = 10 單位 輸出 體積 = 1570.8 立方單位 解釋 使用公式計算體積: 體積 = π × r2 × h (4

PHP和Python各有優勢,適合不同場景。 1.PHP適用於web開發,提供內置web服務器和豐富函數庫。 2.Python適合數據科學和機器學習,語法簡潔且有強大標準庫。選擇時應根據項目需求決定。

PHP適合web開發,特別是在快速開發和處理動態內容方面表現出色,但不擅長數據科學和企業級應用。與Python相比,PHP在web開發中更具優勢,但在數據科學領域不如Python;與Java相比,PHP在企業級應用中表現較差,但在web開發中更靈活;與JavaScript相比,PHP在後端開發中更簡潔,但在前端開發中不如JavaScript。

Java是熱門程式語言,適合初學者和經驗豐富的開發者學習。本教學從基礎概念出發,逐步深入解說進階主題。安裝Java開發工具包後,可透過建立簡單的「Hello,World!」程式來實踐程式設計。理解程式碼後,使用命令提示字元編譯並執行程序,控制台上將輸出「Hello,World!」。學習Java開啟了程式設計之旅,隨著掌握程度加深,可創建更複雜的應用程式。
