#include <stdio.h>
#include <malloc.h>
#define SIZE 100

int leftdep,rightdep;
typedef struct       BiTNode           //定義二叉樹節點結構
{
char       data;                          //數據域
struct BiTNode *lchild,*rchild; //左右孩子指針域
}BiTNode,*BiTree;


int visit(BiTree t);
void CreateBiTree(BiTree &T);         //生成一個二叉樹
void PreOrder(BiTree);               //遞歸先序遍歷二叉樹
void InOrder(BiTree);                //遞歸中序遍歷二叉樹
void PostOrder(BiTree);              //遞歸后序遍歷二叉樹
void InOrderTraverse(BiTree T); //非遞歸中序遍歷二叉樹
void PreOrder_Nonrecursive(BiTree T);//非遞歸先序遍歷二叉樹
void LeverTraverse(BiTree T);//非遞歸層序遍歷二叉樹



/*
//建立二叉樹  參數法
void TCreateBiTree(BiTree &T)
{
char ch;
scanf("%c",&ch);         //讀入一個字符   
if(ch==' ') {T=NULL;printf("!");}      //注意遞歸的推出機制
else 
{
       T=(BiTNode *)malloc(sizeof(BiTNode)); //生成一個新結點
       T->data=ch;
	   //printf("%c\n",ch);
       TCreateBiTree(T->lchild);       //生成左子樹
	   //printf("%c\n",ch);
       TCreateBiTree(T->rchild);       //生成右子樹
	   //printf("%c\n",ch);
          }
}
*/

//建立二叉樹  非參數法
BiTree CreateBiTree()
{
BiTree t;
char ch;
scanf("%c",&ch);
if(ch==' ')t=NULL;

else {
     t=(BiTNode*)malloc(sizeof(BiTNode));
     t->data=ch;
	 t->lchild=CreateBiTree();
	 t->rchild=CreateBiTree();
	}
return t;
}

//先序遍歷的遞歸
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 printree(BiTree t)
{
	if(t!=NULL)
		{printf("%c",t->data);
		 if(t->lchild!=NULL||t->rchild!=NULL)
			{	printf("(");
				printree(t->lchild);
				if(t->rchild!=NULL)
				printf(",");
				printree(t->rchild);
				printf(")");
			}
		}
}

int treedepth(BiTree t)
{
  if(t==NULL) return 0;
  else
	{
		leftdep=treedepth(t->lchild);
		rightdep=treedepth(t->rchild);
		if(leftdep>rightdep)
		return (leftdep+1);
		else
		return (rightdep+1);
	}
}

/*int TreeLeaf(BiTree T)
{
if(T==NULL) return 0;
else if(T->lchild==NULL&&T->rchild==NULL) return 1;
else return(TreeLeaf(T->lchild)+TreeLeaf(T->rchild));
}
*/
//主函數
void main()
{
BiTree T;       
char j;
int flag=1;
//---------------------程序解說-----------------------
printf("本程序實現二叉樹的操作。\n");
printf("葉子結點以空格表示。\n");
printf("可以進行建立二叉樹，遞歸先序、中序、后序遍歷，非遞歸先序、中序遍歷及非遞歸層序遍歷等操作。\n");
//----------------------------------------------------
printf("\n");
printf("請建立二叉樹。\n");
printf("建樹將以三個空格后回車結束。\n");
printf("例如:1 2 3 4 5 6        (回車)\n");
//CreateBiTree(T);            //初始化隊列
T=CreateBiTree();
printree(T);

int H=treedepth(T);
printf("%d,%d,%d\n",H,leftdep,rightdep);

//int LeafNum=TreeLeaf(T);
//printf("TreeLeafNum=%d",LeafNum);
getchar();
while(flag)
         {
       printf("\n");
       printf("請選擇: \n");
       printf("1.遞歸先序遍歷\n");
       printf("2.遞歸中序遍歷\n");
       printf("3.遞歸后序遍歷\n");
       printf("4.非遞歸中序遍歷\n");
       printf("5.非遞歸先序遍歷\n");
       printf("6.非遞歸層序遍歷\n");
       printf("0.退出程序\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;

        default:flag=0;printf("程序運行結束，按任意鍵退出!\n");
       }
         }
}