首先，二分搜索樹?作為?二叉樹?的一種，有著二叉樹的基本特性：
1.每個結(jié)點(diǎn)（?根結(jié)點(diǎn)?除外）都有一個?前驅(qū)結(jié)點(diǎn)（即其父結(jié)點(diǎn)）。
2.每個結(jié)點(diǎn)至多有兩個?后繼結(jié)點(diǎn)（即其子結(jié)點(diǎn)）。
此外，二分搜索樹還有一些特殊的特性：
1.每個結(jié)點(diǎn)?左孩子?及其后代的值都?小于?這個結(jié)點(diǎn)的值。
2.每個結(jié)點(diǎn)?右孩子?及其后代的值都?大于?這個結(jié)點(diǎn)的值。
3.結(jié)點(diǎn)的值?不重復(fù)?。
所以，能以二分搜索樹結(jié)構(gòu)存放的數(shù)據(jù)有著一條基本要：可比性?。
下面以一個我實(shí)現(xiàn)的一個簡單的二分搜索樹類來進(jìn)一步理解二分搜索樹。

和鏈表類似，首先設(shè)計(jì)一個?結(jié)點(diǎn)類?，這個結(jié)點(diǎn)類包含?數(shù)據(jù)?和?指向左右兩邊結(jié)點(diǎn)的指針?。結(jié)點(diǎn)類的構(gòu)造函數(shù)可以直接對結(jié)點(diǎn)賦值，然后利用結(jié)點(diǎn)類對象來創(chuàng)建一棵二叉搜索樹。二叉搜索樹類的設(shè)計(jì)如下：

這里為了避免重復(fù)設(shè)計(jì)就可以兼容更多數(shù)據(jù)類型，引入了?泛型?，即?模板?的概念。（模板的關(guān)鍵字是?class?或?typename）

這里的?root?表示?根節(jié)點(diǎn)?，m_size?表示?二分搜索樹大小?。為了保護(hù)數(shù)據(jù)，這些變量都設(shè)置為?private?。
與鏈表不同的是，二分搜索樹一般不需要引入?虛擬頭結(jié)點(diǎn)?的概念。
實(shí)現(xiàn)了前面的程序之后，接下來就是一個二分搜索樹的增、刪、查以及一些其他基本操作，接下來利用代碼去實(shí)現(xiàn)。

2. 基本操作程序?qū)崿F(xiàn)

2.1 增加操作

首先，在類體內(nèi)進(jìn)行增加操作函數(shù)的原型說明。這里包括兩個函數(shù)：
add (public)
add (private)
這里為什么這么做呢？因?yàn)閷τ跇浣Y(jié)構(gòu)來講，不管是增、刪、改、查，還是遍歷操作，根節(jié)點(diǎn)是一個很重要的結(jié)點(diǎn)。為了保護(hù)數(shù)據(jù)，這個結(jié)點(diǎn)一般對用戶是屏蔽的，即用戶不需要知道根節(jié)點(diǎn)就可以完成需要的操作。
而對于樹結(jié)構(gòu)來說，這些操作一般都是通過遞歸來實(shí)現(xiàn)的（某些操作使用了非遞歸的方式進(jìn)行了實(shí)現(xiàn)），遞歸的時候往往需要結(jié)點(diǎn)參數(shù)，所以這里利用了一個?public?函數(shù)來調(diào)用另一個?private?函數(shù)實(shí)現(xiàn)操作，下面的操作也是這樣。
注：樹的操作也可以使用非遞歸的方式實(shí)現(xiàn)，這里只是為了方便代碼編寫以及理解，使用了遞歸的方式。同理，對于鏈表的操作而言，也可以使用遞歸的方式進(jìn)行實(shí)現(xiàn)。

由于這些函數(shù)在類體外，所以每個函數(shù)頭部必須添加一行代碼：

表示該函數(shù)使用模板，下面同理。

注意理解這里私有的?add?函數(shù)，為了方便代碼編寫，特意加了返回值。如果不加返回值，函數(shù)是通過父結(jié)點(diǎn)連接要添加的子結(jié)點(diǎn)，而加了返回值就可以將子結(jié)點(diǎn)返回給父結(jié)點(diǎn)，操作更加簡便。

2.2 刪除操作

對于二分搜索樹來說，為了保證刪除操作完成后的樹依舊是一棵二分搜索樹，我們需要分三種情況討論：
（1）欲刪除結(jié)點(diǎn)左右子樹均為空

若左右子樹均為空，則直接刪除該結(jié)點(diǎn)，并將其父結(jié)點(diǎn)指向刪除結(jié)點(diǎn)的指針清空。

（2）欲刪除結(jié)點(diǎn)左右子樹僅一方為空

若左右子樹僅一方為空，則刪除該結(jié)點(diǎn)，并將該結(jié)點(diǎn)不為空的子樹連接到刪除結(jié)點(diǎn)的父結(jié)點(diǎn)指向刪除結(jié)點(diǎn)的那一支。

（3）欲刪除結(jié)點(diǎn)左右子樹均不為空

若左右子樹均不為空，就用刪除結(jié)點(diǎn)的右邊第一個結(jié)點(diǎn)的最左邊的結(jié)點(diǎn)（即一直往左走，直到該結(jié)點(diǎn)的左子樹為空的那個結(jié)點(diǎn)）來替換掉刪除結(jié)點(diǎn)，然后刪除掉該結(jié)點(diǎn)。而用來替換的那個結(jié)點(diǎn)的后代也注意需要維護(hù)，不能丟失。

同理，在類體內(nèi)進(jìn)行刪除函數(shù)的原型說明。這里包括兩個函數(shù)：
remove (public)
remove (private)
分別去實(shí)現(xiàn)它們。

2.3 查找操作

同樣，查找操作也有兩個函數(shù)：
contains (public)
contains (private)

2.4 遍歷操作

樹的遍歷是一個很重要的概念，下面給出一張圖來說明四種遍歷的過程。
注：因?yàn)槎鏄涞谋闅v操作是通用的，所以這里并沒有以二分搜索樹為例子，而是一棵普通的二叉樹。

二叉樹的先（中或后）序遍歷實(shí)際上表示的是結(jié)點(diǎn)被訪問第幾次會輸出。
先序遍歷表示第一次被訪問時（橙色）會輸出；
中序遍歷表示第二次被訪問時（綠色）會輸出；
后序遍歷表示第三次被訪問時（黃色）會輸出。
這三種遍歷的遞歸版本比較容易實(shí)現(xiàn)，依靠輸出位置的不同決定是哪一種遍歷。這三種遍歷實(shí)質(zhì)上是一種?深度優(yōu)先?遍歷。而非遞歸版本比較難，下面也給出了一種程序?qū)崿F(xiàn)方法。
注：這三種遍歷的非遞歸版本利用調(diào)用棧來實(shí)現(xiàn)，這里我們使用了我們在?1.2?中實(shí)現(xiàn)的?數(shù)組棧?作為調(diào)用棧。
層序遍歷表示一層一層（圖中的藍(lán)色虛線）的訪問輸出，使用的是非遞歸的方法，調(diào)用了一個隊(duì)列來實(shí)現(xiàn)，層序遍歷實(shí)質(zhì)上是一種?廣度優(yōu)先?遍歷。
注：層序遍歷實(shí)現(xiàn)利用了我們在?1.4?中實(shí)現(xiàn)的?循環(huán)隊(duì)列?作為調(diào)用隊(duì)列。

這里遍歷函數(shù)較多，一共有十個：
preOrder (public)：先序遍歷
preOrder (private)
preOrder (public)：中序遍歷
preOrder (private)
preOrder (public)：后序遍歷
preOrder (private)
preOrderNR：先序遍歷（非遞歸版本）
inOrderNR：中序遍歷（非遞歸版本）
postOrderNR：后序遍歷（非遞歸版本）
levelOrder：層序遍歷
和前面的函數(shù)一樣，遞歸版本的遍歷函數(shù)有?public?和?private?兩個，實(shí)現(xiàn)遞歸版本遍歷的操作。然后又實(shí)現(xiàn)了三種遍歷操作的非遞歸版本，以及層序遍歷（非遞歸）。下面分別對它們進(jìn)行實(shí)現(xiàn)。

2.5 其他操作

二分搜索樹還有一些其他的操作，這些函數(shù)我在類體內(nèi)進(jìn)行了實(shí)現(xiàn)。
包括?二分搜索樹大小?的查詢等操作。

3. 算法復(fù)雜度分析

3.1 增加操作

因?yàn)槎炙阉鳂涞奶赜行再|(zhì)，這里平均復(fù)雜度是以?2?為底?n?的對數(shù)，簡單寫作?logn?，即其是對數(shù)級別的時間復(fù)雜度，下面的同理，這正是二分搜索樹的優(yōu)點(diǎn)。

3.2 刪除操作

3.3 查找操作

總體情況：

因?yàn)槎炙阉鳂涞奶赜行再|(zhì)，所以操作的復(fù)雜度都是?O(logn)?級別的，和線性結(jié)構(gòu)相比，（線性結(jié)構(gòu)很多操作需要?O(n)?級別的時間復(fù)雜度）充分體現(xiàn)出二分搜索樹這一結(jié)構(gòu)的優(yōu)點(diǎn)。

4. 完整代碼

程序完整代碼（這里使用了頭文件的形式來實(shí)現(xiàn)類）如下：
其中，數(shù)組棧?類以及?循環(huán)隊(duì)列?類的代碼不再重復(fù)給出，如有需要，可以查看?1.2?和?1.4的內(nèi)容。