二叉排序树的构建，查找

/*
  基本概念：
1.二叉排序树可以是一颗空树。
2.若左子树不为空，则左子树数据元素的关键字小于根节点数据元素的关键字。
3.若右子树不为空，则右子树数据元素的关键字大于等于根节点数据元素的关键字
4.左右子树也符合二叉排序树
 */


#include
#include


typedef int key_type;
typedef struct data_type{
key_type key;
}data_type;


typedef struct node{
data_type data;
struct node *left_child;
struct node *right_child;
}node;// 二叉排序树数据节点


//查找算法
int search(node *root,data_type x)
{
node *p;
if(root!=NULL){
p=root;
while(p!=NULL){
if(p->data.key==x.key) return 1;
if(x.key>p->data.key) p=p->right_child;
else p=p->left_child;

}
}
return 0;
}
//二叉排序树的插入
/*
首先查找该数据元素是否存在，若存在，不插入，若不存在，则把该数据元素插入到
二叉排序树上查找失败时节点的左孩子或右孩子上，所以这里的查找也要记住当前节点的位置
 */
int insert(node **root,data_type x)
{
node *current,*parent=NULL,*p;
current=*root;
while(current!=NULL){
if(current->data.key==x.key) return 0;
parent=current;
if(current->data.keyright_child;
else current=current->left_child;
}
p=(node*)malloc(sizeof(node));


//生成新的节点
p->data=x;
p->left_child=NULL;
p->right_child=NULL;
if(parent==NULL) *root=p;
else if(x.keydata.key) parent->left_child=p;
else parent->right_child=p;
return 1;
}
//二叉排序树的遍历
void travel(node *root)
{
if(root==NULL) return;
if(root->left_child!=NULL) travel(root->left_child);
printf("%d ",root->data.key);
if(root->right_child!=NULL) travel(root->right_child);
}
int main()
{
data_type test[]={3,45,5,7,8,9,1};
data_type x={9};
node *root=NULL;
int i;
for(i=0;i<7;i++){
insert(&root,test[i]);
}
travel(root);
int s=search(root,x);
if(s==1){
printf("\n数据%d存在。\n",x.key);
}
else printf("\n数据%d不存在。\n",x.key);
return 0;
}