#include<stdio.h>
#include<stdlib.h>
#define OVERRFLOW 0
#define OK 1
#define ERROR 0
#define MAXSIZE 100

typedef struct BiNode{
   char data;
   struct BiNode *lchild,*rchild;
}BiNode,*BiTree;

typedef struct SqQueue{ //循環(huán)隊(duì)列結(jié)點(diǎn)
    BiTree *base;
	int front;
	int rear;
	int queuesize;
}SqQueue,*SqQueueptr;

typedef enum{Visit,Travel}TaskType;

typedef struct{
 BiTree ptr;
 TaskType task;
}ElemType;

typedef struct stack{
  ElemType *base;
  ElemType *top;
  int stacksize;
}Stack;

InitStack(Stack &S){
S.base=new ElemType[100];
if(!S.base) return ERROR;
S.top=S.base;
S.stacksize=MAXSIZE;
return OK;
}

StackEmpty(Stack S){
if(S.base==S.top)return OK;
else return ERROR;

}
Push(Stack &S,ElemType e){
//插入新的元素e使之成為新的棧頂元素
if(S.top>S.base+S.stacksize) return ERROR;
*S.top++=e;  
return OK; 
}

Pop(Stack &S,ElemType &e){
 if(S.top==S.base)return ERROR;
 e=*(--S.top);
 return OK;
}

InitQueue(SqQueue &Q){   //初始化循環(huán)鏈表
Q.base=new BiTree[MAXSIZE];
if(!Q.base)exit(0);
Q.queuesize=MAXSIZE;
Q.front=Q.rear=0;
return OK;
}

IsEmpty(SqQueue Q){    
if(Q.rear==Q.front)return OK;
else return ERROR;
}

EnQueue(SqQueue &Q,BiTree e){           //新元素入隊(duì)列
//插入元素e為Q的新的隊(duì)尾元素
	if((Q.rear+1)%Q.queuesize==Q.front)return ERROR;
	Q.base[Q.rear]=e;
	Q.rear=(Q.rear+1)%Q.queuesize;
	return OK;
}

DeQueue(SqQueue &Q,BiTree &e){      //出隊(duì)列
if(Q.front==Q.rear)return ERROR;
e=Q.base[Q.front];
Q.front=(Q.front+1)%Q.queuesize;
return OK;
}

CreateBiTree(BiTree &T){            //創(chuàng)建二叉樹(shù)
	char ch;
	scanf("%c",&ch);
	if(ch==' ')T=NULL;
	else{
	if(!(T=(BiNode *)malloc(sizeof(BiNode)))) exit(0);
	T->data=ch;
	CreateBiTree(T->lchild);
	CreateBiTree(T->rchild);	
	}
  return OK;
}

PrintElement(BiTree T){
 printf("%c",T->data);
 return OK;
}

PreOderTrverse(BiTree T){       //遞歸前序輸出
  
	if(T){
	  if(PrintElement(T))
	  if(PreOderTrverse(T->lchild))
	  if(PreOderTrverse(T->rchild)) return OK;
	  return ERROR;
	}
   else return OK;
}
BackOderTrverse(BiTree T){          //遞歸后序輸出
  
	if(T){
	  if(BackOderTrverse(T->lchild))
	  if(BackOderTrverse(T->rchild)) 
	  if(PrintElement(T))return OK;
	  return ERROR;
	}
   else return OK;

}

InOderTrverse(BiTree T){           //遞歸中序輸出
  
	if(T){

	  if(InOderTrverse(T->lchild))
	  if(PrintElement(T))
	  if(InOderTrverse(T->rchild)) return OK;
	  return ERROR;
	}
   else return OK;

}
PreOderTraverse1(BiTree T){
Stack S;ElemType e;BiTree p;
InitStack(S);
e.ptr=T;e.task=Travel;
if(T)Push(S,e);
while(!StackEmpty(S)){
Pop(S,e);
if(e.task==Visit)PrintElement(e.ptr);
else if(e.ptr){
p=e.ptr;e.ptr=p->rchild;e.task=Travel;
Push(S,e);
e.ptr=p->lchild;
Push(S,e);
e.ptr=p;e.task=Visit;
Push(S,e);
}
}
return OK;
}

InOderTraverse1(BiTree T){      
Stack S; ElemType e;BiTree p;
InitStack(S);
e.ptr=T;e.task=Travel;
if(T)Push(S,e);
while(!StackEmpty(S)){
	Pop(S,e);
	if(e.task==Visit)PrintElement(e.ptr);
    else if(e.ptr){
	p=e.ptr;e.ptr=p->rchild;e.task=Travel;
    Push(S,e);
    e.ptr=p;e.task=Visit;
	Push(S,e);
    p=e.ptr;e.ptr=p->lchild;e.task=Travel;
	Push(S,e);
	}
}
return OK;
}

BackTraverse1(BiTree T){
Stack S; ElemType e;BiTree p;
InitStack(S);
e.ptr=T;e.task=Travel;
if(T)Push(S,e);
while(!StackEmpty(S)){
Pop(S,e);  
if (e.task==Visit) PrintElement(e.ptr);
else if(e.ptr){
 //p=e.ptr; 
 e.task=Visit;  
 Push(S,e); 
 p=e.ptr; e.task=Travel; e.ptr=p->rchild;  
 Push(S,e); // 遍歷右子樹(shù)
 e.ptr=p->lchild; 
 Push(S,e); // 遍歷左子樹(shù)
}
}
return  OK;
}

LayerTraverse(BiTree T){       //層次輸出
SqQueue Q;BiTree p;//p=T;
InitQueue(Q);
if(T)EnQueue(Q,T);
while(!IsEmpty(Q)){
	DeQueue(Q,p);PrintElement(p);
    if(p->lchild)EnQueue(Q,p->lchild);
	if(p->rchild)EnQueue(Q,p->rchild);
}
return  OK;
}

BiTreeDepth(BiTree T,int &depth){       //求二叉樹(shù)的深度
int Ldepth=0,Rdepth=0;
if(!T)depth=0;
else {
  BiTreeDepth(T->lchild,Ldepth);
  BiTreeDepth(T->rchild,Rdepth);
  depth=1+(Ldepth>Rdepth?Ldepth:Rdepth);
}
return OK;
}


CountFleaves(BiTree T,int &count){      //求葉子結(jié)點(diǎn)的數(shù)目
if(T){
	if(T->lchild==NULL&&T->rchild==NULL)
	  count++;
	  CountFleaves(T->lchild,count);
      CountFleaves(T->rchild,count);
	}
   return OK;
}

CountNodes(BiTree T,int &count2){   //總結(jié)點(diǎn)的數(shù)目

	if(T) {
	 count2++;
	 CountNodes(T->lchild,count2);
	 CountNodes(T->rchild,count2);
	  
	}
 
   return OK;

}

main(){           //主函數(shù)
int i;
BiTree T;
int count,count2,depth;
while(1){
count=0,count2=0;depth=0;
printf("\n\n創(chuàng)建二叉樹(shù)-------------------------1\n");
printf("遞歸方法輸出(前、中、后序)---------2\n");
printf("非遞歸方法輸出(前、中、后序)-------3\n");
printf("二叉樹(shù)的深度-----------------------4\n");
printf("層次輸出---------------------------5\n");
printf("葉子接點(diǎn)數(shù)-------------------------6\n");
printf("接點(diǎn)總數(shù)---------------------------7\n");
printf("退出-------------------------------0\n");
scanf("%d",&i);
switch(i){
case 0: exit(0);break;
case 1: printf("\n輸入二叉樹(shù)的項(xiàng):\n");getchar();CreateBiTree(T); break;
case 2:	printf("遞歸方法實(shí)現(xiàn)遍歷:\n前序輸出:\n");PreOderTrverse(T);
	    printf("\n中序輸出:\n");InOderTrverse(T);
		printf("\n后序輸出:\n");BackOderTrverse(T);break;
case 3: printf("非遞歸方法實(shí)現(xiàn)遍歷:\n前序輸出:\n");PreOderTraverse1(T);
	    printf("\n中序輸出:\n");InOderTraverse1(T);
	    printf("\n后序輸出:\n");BackTraverse1(T);break;
case 4: BiTreeDepth(T,depth);printf("二叉樹(shù)的深度為:%d\n",depth);break;
case 5: printf("層次輸出:\n");LayerTraverse(T);break;
case 6: CountFleaves(T,count);printf("葉子接點(diǎn)數(shù)為:%d\n",count);break;
case 7: CountNodes(T,count2); printf("接點(diǎn)總數(shù)為:%d\n",count2);break;
default: break;
}
}
return OK;
}