二叉排序树（Binary Sort Tree）又称二叉查找树（Binary Search Tree），亦称二叉搜索树。 

它或者是一棵空树；或者是具有下列性质的二叉树： 

（1）若左子树不空，则左子树上所有结点的值均小于它的根结点的值； 

（2）若右子树不空，则右子树上所有结点的值均大于它的根结点的值； 

（3）左、右子树也分别为二叉排序树；

上机代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cstdlib>
#include <cmath> 
using namespace std;

#define KeyType int 
#define EQ(a,b) ((a)==(b))
#define LT(a,b) ((a)< (b))
#define LQ(a,b) ((a)<=(b))
#define FALSE 0
#define TRUE 1 
#define OK 1
//#define OVERFLOW 0
#define ERROR 0
#define STACK_INIT_SIZE 100
#define STACKINCREMENT 10

typedef struct  
{
	KeyType key;                                                //关键字域
} ElemType;                                                                                   

typedef struct BiTNode               //定义二叉树二叉链表
{
	ElemType  data;
	struct BiTNode *lchild, *rchild;
}BiTNode,*BiTree,*SElemType;

typedef struct
{
	SElemType *base;
	SElemType *top;
	int stacksize;
}SqStack;

int DestroyBiTree(BiTree &T) //销毁树
{
	if(T!=NULL)
	free(T);
	return 0;
}

int ClearBiTree(BiTree &T) //清空树
{
	if(T!=NULL)
	{
		T->lchild=NULL;
		T->rchild=NULL;
		T=NULL;
	}
	return 0;
}

int SearchBST(BiTree T,KeyType key,BiTree f,BiTree &p)    //查找关键字,指针p返回
{
	if(!T)
	{
		p=f;
		return FALSE;
	}
	else if EQ(key,T->data.key) 
	{
		p=T;
		return TRUE;
	}
	else if LT(key,T->data.key)
		return SearchBST(T->lchild,key,T,p);
	else 
		return SearchBST(T->rchild,key,T,p);
}

int InsertBST(BiTree &T,ElemType e)   //插入节点元素
{
	BiTree s,p;
	if(!SearchBST(T,e.key,NULL,p))
	{
		s=(BiTree)malloc(sizeof(BiTNode));
		s->data=http://www.mamicode.com/e;>

数据结构 - 二叉排序树的实现