二叉排序树的性质：每个节点的左子树中的所有节点的关键字都小于该节点的关键值，而右子树中的所有节点的关键字都大于该节点的关键值。
二叉排序树的构造是指将一个给定的数据元素构造为相应的二叉排序树。 基本思想为： 对于任给的一组数据元素{ 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