btree.c

二叉排序树：对随机生成的一些数构建二叉排序树

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

#define null 0
#define n 100

typedef int keytype;

typedef struct node
{
	keytype key;//二叉排序树结点的关键字域
	struct node *lchild;
	struct node  *rchild;
}bstnode; //二叉排序树结点结构

typedef bstnode *bstree;//二叉排序树类型定义



void insertbst(bstree *tptr,keytype key)
{
	bstnode *ins, *p, *pf;
	int l;
	ins=(struct node *) malloc (sizeof(struct node));
	ins->key=key;
	ins->lchild=NULL;
	ins->rchild=NULL;
	if(*tptr==null) *tptr=ins;
	else {
		p=*tptr;
		while(p) {
			pf=p;
			if(key<p->key)   {p=p->lchild;l=1;}
			else             {p=p->rchild;l=0;}
		}
		if(l) pf->lchild=ins;
		else  pf->rchild=ins;
	}



}//end of insertbst

void createbst(bstree *t)
{
	//创建一棵二叉排序树t
	keytype key;
	int i,m;

	//随机输入100个以内的数据生成二叉排序树
	m = rand()%100;
	printf("random source data:");
	for(i=1; i<=m; i++)
	{
			key=rand()%100;;
			printf("%d ",key);
			insertbst(t,key);//将关键字key插入到二叉排序树t中
	}
	printf("\n");
	
}//end of createbst 

void inorder(bstree t)
{
	//对二叉排序树t进行中序遍历
	if (t)
	{
		inorder(t->lchild);//中序遍历左子树
		printf(" %d",t->key);//访问根结点
		inorder(t->rchild);//中序遍历右子树
	}//end of if 
}//end of inorder


void main()//主函数
{
	bstree t=null,q=null;
	
	srand( (unsigned)time( NULL ) );
	
	createbst(&t);//创建一棵二叉排序树t
	printf("\nbst data:");
	
	inorder(t);//输出二叉排序树t的中序遍历序列
	printf("\n");
}