怎么理解并掌握Java二叉查找樹

本篇內容主要講解“怎么理解并掌握Java二叉查找樹”，感興趣的朋友不妨來看看。本文介紹的方法操作簡單快捷，實用性強。下面就讓小編來帶大家學習“怎么理解并掌握Java二叉查找樹”吧!

一、介紹

二叉查找樹，英文全稱：Binary Search Tree，簡稱：BST，它是計算機科學中最早投入實際使用的一種樹形結構，特性如下：

• 若左子樹不為空，則左子樹上所有結點的值均小于它的根結點的值;

• 若右子樹不為空，則右子樹上所有結點的值均大于或等于它的根結點的值;

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

特性定義比較粗放，所以在樹形形態結構上，有著多樣，例如下圖：

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

• a圖，需要5次;

• b圖，需要3次;

• c圖，需要8次;

由此可見，不同的形狀，所需查找的次數是不一樣的，關于這一點，后面我們在介紹平衡二叉查找樹、紅黑樹這種數據結構的時候，會進行詳細介紹。

雖然二叉查找樹，在不同的形狀下，查找效率不一樣，但是它是學習其他樹形結構的基礎，了解了二叉查找樹的算法，相信再了解其他二叉樹結構會輕松很多。

二、算法思路

2.1、 新增

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

2.2、 查找

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

2.3、 刪除

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

被刪除的節點，右子樹為空

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

• 被刪除的節點，左子樹為空

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

• 被刪除的節點，左、右子樹不為空 

這種場景，稍微復雜一點，先定位到要刪除的目標元素，根據左子節點內容一定小于當前節點內容特點，找到目標元素的左子樹，通過遞歸遍歷找到目標元素的左子樹的右子樹，找到最末端的元素之后，進行與目標元素進行替換，最后移除最末端元素。

2.4、 遍歷

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

• 層次遍歷，從根節點開始;

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

2.4.1、層次遍歷

層次遍歷，算法思路比較簡單，從根節點開始，分層從左到右進行遍歷元素。

2.4.2、深度遍歷

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

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

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

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

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

三、代碼實踐

首先創建一個實體數據結構BSTNode，內容如下：

然后，創建一個二叉查找樹操作類BinarySearchTree，內容如下：

最后，我們來測試一下，代碼內容如下：

輸出結果：

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

到此，相信大家對“怎么理解并掌握Java二叉查找樹”有了更深的了解，不妨來實際操作一番吧！這里是億速云網站，更多相關內容可以進入相關頻道進行查詢，關注我們，繼續學習！