#include<stdio.h>
#include<stdlib.h>
/*
递归前中后遍历
*/
typedef struct node
{
int data;
struct node*left;
struct node*right;
}BTnode;
BTnode*CreateTree(int a[],int n){
BTnode*root,*c,*p,*pa;
int i;
root=(BTnode*)malloc(sizeof(BTnode));
root->data=a[0];
root->left=root->right=NULL;//建立根节点
for(i=1;i<n;i++)
{
p=(BTnode*)malloc(sizeof(BTnode));
p->data=a[i];
p->left=p->right=NULL;
c=root; //根节点给C指针
while(c)
{ //判断p结点时属于左子树还是右子树
pa=c; //pa指针是p结点的父节点
if(c->data>p->data)
c=c->left;
else
c=c->right;
}
if(pa->data>p->data) //p结点时父节点的左孩子还是右孩子
pa->left=p;
else
pa->right=p;
}
return root;
}
BTnode * Query(BTnode*root,int key)
{
if(!root) //二叉树没有key
return NULL;
else if(root->data == key)
return root;
else if(key <root->data ) //key值小于当前结点的值，把指针给当前结点的左孩子继续比较
return Query(root->left,key);
else if(key >root->data ) //key值大于当前结点的值，把指针给当前结点的右孩子继续比较
return Query(root->right,key);
}
void Forder(BTnode*root)
{
if(root){
printf("%d",root->data);
printf("\n");
Forder(root->left);
Forder(root->right);
}
}
void Inorder(BTnode*root)
{
if(root){
Inorder(root->left);
printf("%3d",root->data);
printf("\n");
Inorder(root->right);
}
}
void Porder(BTnode*root)
{
if(root){
Porder(root->left);
Porder(root->right);
printf("%6d",root->data);
printf("\n");
}
}
int main(void)
{
BTnode*root;
int *a;
int n;
int i;
printf("请输入n=");
scanf("%d",&n);
a=(int*)malloc(n*sizeof(int));
printf("请输入数组a[]=");
for(i=0;i<n;i++)
scanf("%d",&a[i]);
root=CreateTree(a,n);
Forder(root);
Inorder(root);
Porder(root);
root = Query(root,10);
if(!root)
printf(" 二叉树中没有key");
else
printf("%d",root->data);
}
二叉排序树的查找
原文：http://blog.51cto.com/13645380/2156863
