#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <assert.h>
 
struct data{
  int integer;              
  int level;                
  struct data *rlink;       
  struct data *llink;
  struct data *connect;     
};
 
struct QUEUE{
    struct data *rear,*front;
};
 
void insertion(void);     
void access(int);      
void preorder(struct data*);            //preorder traversal
void inorder(struct data*);             //inorder traversal
void postorder(struct data*);           //postorder traversal
void breadth_first(struct data*);       //breadth-first traversal
 
struct data *root, *ptr;
 
 
int main()
{
    int i=0;
    int a;
    int exit=0;
    srand(time(NULL));
 
 
    FILE *fp;                         
    fp=fopen("data.txt","w");
    assert( fp != NULL );
    for(i=0;i<10;i++)
    fprintf(fp,"%d\n",rand()%100+1);
    fclose(fp);
 
    insertion();
    while(exit!=5)
    {
        printf("\n----HELLO!THIS IS PROJECT4!----\n");
        printf("(1)preorder\n(2)inorder\n(3)postorder\n(4)breadth-first\n(5)exit\n");
        printf("please select one operation:");
        scanf("%d",&a);
 
       switch(a)
       {
        case 1:
              preorder(root);
              break;
 
        case 2:
              inorder(root);
              break;
 
        case 3:
              postorder(root);
              break;
 
        case 4:
              breadth_first(root);
              break;
 
        case 5:
            printf("exit!\n");
            exit = 5;
            break;
       }
      }
    return 0;
}
 
void insertion(void)
{
    FILE *fptr;
    int integer;
    printf("\nFile loading...\n");
    if((fptr = fopen("data.txt","r")) == NULL)
    {
         printf("failed......");
         return;
    }
    while(fscanf(fptr,"%d\n",&integer)!=EOF)
     access(integer);
     fclose(fptr);
     printf("loading success\n");
}
 
void access(int integer)
{
    struct data *node, *prev;
    ptr = (struct data *)malloc(sizeof(struct data));
    ptr->integer=integer;
    ptr->llink = ptr->rlink = NULL;
    if(root == NULL)     
       root = ptr;
    else              
    {
        node = root;
        while(node!=NULL)
        {
            prev = node;
            if((ptr->integer) < (node->integer))     
                node = node->llink;
            else
                node = node->rlink;                  
        }
        if((ptr->integer) < (prev->integer))
                prev->llink = ptr;
        else
                prev->rlink = ptr;
     }
}
 
void preorder(struct data *node)
{
    if(node!=NULL)
    {
      printf("%d.",node->integer);
      preorder(node->llink);
      preorder(node->rlink);
    }
}
 
void inorder(struct data *node)
{
    if(node!=NULL)
    {
        inorder(node->llink);
        printf("%d.",node->integer);
        inorder(node->rlink);
    }
}
 
void postorder(struct data *node)
{
    if(node!=NULL)
    {
        postorder(node->llink);
        postorder(node->rlink);
        printf("%d.",node->integer);
    }
 
}
 
void breadth_first(struct data *node)
{
    struct QUEUE *p;
    p = (struct QUEUE *)malloc(sizeof(struct QUEUE));
    int i;
 
     for(i=0;;i++)
     {
      if(i==0)
      {
            p->front=root;                      
            root->level=i+1;                    
            printf("%d.",root->integer);
            p->rear=root;
      }
      else
      {
       while(p->front->level==i)
       {
            if(p->front->llink!=NULL)            
                {
                    p->rear->connect = p->front->llink;
                    p->rear = p->front->llink;
                    p->rear->level = i+1;
                    printf("%d.",p->rear->integer);
                }
            if(p->front->rlink!=NULL)            
                {
                    p->rear->connect = p->front->rlink;
                    p->rear = p->front->rlink;
                    p->rear->level=i+1;
                    printf("%d.",p->rear->integer);
                }
            if(p->front->connect!=NULL)
                {
                     p->front=p->front->connect;
                }
            else
                {
                    break;
                }
       }
      }
 
      if((p->front->llink==NULL) && (p->front->rlink==NULL) && (p->front->connect==NULL))  
      {
        break;
      }
 
     }
}