/*实现一个函数，其参数包含一个整数数组，它首先对数组里的数据排序，而后创建出一棵最佳二叉排序树（假定各数据等权）。写一个主函数，它先调用上述函数构造最佳排序树，然后按照先根序打印树中各结点的值。*/
#include<stdio.h>
#include<malloc.h>
#include<conio.h>
#include<string.h>

typedef int KeyType;
typedef char InfoType;
typedef struct Node
{
KeyType key;
InfoType data;
struct Node *rchild, *lchild;
} * BNode;

int InsertSort(int R[],int n)
{
int i=1,j,k;
int temp;

for(i=1;i<n;i++)
{

temp=R[i];
j=i-1;

while(j>=0&&temp<R[j])
{
R[j+1]=R[j];
j--;
}

R[j+1]=temp;
printf(" i= %d",i);

for(k=0;k<n;k++)
printf(" %3d ",R[k]);
printf( "\n");

}

}

int InsertTree(BNode p, KeyType k)
{

if(p==NULL)
{
p=(BNode)malloc(sizeof(BNode));
p->key=k;
p->lchild=p->rchild=NULL;
return 1;
}

else
{
if(k==p->key)
{
printf("k exist!!");
return 0;
}
else if(k>p->key)

InsertTree(p->rchild,k);

else

InsertTree(p->lchild,k);
}

}

BNode * CreatTree(int R[],int n)
{
BNode bt;
int i;
bt=(BNode *)malloc(sizeof(struct Node));

if(bt==NULL)
{
printf("fail to get space");
return NULL;
}

for(i=0;i<n;i++)
{
InsertTree(bt,R[i]);
return bt;
}
}

void DispTree(BNode bt)
{
if(bt==NULL)
printf("empty tree");

else
{
printf(" %3d",bt->key);

if(bt->rchild!=NULL||bt->lchild!=NULL)
{
printf("(");
DispTree(bt->lchild);
if(bt->rchild!=NULL)
printf(",");
DispTree(bt->rchild);
printf(")");
}
}
}

void main(){
int R[10],i,n=10;
BNode bt;
clrscr();

printf("first please input ten nums as element of the array");
for(i=0;i<10;i++)
{
scanf("%d",&R[i]);
}
InsertSort(R,n);
for(i=0;i<n;i++)
printf("%3d",R[i]);

bt=CreatTree(R,10);
DispTree(bt);
printf("programe over");
}

/*希望您将回复copy一份到我邮箱里 shijunyi@126.com 3x!!!