二叉查找树的定义
如果一颗二叉树的每个节点对应一个关键字，整个二叉树各结点对应的关键字组成一个关键字集合，并且此关键字集合中的各个关键字在二叉树中是有序的，则乘此二叉树为二叉查找树，或称为二叉排序树。
二叉查找树或者是一颗空树，或者是具有下列性质的二叉树：
（1）若左子树不空，则左子树上的所有结点的值均小于根节点的值；
（2）若右子树不空，则右子树上的所有结点的值均大于根节点的值；
（3）左右子树也都是一颗二叉查找树。
二叉查找树的查找过程
对于二叉查找树构成的查找树，根据二叉查找树的基本特点，查找集合中关键字等于给定值的查找过程，若查找树为空树，查找失败；否则
（1）若给定key等于根节点的关键字，则查找成功；
（2）若给定值key小于根节点的关键字，则继续在左子树中查找；
（3）若给定值key大于根节点的关键字，则继续在右子树中查找。
二查找树的插入操作
若二叉查找树为空，则插入结点为新的根节点；否则，在二叉查找树进行查找，若查找成功，则不需要插入该结点；查找不成功，则作为查找失败前的最后一个结点的孩子结点插入该结点。
二叉查找树的删除操作
从二叉查找树中删除一个结点，要保持删除后所得的二叉树仍满足二叉树找书的性质。删除结点需要从以下三种情况讨论:
（1）被删结点为叶子结点，此时删除该结点不影响其他结点的关系，因此仅需修改其双亲结点的相应指针即可。
（2）被删结点只有左子树或右子树，则只需保持该结点的子树和其双亲之间原有的关系即可，即删除该结点之后，它的子树种的结点仍在其双亲的左子树或右子树上，因此只需要将其左子树或右子树直接链接到其双亲结点，成为其双亲结点的子树即可。
（3）被删结点的左右子树均不空。此时若将二叉查找树看作一个有序序列，为保持其左子树和右子树的有序关系，可用中序遍历的直接前驱结点替代被删结点，即将被删结点赋值为中序遍历的直接前驱结点，然后从二叉查找树上删去这个前驱结点，使得删除一个结点之后的二叉查找树上其余结点之间的有序关系不变，而其前驱结点由于只有左子树容易删除。
