二叉排序树

左子树结点值<根结点值<右子树结点值

二叉排序树结点

typedef struct BSTNode{
    int key;
    struct BSTNode *lchild,*rchild; 
    }BSTNode *BTSTree; 

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

BSTNode *BST_Search(BSTree T,int key){
    while(T!= NULL&&key != T->key)  //如果树空或等于根结点值，则结束循环
    { if(key<T->key) T = T->lchild;
     else T = T->rchild; 


 }  return T; 
 }   //最坏空间复杂度为 O（1) 
（递归算法）
BSTNode *BSTSearch(BSTtee T,int key){
    if(T == NULL)
    return NULL;  //查找失败 
    if(key == T->key)
    return T; //查找成功 
    else if(key < T->key)
    return   BSTSearch(T->lchild,key); //在左子树中找 
    else return BSTSearch(T->rchild,key);//在右子树中找 
}  //最坏空间复杂度为 O（h) 

二叉排序树的插入 若二叉排序树为空，则直接插入结点；否则若关键字k小于根节点
值，则插入到左子树中，否则插入右子树中，若关键字k大于结点值，则插入到右子树

//在二叉排序树中插入关键字为k的新节点（递归实现）
int BST_Insert(BSTree &T,int k){
    if(T == NULL){  //原树为空，新插入的结点为根节点
    T=(BSTree)malloc(sizeof(BSTNode));
    T->key = k;
    T->lchild = T->rchild = NULL;
    return 1; //插入成功 

    }
    else if(k == T->key)
     return 0;   //如果有相同关键字的结点则插入失败 
    else if(k < T->key)
     return BST_Insert(T->lchild,k); //插入左子树 
    else 
    return BST_Insert(T->rchild,k);//插入右子树 
} 

二叉排序树的构造 
void Creat_BST(BSTree &T,int str[],int n){
    T=NULL;//初始时 T为空树
    int i = 0;
    while (i<n){  //依次将每个关键字插入二叉排序树中 
        BST_Insert(T,str[i]);
        i++
    } 
}