二叉查找樹的結(jié)構(gòu)比較簡單：

1，有一個根節(jié)點，否則就是空樹

2，每個節(jié)點有一個值，一個左子節(jié)點，一個右子節(jié)點

3，每個節(jié)點的左子樹的所有節(jié)點的值都比當(dāng)前節(jié)點的值小

4，每個節(jié)點的右子樹的所有節(jié)點的值都比當(dāng)前節(jié)點的值大

代碼：

測試：

最理想情況

結(jié)果：

最壞情況：

二叉查找樹在最好情況下（上圖左），按值查找最多需要log2（N+1）次；

最壞的情況（上圖右），按值查找需要N次，和鏈表的結(jié)構(gòu)是一樣的了。

為了保證結(jié)構(gòu)不退化，需要加一些條件，AVL樹是其中一種比較好且容易實現(xiàn)的結(jié)構(gòu)（以后再說）。