二叉排序樹的性質：每個節點的左子樹中的所有節點的關鍵字都小于該節點的關鍵值，而右子樹中的所有節點的關鍵字都大于該節點的關鍵值。
二叉排序樹的構造是指将一個給定的資料元素構造為相應的二叉排序樹。 基本思想為： 對于任給的一組資料元素{ R1, R2, …, Rn } , 可按以下方法來構造二叉排序樹： (1) 令R1為二叉樹的根; (2) 若R2<R1, 令R2為R1左子樹的根結點，否則R2為R1右子樹的根結點； (3) 對R3, …, Rn結點，也是依次與前面生成的結點比較以确定輸入結點的位置。 這一方法中的一個結點插入，可用以下的非遞歸插入算法來實作：
插入過程可以由下圖一目了然：
從上述的插入過程可以看出每次插入的新結點都是二叉排序樹的葉子結點并且不需移動其他結點，是以在進行插入這樣的操作時比向量（線性表）操作更友善。由于對二叉排序樹進行中序周遊時，可以得到一個按關鍵字大小排列的有序序列，是以對一個無序序列可通過構造二叉排序樹和對這個排序樹進行中序周遊來産生一個有序序列。 具體的程式實作如下：
若要删除的結點由p指出，雙親結點由q指出，則二叉排序樹中結點的删除可分以下三種情況考慮： (1) 若p指向葉子結點，則直接将該結點删除。 (2) 若p所指結點隻有左子樹pL或隻有右子樹pR，此時隻要使pL或pR成為q所指結點的左子樹或右子樹即可，如下圖(a)和(b)所示 (3) 若p所指結點的左子樹pL和右子樹pR均非空，則需要将pL和pR連結到合适的位置上，并且保持二叉排序樹的特點，即應使中序周遊該二叉樹所得序列的相對位置不變。具體做法有兩種：①令pL直接連結到q的左（或右）孩子鍊域上，pR連結到p結點中序前趨結點s上（s是pL最右下的結點）；② 以p結點的直接中序前趨或後繼替代p所指結點，然後再從原二叉排序樹中删去該直接前趨或後繼，如下圖(d)、(e)、(f)所示。從圖中可以看出使用①中做法，會使二叉樹的深度增加，是以不如②中的做法好。 如下圖所示：(紅色代表要删除的節點)
具體程式實作如下：
一個完整執行個體如下：
參考文獻：《計算機軟體技術基礎》 劉彥明 榮政 編 、《 算法導論》
作者：nineheadedbird