Java數(shù)據(jù)結構之二叉查找樹的實現(xiàn)
更新時間：2022年03月28日 15:49:13 作者：gonghr
二叉查找樹（亦稱二叉搜索樹、二叉排序樹）是一棵二叉樹，且各結點關鍵詞互異，其中根序列按其關鍵詞遞增排列。本文將通過示例詳細講解二叉查找樹，感興趣的可以了解一下
定義
二叉查找樹（亦稱二叉搜索樹、二叉排序樹）是一棵二叉樹，且各結點關鍵詞互異，其中根序列按其關鍵詞遞增排列。
等價描述：二叉查找樹中任一結點 P，其左子樹中結點的關鍵詞都小于 P 的關鍵詞，右子樹中結點的關鍵詞都大于 P 的關鍵詞，且結點 P 的左右子樹也都是二叉查找樹
節(jié)點結構
:one: key：關鍵字的值
:two: value：關鍵字的存儲信息
:three: left：左節(jié)點的引用
:four: right：右節(jié)點的引用
class BSTNode<K extends Comparable<K>,V>{
public K key;
public V value;
public BSTNode<K,V> left;
public BSTNode<K,V> right;
}為了代碼簡潔，本文不考慮屬性的封裝，一律設為 public
查找算法
思想：利用二叉查找樹的特性，左子樹值小于根節(jié)點值，右子樹值大于根節(jié)點值，從根節(jié)點開始搜索
- 如果目標值等于某節(jié)點值，返回該節(jié)點
- 如果目標值小于某節(jié)點值，搜索該節(jié)點的左子樹
- 如果目標值大于某節(jié)點值，搜索該節(jié)點的右子樹
:one: 遞歸版本
public BSTNode<K, V> searchByRecursion(K key) {
return searchByRecursion(root, key);
}
private BSTNode<K, V> searchByRecursion(BSTNode<K, V> t, K key) {
if (t == null || t.key == key) return t;
else if (key.compareTo(t.key) < 0) return searchByRecursion(t.left, key);
else return searchByRecursion(t.right, key);
}:two: 迭代版本
public BSTNode<K,V> searchByIteration(K key) {
BSTNode<K,V> p = this.root;
while(p != null) {
if(key.compareTo(p.key) < 0) p = p.left;
else if(key.compareTo(p.key) > 0) p = p.right;
else return p;
}
return null;
}插入算法
- 在以
t為根的二叉查找樹中插入關鍵詞為key的結點 - 在
t中查找key，在查找失敗處插入
:one: 遞歸版本
public void insertByRecursion(K key, V value) {
this.root = insertByRecursion(root, key, value);
}
private BSTNode<K, V> insertByRecursion(BSTNode<K, V> t, K key, V value) {
if (t == null) {
return new BSTNode<>(key, value);
}
else if (key.compareTo(t.key) < 0) t.left = insertByRecursion(t.left, key, value);
else if (key.compareTo(t.key) > 0) t.right = insertByRecursion(t.right, key, value);
else {
t.value = value; // 如果二叉查找樹中已經(jīng)存在關鍵字，則替換該結點的值
}
return t;
}:two: 迭代版本
public void insertByIteration(K key, V value) {
BSTNode<K, V> p = root;
if (p == null) {
root = new BSTNode<>(key, value);
return;
}
BSTNode<K, V> pre = null;
while (p != null) {
pre = p;
if (key.compareTo(p.key) < 0) p = p.left;
else if (key.compareTo(p.key) > 0) p = p.right;
else {
p.value = value; // 如果二叉查找樹中已經(jīng)存在關鍵字，則替換該結點的值
return;
}
}
if(key.compareTo(pre.key) < 0) {
pre.left = new BSTNode<>(key, value);
} else {
pre.right = new BSTNode<>(key, value);
}
}刪除算法
在以 t 為根的二叉查找樹中刪除關鍵詞值為 key 的結點
在 t 中找到關鍵詞為 key 的結點，分三種情況刪除 key
1.若 key 是葉子節(jié)點，則直接刪除
2.若 key 只有一棵子樹，則子承父業(yè)
3.若 key 既有左子樹也有右子樹，則找到 key 的后繼結點，替換 key 和后繼節(jié)點的值，然后刪除后繼節(jié)點（后繼節(jié)點只有一棵子樹，轉化為第二種情況）。
后繼結點是當前結點的右子樹的最左結點，如果右子樹沒有左子樹，則后繼節(jié)點就是右子樹的根節(jié)點。
public void removeByRecursion(K key) {
this.root = removeByRecursion(root, key);
}
private BSTNode<K, V> removeByRecursion(BSTNode<K, V> t, K key) {
if(t == null) return root;
else if(t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大，遞歸處理右子樹
else if(t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key); // key小，遞歸處理左子樹
else {
if(t.right == null) return t.left; // 情況一、二一起處理
if(t.left == null) return t.right; // 情況一、二一起處理
BSTNode<K, V> node = t.right; // 情況三：右子樹沒有左子樹
if (node.left == null) {
node.left = t.left;
} else { // 情況三：右子樹有左子樹
BSTNode<K, V> pre = null;
while (node.left != null) {
pre = node;
node = node.left;
}
t.key = node.key;
t.value = node.value;
pre.left = node.right;
}
}
return t;
}完整代碼
class BSTNode<K extends Comparable<K>, V> {
public K key;
public V value;
public BSTNode<K, V> left;
public BSTNode<K, V> right;
public BSTNode(K key, V value) {
this.key = key;
this.value = value;
}
}
class BSTree<K extends Comparable<K>, V> {
public BSTNode<K, V> root;
private void inorder(BSTNode<K, V> root) {
if (root != null) {
inorder(root.left);
System.out.print("(key: " + root.key + " , value: " + root.value + ") ");
inorder(root.right);
}
}
private void preorder(BSTNode<K, V> root) {
if (root != null) {
System.out.print("(key: " + root.key + " , value: " + root.value + ") ");
preorder(root.left);
preorder(root.right);
}
}
private void postorder(BSTNode<K, V> root) {
if (root != null) {
postorder(root.left);
postorder(root.right);
System.out.print("(key: " + root.key + " , value: " + root.value + ") ");
}
}
public void postorderTraverse() {
System.out.print("后序遍歷：");
postorder(root);
System.out.println();
}
public void preorderTraverse() {
System.out.print("先序遍歷：");
preorder(root);
System.out.println();
}
public void inorderTraverse() {
System.out.print("中序遍歷：");
inorder(root);
System.out.println();
}
public BSTNode<K, V> searchByRecursion(K key) {
return searchByRecursion(root, key);
}
private BSTNode<K, V> searchByRecursion(BSTNode<K, V> t, K key) {
if (t == null || t.key == key) return t;
else if (key.compareTo(t.key) < 0) return searchByRecursion(t.left, key);
else return searchByRecursion(t.right, key);
}
public BSTNode<K, V> searchByIteration(K key) {
BSTNode<K, V> p = this.root;
while (p != null) {
if (key.compareTo(p.key) < 0) p = p.left;
else if (key.compareTo(p.key) > 0) p = p.right;
else return p;
}
return null;
}
public void insertByRecursion(K key, V value) {
this.root = insertByRecursion(root, key, value);
}
private BSTNode<K, V> insertByRecursion(BSTNode<K, V> t, K key, V value) {
if (t == null) {
return new BSTNode<>(key, value);
} else if (key.compareTo(t.key) < 0) t.left = insertByRecursion(t.left, key, value);
else if (key.compareTo(t.key) > 0) t.right = insertByRecursion(t.right, key, value);
else {
t.value = value;
}
return t;
}
public void insertByIteration(K key, V value) {
BSTNode<K, V> p = root;
if (p == null) {
root = new BSTNode<>(key, value);
return;
}
BSTNode<K, V> pre = null;
while (p != null) {
pre = p;
if (key.compareTo(p.key) < 0) p = p.left;
else if (key.compareTo(p.key) > 0) p = p.right;
else {
p.value = value; // 如果二叉查找樹中已經(jīng)存在關鍵字，則替換該結點的值
return;
}
}
if (key.compareTo(pre.key) < 0) {
pre.left = new BSTNode<>(key, value);
} else {
pre.right = new BSTNode<>(key, value);
}
}
public void removeByRecursion(K key) {
this.root = removeByRecursion(root, key);
}
private BSTNode<K, V> removeByRecursion(BSTNode<K, V> t, K key) {
if(t == null) return root;
else if(t.key.compareTo(key) < 0) t.right = removeByRecursion(t.right, key); // key大，遞歸處理右子樹
else if(t.key.compareTo(key) > 0) t.left = removeByRecursion(t.left, key); // key小，遞歸處理左子樹
else {
if(t.right == null) return t.left; // 情況一、二一起處理
if(t.left == null) return t.right; // 情況一、二一起處理
BSTNode<K, V> node = t.right; // 情況三：右子樹沒有左子樹
if (node.left == null) {
node.left = t.left;
} else { // 情況三：右子樹有左子樹
BSTNode<K, V> pre = null;
while (node.left != null) {
pre = node;
node = node.left;
}
t.key = node.key;
t.value = node.value;
pre.left = node.right;
}
}
return t;
}
}:bug: 方法測試：
public class Main {
public static void main(String[] args) {
BSTree<Integer, Integer> tree = new BSTree<>();
// tree.insertByRecursion(1, 1);
// tree.insertByRecursion(5, 1);
// tree.insertByRecursion(2, 1);
// tree.insertByRecursion(4, 1);
// tree.insertByRecursion(3, 1);
// tree.insertByRecursion(1, 2);
tree.insertByIteration(1, 1);
tree.insertByIteration(5, 1);
tree.insertByIteration(2, 1);
tree.insertByIteration(4, 1);
tree.insertByIteration(3, 1);
tree.insertByIteration(1, 5);
tree.removeByRecursion(4);
tree.inorderTraverse();
tree.postorderTraverse();
tree.preorderTraverse();
BSTNode<Integer, Integer> node = tree.searchByIteration(1);
System.out.println(node.key + " " + node.value);
}
}
中序遍歷：(key: 1 , value: 5) (key: 2 , value: 1) (key: 3 , value: 1) (key: 5 , value: 1)
后序遍歷：(key: 3 , value: 1) (key: 2 , value: 1) (key: 5 , value: 1) (key: 1 , value: 5)
先序遍歷：(key: 1 , value: 5) (key: 5 , value: 1) (key: 2 , value: 1) (key: 3 , value: 1)
1 5
以上就是Java數(shù)據(jù)結構之二叉查找樹的實現(xiàn)的詳細內容，更多關于Java二叉查找樹的資料請關注腳本之家其它相關文章！
相關文章
這篇文章主要介紹了一文帶你徹底搞懂Lambda表達式，具有很好的參考價值，希望對大家有所幫助。一起跟隨小編過來看看吧2020-09-09
這篇文章主要介紹了spring集成redis cluster詳解，分享了maven依賴，Spring配置，增加connect-redis.properties 配置文件等相關內容，具有一定參考價值，需要的朋友可以了解下。2017-11-11
Java Idea TranslationPlugin翻譯插件使用解析
這篇文章主要介紹了Java Idea TranslationPlugin翻譯插件使用解析,文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值,需要的朋友可以參考下2020-04-04
SpringBoot集成xxl-job實現(xiàn)超牛的定時任務的步驟詳解
XXL-JOB是一個分布式任務調度平臺,其核心設計目標是開發(fā)迅速、學習簡單、輕量級、易擴展,現(xiàn)已開放源代碼并接入多家公司線上產(chǎn)品線,開箱即用,本文給大家介紹了SpringBoot集成xxl-job實現(xiàn)超牛的定時任務,需要的朋友可以參考下2023-10-10
本文主要介紹了Mybatis實現(xiàn)ResultMap結果集，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2022-04-04
這篇文章主要介紹了ArrayList源碼和多線程安全問題，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，下面小編和大家一起來學習一下吧2019-05-05
作為后端開發(fā)人員，我們總是在編寫各種API。這些API在服務初期可能表現(xiàn)不錯，但隨著用戶數(shù)量的增長，一開始響應很快的API越來越慢，這時候你就需要考慮如何優(yōu)化你的API性能了。在這篇文章中，我總結了一些行之有效的API性能優(yōu)化技巧，希望能給有需要的朋友一些幫助2023-01-01
Java中的FileInputStream 和 FileOutputStream 介紹_動力節(jié)點Java學院整理
FileInputStream 是文件輸入流，它繼承于InputStream。FileOutputStream 是文件輸出流，它繼承于OutputStream。接下來通過本文給大家介紹Java中的FileInputStream 和 FileOutputStream,需要的朋友可以參考下2017-05-05
這篇文章主要介紹了JavaWeb讀取配置文件的4種方法,方法一采用ServletContext讀取，方法二采用ResourceBundle類讀取配置信息,方法三采用ClassLoader方式進行讀取配置信息，對javaweb讀取配置文件的四種方法感興趣的朋友參考下吧2018-03-03
Springboot基于BCrypt非對稱加密字符串的實現(xiàn)
本文主要介紹了Springboot基于BCrypt非對稱加密字符串的實現(xiàn)，文中通過示例代碼介紹的非常詳細，對大家的學習或者工作具有一定的參考學習價值，需要的朋友們下面隨著小編來一起學習學習吧2023-04-04