二叉排序树
二叉排序树的性质：每个节点的左子树中的所有节点的关键字都小于该节点的关键值，而右子树中的所有节点的关键字都大于该节点的关键值。

二叉排序树的构造
二叉排序树的构造是指将一个给定的数据元素构造为相应的二叉排序树。

基本思想为：

对于任给的一组数据元素{ R1, R2, …, Rn } , 可按以下方法来构造二叉排序树：

(1) 令R1为二叉树的根;

(2) 若R2

(3) 对R3, …, Rn结点，也是依次与前面生成的结点比较以确定输入结点的位置。

这一方法中的一个结点插入，可用以下的非递归插入算法来实现：

**************************************\
函数功能：创建二叉排序树
输入：    原始数组
输出：    二叉排序树的根节点
\**************************************/ 
bstnode* CreatBst(int* arrayA,int n) 
{ 
    bstnode *t,*s; 
    t=NULL; 
    for(int i=1;ikey=arrayA[i];//从arrayA[1]开始  
        s->lchild=s->rchild=NULL; 
        t=InsertBst(t,s);//调用插入函数  
    } 
    return t; 
} 

/**************************************\
函数功能：创建二叉排序树
输入：    原始数组
输出：    二叉排序树的根节点
\**************************************/
bstnode* CreatBst(int* arrayA,int n)
{
 bstnode *t,*s;
 t=NULL;
 for(int i=1;ikey=arrayA[i];//从arrayA[1]开始
  s->lchild=s->rchild=NULL;
  t=InsertBst(t,s);//调用插入函数
 }
 return t;
}

 

二叉排序树的插入
插入过程可以由下图一目了然：

从上述的插入过程可以看出每次插入的新结点都是二叉排序树的叶子结点并且不需移动其他结点，所以在进行插入这样的操作时比向量（线性表）操作更方便。由于对二叉排序树进行中序遍历时，可以得到一个按关键字大小排列的有序序列，所以对一个无序序列可通过构造二叉排序树和对这个排序树进行中序遍历来产生一个有序序列。
具体的程序实现如下：

**************************************\
函数功能：向二叉排序树中插入节点
输入：    二叉排序树的根节点、要插入的节点
输出：    二叉排序树的根节点
\**************************************/ 
bstnode* InsertBst(bstnode* t,bstnode* s) 
{ 
    bstnode *f,*p; 
    p=t; 
    while(p!=NULL) 
    { 
        f=p; 
     
        if(s->key<=p->key) 
            p=p->lchild; 
        else 
            p=p->rchild; 
    } 
    if(t==NULL) 
        return s; 
    if(s->keykey) 
        f->lchild=s; 
    else 
        f->rchild=s; 
    return t; 
 
} 

/**************************************\
函数功能：向二叉排序树中插入节点
输入：    二叉排序树的根节点、要插入的节点
输出：    二叉排序树的根节点
\**************************************/
bstnode* InsertBst(bstnode* t,bstnode* s)
{
 bstnode *f,*p;
 p=t;
 while(p!=NULL)
 {
  f=p;
 
  if(s->key<=p->key)
   p=p->lchild;
  else
   p=p->rchild;
 }
 if(t==NULL)
  return s;
 if(s->keykey)
  f->lchild=s;
 else
  f->rchild=s;
 return t;

}