用c语言实现二叉排序树创建

二叉排序树是一种特殊的二叉树，它的左子树上所有结点的关键字均小于根结点的关键字，右子树上所有结点的关键字均大于根结点的关键字。在C语言中，可以通过结构体和指针来实现二叉排序树的创建。具体实现方法如下：

1.定义二叉排序树结点的结构体：

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

2.在二叉排序树中查找值为key的结点：

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;
}

3.在二叉排序树中插入关键字为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);
}

4.按照str[]中的关键字序列建立二叉排序树：

void Creat_BST(BSTree &T, int str[], int n){
    T=NULL;
    int i=0;
    while(i<n){
        BST_Insert(T,str[i]);
        i++;
    }
}