#include <graphics.h>
#include <stdio.h>
#include <stdlib.h>
#include <dos.h>
#include <time.h>
typedef struct TREE
{
   char data;/*樹的結點數據*/
   struct TREE *lchild;
   struct TREE *rchild;
   int x;/*樹的x坐標*/
   int y;/*樹的y坐標*/
}Tree;
struct OUTPUT
{
   int x;/*三種遍歷的x坐標*/
   int y;/*三種遍歷的y坐標*/
   int num;
}s;
int nodeNUM=0;/*統計當前的結點數字,最多26個*/
char way;/*自動建立樹和手動建立樹的標志,2手動,1自動*/
char str[3];/*顯示結點數據的字符串*/
void Init();/*圖形初始化*/
void Close();/*圖形關閉*/
Tree *CreatTree();/*文本模式下創建樹的過程*/
Tree *InitTree(int h,int t,int w);/*創建樹,h層次,t橫坐標,w樹之間的寬度,n樹的建立方式*/
void DrawTree(Tree *t);/*用圖形顯示創建好的樹*/
void Preorder(Tree *t);/*前序遍歷*/
void Midorder(Tree *t);/*中序遍歷*/
void Posorder(Tree *t);/*后序遍歷*/
void DrawNode(Tree *t,int color);/*遍歷時顯示每個結點的過程*/
void ClrScr();/*清空樹的區域*/
void main()
{
   Tree *root;
   randomize();
   root=CreatTree();/*創建樹*/
   Init();
   DrawTree(root);/*每次遍歷前顯示白色的樹*/
   sleep(1);
   s.x=100;s.y=300;s.num=1;/*每次遍歷前設置顯示遍歷順序顯示的x,y坐標*/
   Preorder(root);/*前序遍歷*/
   getch();
   ClrScr();
   DrawTree(root);
   sleep(1);
   s.x=100;
   s.y=350;
   s.num=1;
   Midorder(root);/*中序遍歷*/
   getch();
   ClrScr();
   DrawTree(root);
   sleep(1);
   s.x=100;
   s.y=400;
   s.num=1;
   Posorder(root);/*后序遍歷*/
   Close();
}
/*清空樹的區域*/
void ClrScr()
{
   setcolor(BLACK);
   setfillstyle(SOLID_FILL,BLACK);
   bar(0,20,640,280);
}
/*文本模式下創建樹的過程*/
Tree *CreatTree()
{
   Tree *root;
   clrscr();
   printf("please input n\n");
   printf("1.computer creat\n");
   printf("2.people creat\n");
   way=getch();/*輸入創建樹的方法,1電腦自動建立,2人工手動建立*/
   if(way!='2')
      way='1';/*其他數字默認自動建立*/
   if(way=='2')/*手動建立提示輸入結點*/
      printf("Please creat the tree\n");
   root=InitTree(1,320,150);
   system("pause");
   return root;
}
/*生成二叉樹，h表示層次，t表示橫坐標，w表示結點左右子樹的寬度，隨機數n確定結點是空或非空，如n為0，則為空*，但要限定確保結點數不少于三個*/
Tree *InitTree(int h,int t,int w)
{
   char ch;
   int n;/*自動建立時隨機賦值判斷是否是NULL的標志*/
   Tree *node;
   if(way=='2')/*手動建立需要自己輸入*/
      scanf("%c",&ch);
   else/*自動建立的賦值*/
   {
      n=random(5);
      if(n==0&&nodeNUM>=3)/*隨機賦值時候確保自動建立的二叉樹有三個結點*/
  ch='.';
      else
  ch=65+random(25);
   }
 if(ch=='.')/*輸入空格代表NULL*/
      return NULL;
   else
   {
      if(h==6||nodeNUM==26)/*如果樹的層次已經到5或者結點樹到達26個就自動返回NULL*/
  return NULL;
      node=(Tree*)malloc(sizeof(Tree));
      node->data=ch;
      node->x=t;/*樹的x坐標是傳遞過來的橫坐標*/
      node->y=h*50;/*樹的y坐標與層次大小有關*/
      nodeNUM++;
      node->lchild=InitTree(h+1,t-w,w/2);
      node->rchild=InitTree(h+1,t+w,w/2);
   }
   return node;
}
/*用圖形顯示創建好的樹*/
void DrawTree(Tree *t)
{
   if(t!=NULL)
   {
      setcolor(BLACK);
      setfillstyle(SOLID_FILL,BLACK);
      fillellipse(t->x,t->y,9,9);
      setcolor(WHITE);
      circle(t->x,t->y,10); /*畫圓*/
      sprintf(str,"%c",t->data);/*將內容轉換成字符串輸出*/
      outtextxy(t->x-3,t->y-2,str);
      if(t->lchild!=NULL)/*左子樹*/
      {
  line(t->x-5,t->y+12,t->lchild->x+5,t->lchild->y-12);
  DrawTree(t->lchild);
      }
      if(t->rchild!=NULL)/*右子樹*/
      {
  line(t->x+5,t->y+12,t->rchild->x-5,t->rchild->y-12);
  DrawTree(t->rchild);
      }
   }
}
/*遍歷時顯示每個結點的過程*/
void DrawNode(Tree *t,int color)
{
   setcolor(YELLOW);
   setfillstyle(SOLID_FILL,YELLOW);
   fillellipse(t->x,t->y,10,10);
   setcolor(RED);
   sprintf(str,"%c",t->data);/*將內容轉換成字符串輸出*/
   outtextxy(t->x-3,t->y-2,str);
   setcolor(color);
   outtextxy(s.x,s.y,str);
   setcolor(RED);
   sprintf(str,"%d",s.num);/*將遍歷次序用數字顯示在樹的結點上*/
   outtextxy(t->x-3,t->y-20,str);
   s.num++;
   sleep(1);
}
/*前序遍歷*/
void Preorder(Tree *t)
{
   if(t!=NULL)
   {
      s.x+=15;
      DrawNode(t,GREEN);
      Preorder(t->lchild);
      Preorder(t->rchild);
   }
}
/*中序遍歷*/
void Midorder(Tree *t)
{
   if(t!=NULL)
   {
      Midorder(t->lchild);
      s.x+=15;
      DrawNode(t,YELLOW);
      Midorder(t->rchild);
   }
}
/*后序遍歷*/
void Posorder(Tree *t)
{
   if(t!=NULL)
   {
      Posorder(t->lchild);
      Posorder(t->rchild);
      s.x+=15;
      DrawNode(t,BLUE);
   }
}
/*圖形初始化*/
void Init()
{
   int gd=DETECT,gm;
   initgraph(&gd,&gm,"c:\\tc");
   cleardevice();
   setcolor(YELLOW);
   outtextxy(250,10,"anykey to continue");
   setcolor(RED);
   outtextxy(20,300,"preorder");
   outtextxy(20,350,"midorder");
   outtextxy(20,400,"posorder");
   getch();
}
/*圖形關閉*/
void Close()
{
   getch();
   closegraph();
}