tree sort.cpp

用二叉树算法实现的排序

#include <stdio.h>
#include<time.h>
#include<stdlib.h>
typedef struct T{//定义树节点
struct T *l;
struct T *r;
long value;
}TREE;

TREE *I(TREE *head,long q)//插入节点
{
TREE *p, *parent;
bool i;
TREE *newnode=new TREE;
p=NULL;
newnode->value=q;
newnode->l=NULL;
newnode->r=NULL;
if(!head)	return newnode;
p=head;
i=true;
while(p){
parent=p;
if(p->value>q)
	{
	p=p->l;
	i=true;
	}
else
	{
	p=p->r;
	i=false;
	}
}
if(i)
parent->l=newnode;
else
parent->r=newnode;
return head;
}

TREE *CREATE(long a[], long n)//建立有序二叉树
{
TREE *head=NULL;
long i;
for(i=1;i<=n;i++)
head=I(head,a[i]);
return head;
}
void OUT(TREE *p){
	if(!p)
	return;
    OUT(p->l);
	printf("%d ",p->value);
	OUT(p->r);
}

void main()
{
clock_t t1,t2;
double time;
long i,n,a[100000];
scanf("%d",&n);
for(i=1;i<=n;i++)
a[i]=rand();
t1=clock();
CREATE(a,n);
t2=clock();
time=(double)(t2-t1)/CLK_TCK;
OUT(CREATE(a,n));
printf("%f",time);
}