二叉排序树的创建

首先二叉排序树的查找，这里father用于记录访问点的前序，如果找到关键字，也就是程序中的e,则p指向这个结点，而father则指向p的父结点，如果没有找到关键字，则father指向查找路径上的最后一个结点，也可以理解为要插入的结点（关键插入father的左子树或者右子树）

typedef struct node {

int data;
struct node *lchild;
struct node *rchild;
}BSTNode,*BSTree;

BSTNode *searchBS(BSTNode * root,int e,BSTree &father){

//father 为空是根结点，p为空是没有这个点
BSTNode * p = root;
father =NULL;

while(p!=NULL&&p->data!=e){

father = p;
if(p->data<e) p=p->rchild;
else p = p->lchild;

}
return p;

} 这是一个非递归的程序，也可以写成递归的 ，若查找关键字成功，则p指向关键字结点，没有找到，p 指向查找路径上的最后一个结点

bool SearchBST(BSTree root,int data,BSTree father,BSTree &p)
{
if(!root)
{
p=father;
return false;
}
else if(data==root->data)
{
p=root;
return true;
}
else if(data<root->data)
return SearchBST(root->lchild,data,root,p);
else if(data>root->data)
return SearchBST(root->rchild,data,root,p);
}
插入程序

bool insertBSTree(BSTree &root ,int e){

BSTNode *p=NULL;
BSTNode *father=NULL;
BSTNode *s=NULL;
p = searchBS(root, e, father);
//SearchBST(root,e,NULL,p);

if(p)return false;
s = (BSTNode *)malloc(sizeof(BSTNode));
s->data = e;
s->lchild = NULL;
s->rchild = NULL;

if(father==NULL) root = s;
else if(e<father->data)
father->lchild = s;
else father->rchild = s;
return true;
}

void orderVisit(BSTNode * root){
if(root){
order Visit(root->lchild);
printf("the order is %d \n" ,root->data);
orderVisit(root->rchild);
}
}

void main(){
BSTNode * root=NULL ;

//为了中序遍历使得到的结果从小到大排序，使用下列数组

int A[7] = {4,2,6,1,3,5,7};

int i = 0;
for(i=0;i<7;i++){
insertBSTree(root,A[i]);
}

orderVisit( root);//中序遍历，得到的结果应该 是1,2,3,4,5,6,7

}