二叉排序树2.c

二叉排序树的实现

#include<stdio.h> 
#include<stdlib.h> 

#define TRUE 1 
#define FALSE 0 

typedef struct BTNode 
{ 
int data; 
struct BTNode *lchild,*rchild; 
}BTNode; /*二叉树的节点类型*/

BTNode *root; 

void Insert(BTNode *s) /*二叉排序树插入一个节点 */
{ 
BTNode *p,*q; 
if(root==NULL) 
root=s; 
else 
{ 
p=root; 
while(p!=NULL) /*当p为空时，q就是可插入的地方 */
{ 
q=p; /*当p向子树节点移动时，q记录p的双亲的位置 */
if(s->data<p->data) /*要插入值比p小*/ 
p=p->lchild; /*左子树中寻找 */
else 
p=p->rchild; /*反之右子树中寻找*/ 
} 
if(s->data<q->data) /*要插入值比插入地方的双亲值小 */
q->lchild=s; /*插入左子树 */
else 
q->rchild=s; /*反之插入右子树 */
} 
} 

int Search(BTNode *s,int n) /*二叉排序中查找数值n */
{ 
BTNode *p; 
p=s; /*每次和p值比较确定位置，p初始为根指针 */
while(p!=NULL) 
{ 
if(n==p->data) return 1; /*找到返回1 */
if(n<p->data) /*值比p值小 */
p=p->lchild; /*左子树中寻找 */
else 
p=p->rchild; /*反之右子树中寻找 */
} 
if(p==NULL) return 0; /*没有找到返回0 */
} 

void print(BTNode *t) /*中序遍历二叉排序数树得到有序数列 */
{ 
if(t!=NULL) 
{ 
print(t->lchild); 
printf("%4d",t->data); 
print(t->rchild); 
} 
} 


void main() 
{ 
BTNode *s; 
int n; 
int i,k; 
root=NULL; 
printf("please input 10 numbers：( There are 10 BTNodes)\n"); 
for(i=0;i<10;i++) 
{ 
scanf("%d",&k); 
s=(BTNode *)malloc(sizeof(BTNode)); 
s->data=k;s->lchild=NULL;s->rchild=NULL; 
Insert(s); 
} 
print(root); 
printf("\nplease input the key.n=?"); 
scanf("%d",&n); 
if(Search(root,n)==1) printf("Found it!"); 
else printf("Failed!"); 
printf("\n"); 
getch();
}
/*说明：没有删除功能，且仅有十个节点*/