Java 實(shí)現(xiàn)二叉搜索樹的查找、插入、刪除、遍歷
由于最近想要閱讀下JDK1.8 中HashMap的具體實(shí)現(xiàn)，但是由于HashMap的實(shí)現(xiàn)中用到了紅黑樹，所以我覺得有必要先復(fù)習(xí)下紅黑樹的相關(guān)知識(shí)，所以寫下這篇隨筆備忘，有不對(duì)的地方請(qǐng)指出～
學(xué)習(xí)紅黑樹，我覺得有必要從二叉搜索樹開始學(xué)起，本篇隨筆就主要介紹Java實(shí)現(xiàn)二叉搜索樹的查找、插入、刪除、遍歷等內(nèi)容。
二叉搜索樹需滿足以下四個(gè)條件：
若任意節(jié)點(diǎn)的左子樹不空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值；
若任意節(jié)點(diǎn)的右子樹不空，則右子樹上所有結(jié)點(diǎn)的值均大于它的根結(jié)點(diǎn)的值；
任意節(jié)點(diǎn)的左、右子樹也分別為二叉查找樹；
沒有鍵值相等的節(jié)點(diǎn)。
二叉搜索樹舉例：
圖一
接下來將基于圖一介紹二叉搜索樹相關(guān)操作。
首先，應(yīng)先有一個(gè)節(jié)點(diǎn)對(duì)象相關(guān)的類，命名為 Node。
class Node {
int key;
int value;
Node leftChild;
Node rightChild;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
public void displayNode() {
}
}
Node 類中包含 key 值，用于確定節(jié)點(diǎn)在樹中相應(yīng)位置，value 值代表要存儲(chǔ)的內(nèi)容，還含有指向左右孩子節(jié)點(diǎn)的兩個(gè)引用。
接下來看下搜索樹相應(yīng)的類：
class Tree {
Node root;//保存樹的根
public Node find(int key) {//查找指定節(jié)點(diǎn)
}
public void insert(int key, int value) {//插入節(jié)點(diǎn)
}
public boolean delete(int key) {//刪除指定節(jié)點(diǎn)
}
private Node getDirectPostNode(Node delNode) {//得到待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)
}
public void preOrder(Node rootNode) {//先序遍歷樹
}
public void inOrder(Node rootNode) {//中序遍歷樹
}
public void postOrder(Node rootNode) {//后序遍歷樹
}
}
類中表示樹的框架，包含查找、插入、遍歷、刪除相應(yīng)方法，其中刪除節(jié)點(diǎn)操作最為復(fù)雜，接下來一一介紹。
一、查找某個(gè)節(jié)點(diǎn)
由于二叉搜索樹定義上的特殊性，只需根據(jù)輸入的 key 值從根開始進(jìn)行比較，若小于根的 key 值，則與根的左子樹比較，大于根的key值與根的右子樹比較，以此類推，找到則返回相應(yīng)節(jié)點(diǎn)，否則返回 null。
public Node find(int key) {
Node currentNode = root;
while (currentNode != null && currentNode.key != key) {
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
} else {
currentNode = currentNode.rightChild;
}
}
return currentNode;
}
二、插入節(jié)點(diǎn)
與查找操作相似，由于二叉搜索樹的特殊性，待插入的節(jié)點(diǎn)也需要從根節(jié)點(diǎn)開始進(jìn)行比較，小于根節(jié)點(diǎn)則與根節(jié)點(diǎn)左子樹比較，反之則與右子樹比較，直到左子樹為空或右子樹為空，則插入到相應(yīng)為空的位置，在比較的過程中要注意保存父節(jié)點(diǎn)的信息 及 待插入的位置是父節(jié)點(diǎn)的左子樹還是右子樹，才能插入到正確的位置。
public void insert(int key, int value) {
if (root == null) {
root = new Node(key, value);
return;
}
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (currentNode != null) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
Node newNode = new Node(key, value);
if (isLeftChild) {
parentNode.leftChild = newNode;
} else {
parentNode.rightChild = newNode;
}
}
三、遍歷二叉搜索樹
遍歷操作與遍歷普通二叉樹操作完全相同，不贅述。
public void preOrder(Node rootNode) {
if (rootNode != null) {
System.out.println(rootNode.key + " " + rootNode.value);
preOrder(rootNode.leftChild);
preOrder(rootNode.rightChild);
}
}
public void inOrder(Node rootNode) {
if (rootNode != null) {
inOrder(rootNode.leftChild);
System.out.println(rootNode.key + " " + rootNode.value);
inOrder(rootNode.rightChild);
}
}
public void postOrder(Node rootNode) {
if (rootNode != null) {
postOrder(rootNode.leftChild);
postOrder(rootNode.rightChild);
System.out.println(rootNode.key + " " + rootNode.value);
}
}
四、刪除指定節(jié)點(diǎn)。
在二叉搜索樹中刪除節(jié)點(diǎn)操作較復(fù)雜，可分為以下三種情況。
1、待刪除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)，可直接刪除。
public boolean delete(int key) {
Node currentNode = root;//用來保存待刪除節(jié)點(diǎn)
Node parentNode = root;//用來保存待刪除節(jié)點(diǎn)的父親節(jié)點(diǎn)
boolean isLeftChild = true;//用來確定待刪除節(jié)點(diǎn)是父親節(jié)點(diǎn)的左孩子還是右孩子
while (currentNode != null && currentNode.key != key) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
if (currentNode == null) {
return false;
}
if (currentNode.leftChild == null && currentNode.rightChild == null) {//要?jiǎng)h除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)
if (currentNode == root)
root = null;
else if (isLeftChild)
parentNode.leftChild = null;
else
parentNode.rightChild = null;
}
......
}
2、待刪除節(jié)點(diǎn)只有一個(gè)孩子節(jié)點(diǎn)
例如刪除圖一中的 key 值為 11 的節(jié)點(diǎn)，只需將 key 值為 13 的節(jié)點(diǎn)的左孩子指向 key 值為 12的節(jié)點(diǎn)即可達(dá)到刪除 key 值為 11 的節(jié)點(diǎn)的目的。
由以上分析可得代碼如下（接上述 delete 方法省略號(hào)后）：
else if (currentNode.rightChild == null) {//要?jiǎng)h除的節(jié)點(diǎn)只有左孩子
if (currentNode == root)
root = currentNode.leftChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.leftChild;
else
parentNode.rightChild = currentNode.leftChild;
} else if (currentNode.leftChild == null) {//要?jiǎng)h除的節(jié)點(diǎn)只有右孩子
if (currentNode == root)
root = currentNode.rightChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.rightChild;
else
parentNode.rightChild = currentNode.rightChild;
}
......
3、待刪除節(jié)點(diǎn)既有左孩子，又有右孩子。
例如刪除圖一中 key 值為 10 的節(jié)點(diǎn)，這時(shí)就需要用 key 值為 10 的節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)（節(jié)點(diǎn) 11）來代替 key 值為 10 的節(jié)點(diǎn)，并刪除 key 值為 10 的節(jié)點(diǎn)的中序后繼節(jié)點(diǎn)，由中序遍歷相關(guān)規(guī)則可知， key 值為 10 的節(jié)點(diǎn)的直接中序后繼節(jié)點(diǎn)一定是其右子樹中 key 值最小的節(jié)點(diǎn)，所以此中序后繼節(jié)點(diǎn)一定不含子節(jié)點(diǎn)或者只含有一個(gè)右孩子，刪除此中序后繼節(jié)點(diǎn)就屬于上述 1,2 所述情況。圖一中 key 值為 10 的節(jié)點(diǎn)的直接中序后繼節(jié)點(diǎn) 為 11，節(jié)點(diǎn) 11 含有一個(gè)右孩子 12。
所以刪除 圖一中 key 值為 10 的節(jié)點(diǎn)分為以下幾步：
a、找到 key 值為 10 的節(jié)點(diǎn)的直接中序后繼節(jié)點(diǎn)（即其右子樹中值最小的節(jié)點(diǎn) 11），并刪除此直接中序后繼節(jié)點(diǎn)。
private Node getDirectPostNode(Node delNode) {//方法作用為得到待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)
Node parentNode = delNode;//用來保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)的父親節(jié)點(diǎn)
Node direcrPostNode = delNode;//用來保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)
Node currentNode = delNode.rightChild;
while (currentNode != null) {
parentNode = direcrPostNode;
direcrPostNode = currentNode;
currentNode = currentNode.leftChild;
}
if (direcrPostNode != delNode.rightChild) {//從樹中刪除此直接后繼節(jié)點(diǎn)
parentNode.leftChild = direcrPostNode.rightChild;
direcrPostNode.rightChild = null;
}
return direcrPostNode;//返回此直接后繼節(jié)點(diǎn)
}
b、將此后繼節(jié)點(diǎn)的 key、value 值賦給待刪除節(jié)點(diǎn)的 key，value值。(接情況二中省略號(hào)代碼之后)
else { //要?jiǎng)h除的節(jié)點(diǎn)既有左孩子又有右孩子
//思路：用待刪除節(jié)點(diǎn)右子樹中的key值最小節(jié)點(diǎn)的值來替代要?jiǎng)h除的節(jié)點(diǎn)的值,然后刪除右子樹中key值最小的節(jié)點(diǎn)
//右子樹key最小的節(jié)點(diǎn)一定不含左子樹,所以刪除這個(gè)key最小的節(jié)點(diǎn)一定是屬于葉子節(jié)點(diǎn)或者只有右子樹的節(jié)點(diǎn)
Node directPostNode = getDirectPostNode(currentNode);
currentNode.key = directPostNode.key;
currentNode.value = directPostNode.value;
}
至此刪除指定節(jié)點(diǎn)的操作結(jié)束。
最后給出完整代碼及簡(jiǎn)單測(cè)試代碼及測(cè)試結(jié)果：
class Node {
int key;
int value;
Node leftChild;
Node rightChild;
public Node(int key, int value) {
this.key = key;
this.value = value;
}
public void displayNode() {
}
}
class Tree {
Node root;
public Node find(int key) {
Node currentNode = root;
while (currentNode != null && currentNode.key != key) {
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
} else {
currentNode = currentNode.rightChild;
}
}
return currentNode;
}
public void insert(int key, int value) {
if (root == null) {
root = new Node(key, value);
return;
}
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (currentNode != null) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
Node newNode = new Node(key, value);
if (isLeftChild) {
parentNode.leftChild = newNode;
} else {
parentNode.rightChild = newNode;
}
}
public boolean delete(int key) {
Node currentNode = root;
Node parentNode = root;
boolean isLeftChild = true;
while (currentNode != null && currentNode.key != key) {
parentNode = currentNode;
if (key < currentNode.key) {
currentNode = currentNode.leftChild;
isLeftChild = true;
} else {
currentNode = currentNode.rightChild;
isLeftChild = false;
}
}
if (currentNode == null) {
return false;
}
if (currentNode.leftChild == null && currentNode.rightChild == null) {
//要?jiǎng)h除的節(jié)點(diǎn)為葉子節(jié)點(diǎn)
if (currentNode == root)
root = null;
else if (isLeftChild)
parentNode.leftChild = null;
else
parentNode.rightChild = null;
} else if (currentNode.rightChild == null) {//要?jiǎng)h除的節(jié)點(diǎn)只有左孩子
if (currentNode == root)
root = currentNode.leftChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.leftChild;
else
parentNode.rightChild = currentNode.leftChild;
} else if (currentNode.leftChild == null) {//要?jiǎng)h除的節(jié)點(diǎn)只有右孩子
if (currentNode == root)
root = currentNode.rightChild;
else if (isLeftChild)
parentNode.leftChild = currentNode.rightChild;
else
parentNode.rightChild = currentNode.rightChild;
} else { //要?jiǎng)h除的節(jié)點(diǎn)既有左孩子又有右孩子
//思路：用待刪除節(jié)點(diǎn)右子樹中的key值最小節(jié)點(diǎn)的值來替代要?jiǎng)h除的節(jié)點(diǎn)的值,然后刪除右子樹中key值最小的節(jié)點(diǎn)
//右子樹key最小的節(jié)點(diǎn)一定不含左子樹,所以刪除這個(gè)key最小的節(jié)點(diǎn)一定是屬于葉子節(jié)點(diǎn)或者只有右子樹的節(jié)點(diǎn)
Node directPostNode = getDirectPostNode(currentNode);
currentNode.key = directPostNode.key;
currentNode.value = directPostNode.value;
}
return true;
}
private Node getDirectPostNode(Node delNode) {//方法作用為得到待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)
Node parentNode = delNode;//用來保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)的父親節(jié)點(diǎn)
Node direcrPostNode = delNode;//用來保存待刪除節(jié)點(diǎn)的直接后繼節(jié)點(diǎn)
Node currentNode = delNode.rightChild;
while (currentNode != null) {
parentNode = direcrPostNode;
direcrPostNode = currentNode;
currentNode = currentNode.leftChild;
}
if (direcrPostNode != delNode.rightChild) {//從樹中刪除此直接后繼節(jié)點(diǎn)
parentNode.leftChild = direcrPostNode.rightChild;
direcrPostNode.rightChild = null;
}
return direcrPostNode;//返回此直接后繼節(jié)點(diǎn)
}
public void preOrder(Node rootNode) {
if (rootNode != null) {
System.out.println(rootNode.key + " " + rootNode.value);
preOrder(rootNode.leftChild);
preOrder(rootNode.rightChild);
}
}
public void inOrder(Node rootNode) {
if (rootNode != null) {
inOrder(rootNode.leftChild);
System.out.println("key: " + rootNode.key + " " + "value: " + rootNode.value);
inOrder(rootNode.rightChild);
}
}
public void postOrder(Node rootNode) {
if (rootNode != null) {
postOrder(rootNode.leftChild);
postOrder(rootNode.rightChild);
System.out.println(rootNode.key + " " + rootNode.value);
}
}
}
public class BinarySearchTreeApp {
public static void main(String[] args) {
Tree tree = new Tree();
tree.insert(6, 6);//插入操作,構(gòu)造圖一所示的二叉樹
tree.insert(3, 3);
tree.insert(14, 14);
tree.insert(16, 16);
tree.insert(10, 10);
tree.insert(9, 9);
tree.insert(13, 13);
tree.insert(11, 11);
tree.insert(12, 12);
System.out.println("刪除前遍歷結(jié)果");
tree.inOrder(tree.root);//中序遍歷操作
System.out.println("刪除節(jié)點(diǎn)10之后遍歷結(jié)果");
tree.delete(10);//刪除操作
tree.inOrder(tree.root);
}
}
測(cè)試結(jié)果：
以上就是本文的全部?jī)?nèi)容，希望本文的內(nèi)容對(duì)大家的學(xué)習(xí)或者工作能帶來一定的幫助，同時(shí)也希望多多支持腳本之家！
相關(guān)文章
組合模式，又叫部分整體模式，它創(chuàng)建了對(duì)象組的數(shù)據(jù)結(jié)構(gòu)組合模式使得用戶對(duì)單個(gè)對(duì)象和組合對(duì)象的訪問具有一致性。本文將通過示例為大家詳細(xì)介紹一下組合模式，需要的可以參考一下2022-05-05
java仿Servlet生成驗(yàn)證碼實(shí)例詳解
這篇文章主要介紹了java仿Servlet生成驗(yàn)證碼實(shí)例詳解的相關(guān)資料,需要的朋友可以參考下2017-04-04
import java和javax區(qū)別小結(jié)
Java包和javax包在Java編程語言中都起著至關(guān)重要的作用,本文就來介紹一下import java和javax區(qū)別小結(jié),具有一定的參考價(jià)值,感興趣的可以了解一下2024-10-10
SpringMVC攔截器的實(shí)現(xiàn)和作用及Redis登陸功能的優(yōu)化詳解
這篇文章主要介紹了Java項(xiàng)目SpringMVC攔截器+Redis優(yōu)化登錄功能實(shí)現(xiàn)過程，文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值，需要的朋友們下面隨著小編來一起學(xué)習(xí)吧2022-09-09
詳解SpringBoot中@NotNull,@NotBlank注解使用
這篇文章主要為大家詳細(xì)介紹了Spring?Boot中集成Validation與@NotNull,@NotBlank等注解的簡(jiǎn)單使用，感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下2022-08-08
RabbitMQ交換機(jī)與Springboot整合的簡(jiǎn)單實(shí)現(xiàn)
這篇文章主要介紹了RabbitMQ交換機(jī)與Springboot整合的簡(jiǎn)單實(shí)現(xiàn),本文通過實(shí)例代碼給大家介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或工作具有一定的參考借鑒價(jià)值，需要的朋友可以參考下2021-07-07
這篇文章主要介紹了Java中如何將Html轉(zhuǎn)換為PDF的方法，文中有相關(guān)的代碼示例和步驟講解，感興趣的同學(xué)可以參考閱讀2023-06-06
Java Lambda表達(dá)式原理及多線程實(shí)現(xiàn)
這篇文章主要介紹了Java Lambda表達(dá)式原理及多線程實(shí)現(xiàn),文中通過示例代碼介紹的非常詳細(xì)，對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友可以參考下2020-07-07
Spring Boot實(shí)現(xiàn)模塊化的幾種方法
模塊可以是業(yè)務(wù)模塊，為應(yīng)用程序提供一些業(yè)務(wù)服務(wù)，或者為幾個(gè)其他模塊或整個(gè)應(yīng)用程序提供跨領(lǐng)域關(guān)注的技術(shù)模塊。這篇文章主要介紹了Spring Boot實(shí)現(xiàn)模塊化,需要的朋友可以參考下2018-07-07
Spring Cloud Alibaba Nacos Config進(jìn)階使用
這篇文章主要介紹了Spring Cloud Alibaba Nacos Config進(jìn)階使用，文中使用企業(yè)案例，圖文并茂的展示了Nacos Config的使用，感興趣的小伙伴可以看一看2021-08-08