//* * * * * * * * * * * * * * * * * * * * * * * *
//*CHAPTER          :4  (4_1)                   *
//*PROGRAM          :二叉樹                     *
//*CONTENT          :建立，前序、中序、后序遍歷 *
//* * * * * * * * * * * * * * * * * * * * * * * *
#include <dos.h>
#include <conio.h>
#include <stdio.h>
#include <stdlib.h>
enum BOOL{False,True};
typedef struct  BiTNode      //定義二叉樹節點結構
{char  data;                     //數據域
 struct BiTNode *lchild,*rchild; //左右孩子指針域
}BiTNode,*BiTree;
void CreateBiTree(BiTree &);    //生成一個二叉樹
void PreOrder(BiTree);          //先序遞歸遍歷二叉樹
void InOrder(BiTree);           //中序遞歸遍歷二叉樹
void PostOrder(BiTree);         //后序遞歸遍歷二叉樹
void main()
{BiTree T;       
 char ch,j;
 int flag=1;
 BOOL temp;
 textbackground(3);  //設定屏幕顏色
 textcolor(15);
 clrscr();
 //---------------------程序解說-----------------------
 printf("本程序實現二叉樹的操作。\n");
 printf("可以進行建立二叉樹，遞歸先序、中序、后序遍歷等操作。\n");
 //----------------------------------------------------
 printf("請將先序遍歷二叉樹的結果輸入以建立二叉樹。\n");
 printf("對于葉子結點以空格表示。\n");
 printf("例如:abc  de g  f   (回車)，建立如下二叉樹：\n");
 printf("           a      \n");
 printf("          /       \n");
 printf("         b        \n");
 printf("        / \\       \n");
 printf("       c   d      \n");
 printf("          / \\     \n");
 printf("         e   f    \n");
 printf("          \\       \n");
 printf("           g      \n");
 CreateBiTree(T);       //初始化隊列
 getchar();
 while(flag)
    { printf("請選擇: \n");
      printf("1.遞歸先序遍歷\n");
      printf("2.遞歸中序遍歷\n");
      printf("3.遞歸后序遍歷\n");
      printf("4.退出程序\n");
      scanf(" %c",&j);
      switch(j)
	{case '1':if(T)
		     {printf("先序遍歷二叉樹:");
		      PreOrder(T);
		      printf("\n");
		     }
		  else printf("二叉樹為空!\n");
		  break;
	 case '2':if(T)
		    {printf("中序遍歷二叉樹:");
		     InOrder(T);
		     printf("\n");
		    }
		  else printf("二叉樹為空!\n");
		  break;
	 case '3':if(T)
		    {printf("后序遍歷二叉樹:");
		     PostOrder(T);
		     printf("\n");
		    }
		  else printf("二叉樹為空!\n");
		  break;
	 default:flag=0;printf("程序運行結束，按任意鍵退出!\n");
	}
    }
getch();
}

void CreateBiTree(BiTree &T)
{char ch;
 scanf("%c",&ch);    //讀入一個字符   
 if(ch==' ') T=NULL;
 else {T=(BiTNode *)malloc(sizeof(BiTNode)); //生成一個新結點
       T->data=ch;
       CreateBiTree(T->lchild);  //生成左子樹
       CreateBiTree(T->rchild);  //生成右子樹
      }
}
void PreOrder(BiTree T)
{
 if(T)
  {
   printf("%c",T->data);  //訪問結點
   PreOrder(T->lchild);   //遍歷左子樹
   PreOrder(T->rchild);   //遍歷右子樹
  }
}
void InOrder(BiTree T)
{if(T)
  {
   InOrder(T->lchild);   //遍歷左子樹 
   printf("%c",T->data); //訪問結點
   InOrder(T->rchild);   //遍歷右子樹
  }
}
void PostOrder(BiTree T)
{
 if(T)
  {
   PostOrder(T->lchild); //遍歷左子樹
   PostOrder(T->rchild); //訪問結點
   printf("%c",T->data); //遍歷右子樹
  }
}