二叉查找樹(shù)（Binary Search Tree）又稱(chēng)二叉排序樹(shù)、二叉搜索樹(shù)。二叉查找樹(shù)是為了實(shí)現(xiàn)快速查找而生的，一般情況下，查詢(xún)效率比鏈表結(jié)構(gòu)要高。不過(guò)，它不僅僅支持快速查找一個(gè)數(shù)據(jù)，還支持快速插入、刪除一個(gè)數(shù)據(jù)。二叉查找樹(shù)要求，在樹(shù)中的任意一個(gè)節(jié)點(diǎn)都要滿(mǎn)足，其左子樹(shù)中每個(gè)節(jié)點(diǎn)的值，都要小于這個(gè)節(jié)點(diǎn)的值，而右子樹(shù)每個(gè)節(jié)點(diǎn)的值都大于這個(gè)節(jié)點(diǎn)的值。二叉查找樹(shù)操作主要分為查找，插入和刪除，下面我們來(lái)一一介紹。

1.查找

在二叉查找樹(shù)中查找一個(gè)節(jié)點(diǎn)，我們先取根節(jié)點(diǎn)，如果它等于我們要查找的數(shù)據(jù)，那就返回。如果要查找的數(shù)據(jù)比根節(jié)點(diǎn)的值小，那就左子樹(shù)中遞歸查找；如果要查找的數(shù)據(jù)比根節(jié)點(diǎn)的值大，那就右子樹(shù)中遞歸查找。

查找的代碼實(shí)現(xiàn):

public class BinarySearchTree {
????private Node root;
????public Node find(int data) {
????????Node temp = root;
????????while (temp != null) {
????????????if (data == temp.data) {
????????????????return temp;
????????????} else if(data > temp.data) {
????????????????temp = temp.rchild;
????????????} else {
????????????????temp = temp.lchild;
????????????}
????????}
????????return null;
????}
}

public class Node {
????int data;
????Node lchild;
????Node rchild;
????public Node(int data) {
????????this.data = data;
????}
}

2.插入

插入的操作類(lèi)似于查找的操作。從根節(jié)點(diǎn)開(kāi)始，依次比較要插入的數(shù)據(jù)和節(jié)點(diǎn)的關(guān)系。 如果要插入的數(shù)據(jù)比節(jié)點(diǎn)的數(shù)據(jù)大，并且節(jié)點(diǎn)的右子樹(shù)為空，就將數(shù)據(jù)直接插入到右子節(jié)點(diǎn)的位置，如果右子樹(shù)不為空，那就繼續(xù)遍歷右子樹(shù)；如果要插入的數(shù)據(jù)比節(jié)點(diǎn)的數(shù)據(jù)小，并且節(jié)點(diǎn)的左子樹(shù)為空，就將數(shù)據(jù)直接插入到左子節(jié)點(diǎn)的位置，如果左子樹(shù)不為空，那就繼續(xù)遍歷左子樹(shù)。

插入的代碼實(shí)現(xiàn):

public void insert(int data) {
????????if (root == null) {
????????????root = new Node(data);
????????????return;
????????}
????????
????????Node temp = root;
????????while (true) {
????????????if (data > temp.data) {
????????????????if (temp.rchild == null) {
????????????????????temp.rchild = new Node(data);
????????????????????return;
????????????????}
????????????????temp = temp.rchild;
????????????} else {
????????????????if (temp.lchild == null) {
????????????????????temp.lchild = new Node(data);
????????????????????return;
????????????????}
????????????????temp = temp.lchild;
????????????}
????????}
}

3.刪除

二叉查找樹(shù)的查找和插入的操作比較簡(jiǎn)單，但是刪除的操作較為復(fù)雜，分為三種情況。 第一種情況，要?jiǎng)h除的節(jié)點(diǎn)是葉子節(jié)點(diǎn)。此時(shí)只需要直接將父節(jié)點(diǎn)中指向要?jiǎng)h除節(jié)點(diǎn)的指針置為null即可。如下圖中刪除28。 第二種情況，要?jiǎng)h除的節(jié)點(diǎn)有只有一個(gè)子節(jié)點(diǎn)（左子節(jié)點(diǎn)或右子節(jié)點(diǎn)），我們只需要更新父節(jié)點(diǎn)中的指針，讓它指向要?jiǎng)h除節(jié)點(diǎn)的字節(jié)點(diǎn)就可以了。如下圖中的34。 第三種情況，要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)。這種情況下，我們需要把要?jiǎng)h除節(jié)點(diǎn)的右子樹(shù)中最小的節(jié)點(diǎn)替換要?jiǎng)h除節(jié)點(diǎn)。如下圖中的15。

刪除完成后

代碼實(shí)現(xiàn):

?public void delete(int data) {
????????Node temp = root; ?// temp指向要?jiǎng)h除的節(jié)點(diǎn)
????????Node ftemp = null; // ftemp指向要?jiǎng)h除節(jié)點(diǎn)的父節(jié)點(diǎn)
????????while (temp != null && temp.data != data) {
????????????ftemp = temp;
????????????if (data > temp.data) {
????????????????temp = temp.rchild;
???????????} else {

????????????????temp = temp.lchild;
????????????}
????????}

???????if (temp == null) return; // 沒(méi)有找到對(duì)應(yīng)的節(jié)點(diǎn)
???????// 若找到，temp就是要?jiǎng)h除的節(jié)點(diǎn)
???????// 要?jiǎng)h除的節(jié)點(diǎn)有兩個(gè)子節(jié)點(diǎn)
????????if (temp.lchild != null && temp.rchild != null) {
????????????Node minTemp = temp.rchild; ?// 存儲(chǔ)右子樹(shù)的最小節(jié)點(diǎn)
????????????Node fminTemp = temp; // minTemp的父節(jié)點(diǎn)

????????????// 找到右子樹(shù)的最小節(jié)點(diǎn)
????????????while (minTemp.lchild != null) {
????????????????fminTemp = minTemp;
????????????????minTemp = minTemp.lchild;
????????????}

????????????temp.data = minTemp.data; // 將最小節(jié)點(diǎn)的值替換到temp中
????????????temp = minTemp; ?// 變成刪除葉子節(jié)點(diǎn)
????????????ftemp = fminTemp;
????????}

????????// 刪除節(jié)點(diǎn)是葉子節(jié)點(diǎn)或者僅有一個(gè)節(jié)點(diǎn)
????????Node child; // temp的子節(jié)點(diǎn)
????????if (temp.lchild != null) {
????????????child = temp.lchild;
????????} else if (temp.rchild != null) {
????????????child = temp.rchild;
????????} else {
????????????child = null;
????????}

????????if (ftemp == null) { ?// 刪除的是根節(jié)點(diǎn)
???????????root = child;

????????} else if (ftemp.lchild == temp) {
????????????ftemp.lchild = child;
????????} else {
????????????ftemp.rchild = child;
????????}
????}

以上就是對(duì)二叉查找樹(shù)操作的相關(guān)介紹，二叉查找樹(shù)本質(zhì)上是一棵空樹(shù)，或者沒(méi)有鍵值相等的結(jié)點(diǎn)，對(duì)二叉查找樹(shù)的定義也是相對(duì)的。想要深入學(xué)習(xí)二叉查找樹(shù)的小伙伴可以觀看本站的數(shù)據(jù)結(jié)構(gòu)和算法教程，積累更多關(guān)于二叉查找樹(shù)的相關(guān)知識(shí)。