什麼是二叉查找樹？
二叉查找樹（BST），又名二叉搜尋樹是一種基于節點的二叉樹資料結構，具有以下屬性：
- 節點的左子樹僅包含值小于自身值的節點。
- 節點的右子樹隻包含值大于自身值的節點。
- 左右子樹也必須是二叉搜尋樹。
- 不能有重複的節點。
如下圖
二叉查找樹的上述屬性提供了節點值之間的排序，以便可以快速完成搜尋、最小值和最大值等操作。如果沒有排序，那麼我們可能必須比較每個節點值來搜尋給定的數值。
如何在給定的二叉查找樹中搜尋特定的節值？
為了搜尋一個值，如果我們有一個排序數組，我們可以通過二分查找法來進行搜尋。假設我們要在數組中搜尋一個數字，在二分查找中，我們首先将數組定義為我們的搜尋空間，該數字隻能存在于該搜尋空間内。現在我們将要搜尋的數字或要搜尋的元素與搜尋空間的中間元素（中位數）進行比較，如果正在搜尋的記錄小于中間元素，我們就在左半邊搜尋，否則我們繼續搜尋在右半部分，在相等的情況下我們找到了元素。在二分查找中，我們從搜尋空間中的“n”個元素開始，如果中間元素不是我們正在尋找的元素，我們将搜尋空間減少到“n/2”，以此類推我們不斷縮小搜尋空間，直到我們找到想要尋找的值，或者我們将搜尋空間縮小到一個元素并停止搜尋。
二叉查找樹中的搜尋操作與上述操作非常相似。假設我們要搜尋數字，我們從根開始，然後我們将要搜尋的值與根的值進行比較，如果相等，我們完成搜尋，如果它更小，我們知道我們需要轉到左子樹，因為在二叉查找樹中，左子樹中的所有元素都較小，而右子樹中的所有元素都較大。在二叉查找樹中搜尋元素基本上就是這種周遊，在每一步我們要麼向左要麼向右，并且在每一步我們丢棄一個子樹。如果樹是平衡的（如果所有節點的左右子樹的高度差不大于 1，我們稱樹平衡），我們從搜尋空間“n”開始節點，當我們丢棄其中一個子樹時，我們丢棄“n/2”節點，是以我們的搜尋空間減少到“n/2”。在下一步中，我們将搜尋空間減少到“n/4”并重複直到找到元素或我們的搜尋空間減少到隻有一個節點。這裡的搜尋也是二分查找，是以得名；二叉查找樹。
圖例：
在下面的樹中搜尋 6
- 從根開始。
- 将搜尋元素與根進行比較，如果小于根，則遞歸調用左子樹，否則遞歸調用右子樹。
- 如果在任何地方找到要搜尋的元素，則傳回 true，否則傳回 false。
時間複雜度：搜尋和插入操作的最壞情況時間複雜度為 O(h)，其中 h 是二叉搜尋樹的高度。在最壞的情況下，我們可能不得不從根到最深的葉節點。傾斜樹的高度可能變為 n，搜尋和插入操作的時間複雜度可能變為 O(n)。
二叉查找樹的一些特性：
- 二叉查找樹的中序周遊總是産生升序的輸出。
- 我們可以構造一個隻有 前序 或 後序 或層次周遊的二叉查找樹。請注意，我們總是可以通過對特定的周遊進行排序來獲得中序周遊。
- 具有 n 個不同鍵的不同的二叉查找樹的數量是加泰羅尼亞數
完整示例代碼下載下傳連結：
（包含各種語言：C語言、Python、Java，C++等均有示例）
免費資源下載下傳：二叉搜尋樹實作