/*2006.5.2
  熊小輝
  湖南理工學院物電樓506
  本程序功能：直觀的顯示了二樹的三種基本遍歷方法。
 */
#include<stdio.h>
#include<math.h>
#include<graphics.h>
#include<dos.h>
#include<stdlib.h>
#include<time.h>

//利用結構體創建樹結點
typedef struct TREE
    { char data;    //存儲數據
      struct TREE *lchild;    //左孩子
      struct TREE *rchild;    //右孩子
      int x;                  //樹結點的坐標
      int y;
    } tree;
struct output
   { int x;//三種遍歷的坐標
     int y;
     int num; //遍歷時是第幾個結點。
   }s;
char str[5];
int nodenum=0;//統計當前結點的數目


void init(void); //圖形的初始化
void close(void);//關閉圖形
tree *inittree(int h,int t,int w);//建立二叉樹
void showtree(tree *first);     //顯示樹的函數
void posorder(tree *first);     //前序遍歷函數
void midorder(tree *first);     //中序遍歷函數
void preorder(tree *first);     //后序遍歷函數

//=================================================================
//=========主函數====================================================
//==================================================================
void main(void)
     {
       tree *node;
        init();     //圖形初始化
       node=inittree(1,320,150); //創建樹
       showtree(node);      //樹的顯示
       s.x=80;
       s.y=410;          //字母顯示的初始化
       s.num=1;
       preorder(node); //前序遍歷函數
       getch();
       clrscr();    //清屏
       showtree(node); //顯示初始化時的圖形
       s.x=80;
       s.y=430;          //字母顯示的初始化
       s.num=1;
       midorder(node);//中序遍歷
       getch();
       clrscr();      //清屏
       showtree(node); //顯示初始化時的圖形
       s.x=80;
       s.y=450;          //字母顯示的初始化
       s.num=1;
       posorder(node); //后序遍歷

       close();           //關閉圖形
     }
//======顯示遍歷每個結點的過程==============================
void shownode(tree *first,int color)
     {   setcolor(YELLOW);
         setfillstyle(SOLID_FILL,YELLOW);
         fillellipse(first->x,first->y,10,10); //將結點填充黃色
         setcolor(4);
         sprintf(str,"%c",first->data);       //用紅色來填寫字符
         outtextxy(first->x-3,first->y-2,str);
         setcolor(color);
         outtextxy(s.x,s.y,str);    //在字符序列表中加入遍歷的字符
         sprintf(str,"%d",s.num);
         outtextxy(first->x,first->y-10,str); //在結點旁邊加上序列號
         s.num++;
     }
//======前序遍歷函數=========================================
void preorder(tree *first)
     { if(first!=NULL)
          {
               getch(); //實現逐個顯示
              s.x+=15;
              shownode(first,4);       //顯示當前結點

              preorder(first->lchild);  //利用遞歸法查詢左子樹
              preorder(first->rchild);  //利用遞歸查詢右子樹

          }
      }
//======= 中序遍歷函數=============================================
void midorder(tree *first)
    {  if(first!=NULL)
         {
            midorder(first->lchild);   //利用遞歸法查詢左子樹

            getch(); //實現逐個顯示
            s.x+=15;
            shownode(first,6);

            midorder(first->rchild);   //利用遞歸查詢右子樹


        }
    }
//======= 后序遍歷=============================================
void posorder(tree *first)
    { if(first!=NULL)
        {

           posorder(first->lchild); //利用遞歸法查詢左子樹

           posorder(first->rchild);   //利用遞歸查詢右子樹
           s.x+=15;
           getch(); //實現逐個顯示
           shownode(first,4);
        }
    }

//========后序遍歷函數=============================================
/* 生成二叉樹，H 表示層次，T表示橫坐標，W 表示結點左右子樹的寬度，隨機數N確定結點是否為空，
  如果N為0，則為空，但要限定結點數不少于三個*/
tree *inittree(int h,int t,int w)
     {  char ch;
        int n;
        tree *node;
         ch=65+random(25);
         {
            if(h==6||nodenum==40)
              return NULL;
            node=(tree*)malloc(sizeof(tree));
            node->data=ch;
            node->x=t;
            node->y=h*50;
            nodenum++;                          //采用遞歸法建立樹
            node->lchild=inittree(h+1,t-w,w/2);
            node->rchild=inittree(h+1,t+w,w/2);
         }
        return node;
     }
 //========用圖形顯示建立的樹==========================
 void showtree(tree *first)
   {   if(first!=NULL)
         {
             setcolor(WHITE);
             circle(first->x,first->y,10); //畫圓，
             //outtextxy(20,20,"a");  //用于測試符號
             sprintf(str,"%c",first->data);
             outtextxy(first->x-3,first->y-2,str);
             if(first->lchild!=NULL)//左子樹不為0
                {
                     //outtextxy(20,40,"b"); //用于測試符號
                     line(first->x-5,first->y+10,first->lchild->x+5,first->lchild->y-10);
                     showtree(first->lchild);
                }
             if(first->rchild!=NULL)
                {
                   // outtextxy(20,60,"c"); //用于測試符號
                    line(first->x+5,first->y+10,first->rchild->x-5,first->rchild->y-10);
                     showtree(first->rchild);
                }

            }
           // else
            // outtextxy(20,80,"f");  //用于測試符號
        }
//==========關閉圖形函數========================
void close(void)
      { getch();
        closegraph();

      }
//===========圖形初始化函數======================
void init(void)
      { int gdriver=DETECT,gmode;
        registerbgidriver(EGAVGA_driver);
        initgraph(&gdriver,&gmode,"");
        setbkcolor(0);
        cleardevice();
        setcolor(5);
        outtextxy(230,10,"input any key to continue");
        outtextxy(20,410,"preorder:");
        outtextxy(20,430,"midorder:");
        outtextxy(20,450,"posorder:");
        getch();
      }