1.什么是二叉排序树呢？（Binary Sort Tree）

二叉排序树具有以下几个特点。

（1）若根节点有左子树，则左子树的所有节点都比根节点小（就是左子树结点要比双亲结点小）。

（2）若根节点有右子树，则右子树的所有节点都比根节点大（就是右子树结点要比双亲结点大）。

（3）根节点的左，右子树也分别为二叉排序树。

2.构造一棵二叉排序树的目的

其实并不是为了排序，而是为了提高查找和插入删除的效率。

下面是二叉排序树的图示，通过图可以加深对二叉排序树的理解。可以看到，根结点50的左边所有的子结点都比它小，根结点50的右边所有的子结点都比它大

3.下面是二叉排序树常见的操作及思路。

（1）插入节点（要先进行查找，查找结束后，没有，就在那个位置进行插入）

思路：比如我们要插入数字20到这棵二叉排序树中。那么步骤如下：

1)首先将20与根节点进行比较，发现比根节点小，所以继续与根节点的左子树30比较。

2) 发现20比30也要小，所以继续与30的左子树10进行比较。

3) 发现20比10要大，所以就将20插入到10的右子树中。

（2）查找节点（递归）

比如我们要查找节点10，那么思路如下：

1) 还是一样，首先将10与根节点50进行比较大小，发现比根节点要小，所以继续与根节点的左子树30进行比较。

2) 发现10比左子树30要小，所以继续与30的左子树10进行比较。

3) 发现两值相等，即查找成功，返回10的位置。

（3）删除节点（不能因为删除了结点，而让这棵树变得不满足二叉树的特性）

删除节点的情况相对复杂，主要分以下三种情形：

1) 删除的是叶节点(即没有孩子节点的)。比如20，删除它不会破坏原来树的结构，最简单。如图所示。

2) 删除的是单孩子节点。比如90，删除它后需要将它的孩子节点与自己的父节点相连。情形比第一种复杂一些。

3) 删除的是有左右孩子的节点。

这种情况会稍微复杂一些，我们采用覆盖，再删除的方式进行解决。也就是曲线解决。直接将有左子树也有右子树的结点干掉似乎不是很好实现，因为这样会破坏二叉排序树的结果。我们可以间接的去做。可以分为下方的两步。

第一步：查找删除结点右子树中最小的那个值，也就是右子树中位于最左方的那个结点。然后将这个结点的值的父节点记录下来。并且将该节点的值赋给我们要删除的结点。也就是覆盖。

第二步：然后将右子树中最小的那个结点进行删除，该节点肯定符合上述三种情况的某一种情况，所以可以使用上述的方法进行删除。

四、二叉排序树与堆的区别

在二叉排序树中，每个结点的值均大于其左子树上所有结点的值，小于其右子树上所有结点的值，对二叉排序树进行中序遍历得到一个有序序列。所以，二叉排序树是结点之间满足一定次序关系的二叉树；

堆是一个完全二叉树，并且每个结点的值都大于或等于其左右孩子结点的值（这里的讨论以大根堆为例），所以，堆是结点之间满足一定次序关系的完全二叉树。

具有n个结点的二叉排序树，其深度取决于给定集合的初始排列顺序，最好情况下其深度为log n（表示以2为底的对数），最坏情况下其深度为n；

具有n个结点的堆，其深度即为堆所对应的完全二叉树的深度log n 。

在二叉排序树中，某结点的右孩子结点的值一定大于该结点的左孩子结点的值；

在堆中却不一定，堆只是限定了某结点的值大于（或小于）其左右孩子结点的值，但没有限定左右孩子结点之间的大小关系。

在二叉排序树中，最小值结点是最左下结点，其左指针为空；最大值结点是最右下结点，其右指针为空。

在大根堆中，最小值结点位于某个叶子结点，而最大值结点是大根堆的堆顶（即根结点）。

二叉排序树是为了实现动态查找而设计的数据结构，它是面向查找操作的，在二叉排序树中查找一个结点的平均时间复杂度是O(log n)；

堆是为了实现排序而设计的一种数据结构，它不是面向查找操作的，因而在堆中查找一个结点需要进行遍历，其平均时间复杂度是O(n)。

http://www.cnblogs.com/ludashi/p/6004024.html

http://blog.csdn.net/gisredevelopment/article/details/49945785

http://www.cnblogs.com/GumpYan/p/5754731.html

http://www.cppblog.com/guogangj/archive/2009/10/26/99502.html