1、 二叉排序树的定义
2、 二叉排序树的查找：二叉排序树的查找时从根结点开始，沿某一个分支逐层向下进行比较的过程。若相等，则查找成功；若不等，则当根节点的关键字大于给定关键字值时，在根结点的左子树中查找，否则在根结点的右子树中查找。二叉树非递归查找算法如下：
BSTNode *BST_Search(BiTree T,ElemType key,BSTNode *&p){
//查找函数返回指向关键字值为key的结点指针，若不存在，返回NULL
P=NULL; //p指向被查找结点的双亲，用于插入和删除操作
While(T!=NULL&&key!=T->data){
P=T;
If(keydata) T=T->lchild;
Else T=T->rchild;
}
Return T;
}
3、 二叉排序树的插入
描述代码如下：
Int BST_Insert(Bitree &T,KeyType k){
//在二叉排序树T中插入一个关键字为k的结点
If(TNULL){ //原树为空，新插入的记录为根节点
T=(BiTree)malloc(sizeof(BSTNode));
T->key=k;
T->lchild=T->rchild=NULL;
Return 1; //返回1，表示成功
}
Else if(kT->key) //树中存在相同关键字的结点
Return 0;
Else if(kkey) //插入到T的左子树中
Return BST_Insert(T->lchild,k);
Else //插入到T的右子树中
Return BST_Insert(T->rchild,k);
}
4、 二叉排序树的构造
Void Creat_BST(BiTree &T,KeyType str[],int n){
//用关键字数组str[]建立一个二叉排序树
T=NULL; //初始化时bt为空树
Int i=0;
While(i
