/*

 已知，二叉树存储结构定义见bstree.h，请编写一个算法函数bstree creatBstree(int a[],int n)，

 以数组a中的数据作为输入建立一棵二叉排序树，并将建立的二叉排序树进行中序遍历。

 （提示，a中的原始数据可从data1.txt中读入，实验代码详见lab9_05.c）

 */

 #include "Arrayio.h"

 #include "bstree.h"

 #define N 100

 bstree  creatBstree(int a[],int n)

   { /*根据输入的结点序列，建立一棵二叉排序树，并返回根结点的地址*/

     int i, flag;

     bstree root, p, q;

     root = (bstree)malloc(sizeof(bsnode));

     root->key = a[];

     root->lchild = NULL;

     root->rchild = NULL;

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

     {

         p = root;

         while (true)

         {

             if (a[i]<p->key)

             {

                 if (p->lchild != NULL) { p = p->lchild; flag = ; }

                 else {flag=;break;}

             }

             else if (a[i]>p->key)

             {

                 if (p->rchild != NULL) { p = p->rchild; flag = ; }

                 else {flag=;break;}

             }

             else

             {

                 flag = -; break;

             }

         }

         q = (bstree)malloc(sizeof(bsnode));

         q->key = a[i];

         q->lchild = NULL;

         q->rchild = NULL;

         if (flag==)

             p->rchild = q;

         else if (flag==)

             p->lchild = q;

     }

     return root;

 }

 int  main()

   {

     int n,a[N];

     bstree p,t;

     n=readData(a,N,"data1.txt");

     output(a,n);

     t=creatBstree(a,n);         /*创建二叉排序树*/

     printf("中序遍历：\n");

     inorder(t);                 /*中序遍历二叉排序树*/

     return ;

  }

 /**************************************/

 /*         二叉排序树用的头文件       */

 /*          文件名：bstree.h          */

 /**************************************/

 #include<stdio.h>

 #include<stdlib.h>

 typedef struct node1            /*二叉排序树结点定义*/

  {

   int key;                      /*结点值*/

   struct node1 *lchild,*rchild; /*左、右孩子指针*/

   }bsnode;

 typedef bsnode *bstree;

 /*---中序遍历二叉排序树----*/

 void inorder(bstree t)

   { if (t) {    inorder(t->lchild);

                 printf("%8d",t->key);

                 inorder(t->rchild);

              }

    }

 #include <stdio.h>

 #include <stdlib.h>

 #include <time.h>

 #define MAX 500000

 /*从文件中读入数据存入数组a*/

 int readData(int a[], int n,char *f )  /*函数返回成功读入的数据个数*/

 {

     FILE *fp;

     int i;

     fp=fopen(f,"r");

     if (fp==NULL)   return ;

     else

     {

         for (i=;i<n && !feof(fp);i++)

             fscanf(fp,"%d",&a[i]);

         fclose(fp);

         return i;

     }

 }

 /*存盘函数*/

 void saveData(int a[],int n, char *f )

 {

     FILE *fp;

     int i;

     fp=fopen(f,"w");

     if (fp==NULL)   printf("文件建立失败！");

     else

     {

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

             {   if (i%==) fprintf(fp,"%c",'\n');

                 fprintf(fp,"%8d",a[i]);

             }

         fclose(fp);

     }

 }

 /*输出长度为n的整型数组*/

 void output(int a[],int n)

 {  int i;

    printf("\n数组的内容是：\n");

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

      { if (i%==) printf("\n");

        printf("%7d",a[i]);

      }

   printf("\n");

 }