当线性表作为查找表的组织形式时，可以有三种查找法，其中以二分查找效率最高。但由于二分查找要求表中结点按其关键字有序组织，且不能用链表作为存储结构，因此，当表的元素插入或删除操作频繁时，为维护表的有序性，势必要移动表中大量的结点，这种由移动结点引起的额外的时间开销，就会抵消二分查找的优点。在这种情况下，可采用二叉树作为存储结构，在此将它们统称为树表。

二叉排序树

（1）二叉排序树又称为二叉查找树，是一种特殊的二叉树。其定义为：

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

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

（3）左、右子树本身又各是一棵二叉排序树 

（2）二叉排序树定义：

typedef struct node{
    KeyType key;

    Datatype other;

    struct node *lchild，*rchild;

}BSTNode;

1.二叉排序树的插入和生成

①在二叉排序树中插入新的结点，只要保证插入后仍符合二叉排序树的定义即可。插入过程如下：

（1）若二叉排序树为空，则待插入结点*s作为根结点插入到空树中

（2）当二叉树非空，将待插入结点的关键字s->key和树根的关键字t->key进行比较，若s->key=t->key，则说明此树中已有此结点，无需插入；若s->keykey，则将待插入结点*s插入到根的左子树中，否则将*s插入根的右子树中

（3）子树中的插入过程与步骤（1）（2）相同，直到把结点*s作为新的结点插入二叉排序树中，或直到发现该树中已有此*s结点为止。

②二叉排序树的插入算法

BSTNode *INSERTBST(BSTNode *s,BSTNode t){
    BSTNode *f,*p;
    if(t==NULL) return s;
    p=t;
    while(p!=NULL){
        f=p;
        if(s->key==p->key) return t;
        if(s->keykey) p=p->lchild;
        else p=p->rchild;
    }
    if(s->keykey) f->lchild=s;
    else f->rchild=s;
    return t;
}

③二叉排序树的生成算法 

BSTNode *CREATBST(){
    BSTNode *t,*s;
    KeyType key,endflag=0;
    DataType data;
    t=NULL;
    scanf("%d",&key);
    while(k!=endflag){
        s=malloc(BSTNode *)malloc(sizeof(BSTNode));
        s->lchild=s->rchild=NULL;
        s->key=key;
        scanf("%d",data);
        s->other=data;
        t=INSERTBST(t,s);
        scanf("%d",&key);
    }
    return 0;
} 

2. 二叉排序树的查找 

①二叉排序树的查找算法

BSTNode *BSTSearch(BSTNode *t,KeyType t){
    BSTNode *p=t;
    while(p!=NULL){
        if(p->key==k) return p;
        if(p->key>k)
        p=p->lchild;
        else p=p->rchild;
    }
} 

②显然，在二叉排序树上进行查找，若查找成功，则是从根结点出发走一条从根到待查结点的路径；若查找不成功，则是从根结点出发走一条从根到某个叶子结点的路径。因此，与二分法类似，和关键字比较的次数不超过树的深度。