二叉排序树（Binary Sort Tree）：或者是一颗空树，或者是具有以下性质的树：（1）若它的左子树不空，则左子树上所以结点的值均小于它的根节点的值；（2）若它的右子树不空，则右子树上的所以结点的值均大于它的根节点的值；（3）它的左、右子树也分别是二叉排序树。

二叉排序树的基本操作均可以在O(h)时间内完成（算法导论p165）。

相关操作代码如下：

int InsertBST(BiTree &T, int key)//递归插入
{
	if (T == NULL)
	{
		T = new BiNode;
		T->data = http://www.mamicode.com/key;>测试代码：
int main()
{
	const int n = 10;
	int a[n] = {3, 2, 8, 6, 1, 4, 5, 7, 1, 3};
	BiTree T;
	CreateBST(T, a, n);
	InOrderTraverse(T);
	cout << endl;

	BiNode *p;
	for (int i = 1; i < 10; i++)
	{
		p = SearchBST_(T, i);
		if (p != NULL)
			cout << p->data << endl;
	}

	int b[5]={0, 2, 6, 1, 7};
	int ret;
	for (int i = 0; i < 5; i++)
	{
		ret = DeleteBST(T, b[i]);
		if (ret == 0)
			cout << "删除 " << b[i] << " 失败" << endl;
		else
		{
			cout << "删除 " << b[i] << " 后: " ;
			InOrderTraverse(T);
			cout << endl;
		}
	}

	DestoryBST(T);
	getchar();
	return 0;
}
参考：数据结构C语言版、算法导论（关于删除结点操作，该书p173页有注记）