二叉排序树的定义：（1）左子树非空，则左子树上所有结点的值均小于根节点的值。

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

                                     （3）左右子树也分别是一颗二叉排序树。

 根据二叉排序树的定义可以得出   ，左子树结点值<根结点值<右子树结点值，所以得出重要结论” 对二叉排序树进行中序遍历，可以得到一个递增的有序序列“             

下面用代码演示“增，删，改，查”等功能

二叉排序树的非递归查找算法

 1 BSTNode *BST_Search(BiTree T,ElemType key)
 2 {
 3     while(T!=NULL&&key!=T->data)      //若树空或等于根节点值，则结束循环
 4       { 
 5        if(k<T->data)
 6            T=T->lchild;         //小于则在左子树查找
 7        else
 8             T=T->rchild;        //大于则在右子树上查找
 9       }
10     return T;
11 }

二叉排序树的插入

int BST_Insert(BiTree &T,KeyType k)
{
   if(T==NULL)
   {
       T=(BiTree)malloc(sizeof(BSTNode)); //生成新结点
       T->key=k;
       T->lchild=T->rchild=NULL;
       return 1;                              //返回1，插入成功
   }
  else if(k==T->key)    //树中存在相同关键字的结点，插入失败
         return 0;
   else  if(k<T->key)    //插入T左子树中
         return BST_Insert(T->lchild,k);
   else
          return BST_Insert(T->rchild,k):
}

二叉排序树的构造

void Create_BST(BiTree &T,KeyType str[],int n)  //n是数组长度
{
    T=NULL;        //初始时T为空树
    int i=0;
    while(i<n)
    {
        BST_Insert(T,str[i]);       //将每一个关键字插入到二叉排序树中
        i++;
   }
}