1. BST:Binary Sort Tree，二叉排序树
2. p=malloc(...)强制类型转换→p=(BSTNode *)malloc(...)

二叉排序树的存储结构

typedef int KeyType;
typedef int InfoType;
struct BSTNode {
    KeyType key;
    InfoType data;
    struct BSTNode *lchild,*rchild;
};

二叉排序树的查找算法

BSTNode *BSTSearch(BSTNode *bt,KeyType k) {
    if(bt==NULL)
        return NULL;
    else if(bt->key==k)
        return bt;
    else if(k<bt->key)
        return(BSTSearch(bt->lchild,k));
    else
        return(BSTSearch(bt->rchild,k));
}

二叉排序树的插入算法

int BSTInsert(BSTNode *&p,KeyType k) {
    if(p==NULL) {
        p=(BSTNode *)malloc(sizeof(BSTNode));
        p->key=k;
        p->lchild=p->rchild=NULL;
        return 1;
    }
    else if(p->key==k)
        return 0;
    else if(p->key<k)
        return(BSTInsert(p->lchild,k));
    else
        return(BSTInsert(p->rchild,k));
}

构造二叉排序树的算法

void CreateBST(BSTNode *&bt,KeyType str[],int n){
    bt=NULL;
    int i=0;
    while(i<n){
        BSTInsert(bt,str[i]);
        i++;
    }
}