二叉查找樹（binary search tree），也稱二叉排序樹（binary sorted tree），是指一棵空樹或者具有下列性質的二叉樹：
若任意節點的左子樹不空，則左子樹上所有結點的值均小于它的根結點的值
任意節點的右子樹不空，則右子樹上所有結點的值均大于它的根結點的值
任意節點的左、右子樹也分别為二叉查找樹
沒有鍵值相等的節點（no duplicate nodes）
二叉查找樹相比于其他資料結構的優勢在于查找、插入的時間複雜度較低。為o(log n)。
二叉查找樹是基礎性資料結構，用于建構更為抽象的資料結構，如集合、multiset、關聯數組等。
二叉查找樹的查找過程和次優二叉樹類似，通常采取二叉連結清單作為二叉查找樹的存儲結構。中序周遊二叉查找樹可得到一個關鍵字的有序序列，一個無序序列可以通過構造一棵二叉
查找樹變成一個有序序列，構造樹的過程即為對無序序列進行查找的過程。每次插入的新的結點都是二叉查找樹上新的葉子結點，在進行插入操作時，不必移動其它結點，隻需改動
某個結點的指針，由空變為非空即可。搜尋,插入,删除的複雜度等于樹高，期望o(log n),最壞o(n)(數列有序,樹退化成線性表).
雖然二叉查找樹的最壞效率是o(n),但它支援動态查詢,且有很多改進版的二叉查找樹可以使樹高為o(logn),如:sbt,avl,紅黑樹等.故不失為一種好的動态查找方法.
思路：若根結點的關鍵字等于查找的關鍵字，查找成功；否則，若小于根結點的關鍵字的值，遞歸查找左子樹，否則若大于根結點的關鍵字的值，遞歸查找右子樹，若子樹為空，則查找不成功
思路：首先執行查找算法，找出被插入結點的父結點，判斷被查結點是父結點的左孩子還是右孩子，将被插結點作為葉子結點插入，若二叉樹為空，則首先單獨生成根結點
當然也可以使用傳回插入結點的方式：
在二叉查找樹删去一個結點，分三種情況讨論：
① 若p是葉子結點： 直接删除p，如圖(b)所示。
② 若p隻有一棵子樹(左子樹或右子樹)：直接用p的左子樹(或右子樹)取代p的位置而成為f的一棵子樹。即原來p是f的左子樹，則p的子樹成為f的左子樹；原來p是f的右子樹，則p的子樹成為f的右子樹，如圖(c)、 (d)所示。
③ 若p既有左子樹又有右子樹 ：處理方法有以下兩種，可以任選其中一種。
◆ 用p的直接前驅結點代替p。即從p的左子樹中選擇值最大的結點s放在p的位置(用結點s的内容替換結點p内容)，然後删除結點s。s是p的左子樹中的最右邊的結點且沒有右子樹，對s的删除同②，如圖(e)所示。
◆ 用p的直接後繼結點代替p。即從p的右子樹中選擇值最小的結點s放在p的位置(用結點s的内容替換結點p内容)，然後删除結點s。s是p的右子樹中的最左邊的結點且沒有左子樹，對s的删除同②。
<a href="http://poj.org/problem?id=2418" target="_blank">poj2418 hardwood species</a>