本篇內(nèi)容主要講解“怎么理解并掌握J(rèn)ava二叉查找樹”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實(shí)用性強(qiáng)。下面就讓小編來帶大家學(xué)習(xí)“怎么理解并掌握J(rèn)ava二叉查找樹”吧!

創(chuàng)新互聯(lián)專注于企業(yè)成都全網(wǎng)營銷推廣、網(wǎng)站重做改版、惠民網(wǎng)站定制設(shè)計、自適應(yīng)品牌網(wǎng)站建設(shè)、H5開發(fā)、商城網(wǎng)站定制開發(fā)、集團(tuán)公司官網(wǎng)建設(shè)、成都外貿(mào)網(wǎng)站建設(shè)公司、高端網(wǎng)站制作、響應(yīng)式網(wǎng)頁設(shè)計等建站業(yè)務(wù)，價格優(yōu)惠性價比高，為惠民等各大城市提供網(wǎng)站開發(fā)制作服務(wù)。

一、介紹

二叉查找樹，英文全稱：Binary Search Tree，簡稱：BST，它是計算機(jī)科學(xué)中最早投入實(shí)際使用的一種樹形結(jié)構(gòu)，特性如下：

• 若左子樹不為空，則左子樹上所有結(jié)點(diǎn)的值均小于它的根結(jié)點(diǎn)的值;

• 若右子樹不為空，則右子樹上所有結(jié)點(diǎn)的值均大于或等于它的根結(jié)點(diǎn)的值;

• 它的左、右子樹也分別為二叉查找樹;

特性定義比較粗放，所以在樹形形態(tài)結(jié)構(gòu)上，有著多樣，例如下圖：

上圖 a、b、c  三個圖，都滿足以上特性，也被稱為二叉查找樹，雖然通過中序遍歷可以得到一個有效的數(shù)組：[1、2、3、4、5、6、7、8]，但是就查找效率來說，有著一定的差別，例如查詢目標(biāo)為8的內(nèi)容，從根目錄開始查詢，結(jié)構(gòu)如下：

• a圖，需要5次;

• b圖，需要3次;

• c圖，需要8次;

由此可見，不同的形狀，所需查找的次數(shù)是不一樣的，關(guān)于這一點(diǎn)，后面我們在介紹平衡二叉查找樹、紅黑樹這種數(shù)據(jù)結(jié)構(gòu)的時候，會進(jìn)行詳細(xì)介紹。

雖然二叉查找樹，在不同的形狀下，查找效率不一樣，但是它是學(xué)習(xí)其他樹形結(jié)構(gòu)的基礎(chǔ)，了解了二叉查找樹的算法，相信再了解其他二叉樹結(jié)構(gòu)會輕松很多。

二、算法思路

2.1、 新增

新增元素表示向二叉樹中添加元素，比較簡單。如果二叉樹為空，默認(rèn)第一個元素就是根節(jié)點(diǎn)，如果二叉樹不為空，就以上面提到的特點(diǎn)為判斷條件，進(jìn)行左、右節(jié)點(diǎn)的添加。

2.2、 查找

查找元素表示從根節(jié)點(diǎn)開始查找元素，如果根節(jié)點(diǎn)為空，就直接返回空值，如果不為空，通過以左子樹小于父節(jié)點(diǎn)，右子樹大于父節(jié)點(diǎn)的特性為依據(jù)進(jìn)行判斷，然后以遞歸方式進(jìn)行查找元素，直到找到目標(biāo)的元素為止。

2.3、 刪除

刪除元素表示從二叉樹中移除要刪除的元素，邏輯稍微復(fù)雜一些。同樣，先要判斷根節(jié)點(diǎn)是否為空，如果為空，直接返回，如果不為空，分情況考慮。

被刪除的節(jié)點(diǎn)，右子樹為空

這種場景，只需要將被刪除元素的左子樹的父節(jié)點(diǎn)移動到被刪除元素的父節(jié)點(diǎn)，然后將被刪除元素移除即可。

• 被刪除的節(jié)點(diǎn)，左子樹為空

這種場景，與上面類似，只需要將被刪除元素的右子樹的父節(jié)點(diǎn)移動到被刪除元素的父節(jié)點(diǎn)，然后將被刪除元素移除即可。

• 被刪除的節(jié)點(diǎn)，左、右子樹不為空 

這種場景，稍微復(fù)雜一點(diǎn)，先定位到要刪除的目標(biāo)元素，根據(jù)左子節(jié)點(diǎn)內(nèi)容一定小于當(dāng)前節(jié)點(diǎn)內(nèi)容特點(diǎn)，找到目標(biāo)元素的左子樹，通過遞歸遍歷找到目標(biāo)元素的左子樹的右子樹，找到最末端的元素之后，進(jìn)行與目標(biāo)元素進(jìn)行替換，最后移除最末端元素。

2.4、 遍歷

二叉樹的遍歷方式，分兩類：

• 層次遍歷，從根節(jié)點(diǎn)開始;

• 深度遍歷，又分為前序、中序、后序遍歷三種方式;

2.4.1、層次遍歷

層次遍歷，算法思路比較簡單，從根節(jié)點(diǎn)開始，分層從左到右進(jìn)行遍歷元素。

2.4.2、深度遍歷

深度遍歷，在遍歷起始位置上又分三種，分別是前序遍歷、中序遍歷、后序遍歷，每種遍歷方式輸出的結(jié)果不一樣。

• 前序遍歷：從樹根開始 -> 左子樹 -> 右子樹

• 中序遍歷：從最末端左子樹開始 -> 樹根 -> 右子樹

• 后序遍歷：從最末端左子樹 -> 右子樹 -> 最后到樹根

盡管二叉樹在遍歷方式上有多種，但是只要我們掌握了其中的思路原理，再去實(shí)現(xiàn)起來，就會輕松很多。

三、代碼實(shí)踐

首先創(chuàng)建一個實(shí)體數(shù)據(jù)結(jié)構(gòu)BSTNode，內(nèi)容如下：

然后，創(chuàng)建一個二叉查找樹操作類BinarySearchTree，內(nèi)容如下：

最后，我們來測試一下，代碼內(nèi)容如下：

輸出結(jié)果：

========插入元素======== 插入關(guān)鍵字key=5  插入到樹根節(jié) 插入關(guān)鍵字key=2  插入關(guān)鍵字key=7  插入關(guān)鍵字key=1  插入關(guān)鍵字key=6  插入關(guān)鍵字key=4  插入關(guān)鍵字key=8  插入關(guān)鍵字key=3  插入關(guān)鍵字key=9  插入關(guān)鍵字key=10  ========中序遍歷元素======== key:1 key:2 key:3 key:4 key:5 key:6 key:7 key:8 key:9 key:10 ========查找key為9的元素======== 搜索關(guān)鍵字key=9  搜索路徑[5 ->7 ->8 ->9 ->],搜索成功 查找結(jié)果：true ========刪除key為10的元素======== 刪除關(guān)鍵字key=10  開始搜索目標(biāo)元素[5 ->7 ->8 ->9 ->10 ->],搜索成功 刪除結(jié)果：true ========再次中序遍歷元素======== key:1 key:2 key:3 key:4 key:5 key:6 key:7 key:8 key:9

到此，相信大家對“怎么理解并掌握J(rèn)ava二叉查找樹”有了更深的了解，不妨來實(shí)際操作一番吧！這里是創(chuàng)新互聯(lián)網(wǎng)站，更多相關(guān)內(nèi)容可以進(jìn)入相關(guān)頻道進(jìn)行查詢，關(guān)注我們，繼續(xù)學(xué)習(xí)！