大家好，我是鴨血粉絲，拼著頭發(fā)掉光的風險給大家總結(jié)了這篇文章，我愿拿我明年的今天還是單身來祝愿你們能學會～

所謂二叉查找樹，就是按照二分進行查找，每次查詢只需要選擇其中一個子樹就進行查找，從而減少查找次數(shù)，提升查詢效率!

[[314928]]

一、介紹

在前面的文章中，我們對樹這種數(shù)據(jù)結(jié)構(gòu)做了一些基本介紹，今天我們繼續(xù)來聊聊一種非常常用的動態(tài)查找樹： 二叉查找樹。

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

• 若左子樹不為空，則左子樹上所有結(jié)點的值均小于它的根結(jié)點的值;
• 若右子樹不為空，則右子樹上所有結(jié)點的值均大于或等于它的根結(jié)點的值;
• 它的左、右子樹也分別為二叉查找樹;

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

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

• a圖，需要5次;
• b圖，需要3次;
• c圖，需要8次;

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

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

二、算法思路

2.1、 新增

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

2.2、 查找

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

2.3、 刪除

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

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

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

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

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

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

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

2.4、 遍歷

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

• 層次遍歷，從根節(jié)點開始;
• 深度遍歷，又分為前序、中序、后序遍歷三種方式;

2.4.1、層次遍歷

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

2.4.2、深度遍歷

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

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

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

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

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

三、代碼實踐

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

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

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

輸出結(jié)果：

========插入元素======== 
插入關鍵字key=5  
插入到樹根節(jié) 
插入關鍵字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 ->],搜索成功 
查找結(jié)果：true 
========刪除key為10的元素======== 
刪除關鍵字key=10  
開始搜索目標元素[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 

四、總結(jié)

二叉查找樹，作為樹類型中一種非常重要的數(shù)據(jù)結(jié)構(gòu)，有著非常廣泛的應用，但是二叉查找樹具有很高的靈活性，不同的插入順序，可能造成樹的形態(tài)差異比較大，如開文介紹的圖c，在某些情況下會變成一個長鏈表，此時的查詢效率會大大降低，如何解決這個問題呢，平衡二叉樹就要派上用場了，會在后面的文章進行介紹!

(第一句話是開玩笑，呸呸呸，情人節(jié)快樂)