#include<stdio.h>
#include<stdlib.h>
#define MAXSIZE 20
typedef int ElemType;
typedef struct BNode
{
	ElemType data;
	struct BNode *lch,*rch;
}BNode;
typedef struct
{BNode *a[MAXSIZE];
int top;
}sqstack;
typedef struct
{BNode *elem[MAXSIZE];
int front,rear;
}squeue;
BNode *creat_bt0();
BNode *creat_bt1();
void inorder(BNode *p);
BNode *t;
int z,i,j,k,e;
main()
{do{printf("\n\n");
printf("\n\n           0.建立二叉樹(方法0)    ");
printf("\n\n           1.建立二叉樹(方法1)    ");
printf("\n\n           2.中序遞歸遍歷二叉樹    ");
printf("\n\n           3.結束程序運行");
printf("\n===============================");  
printf("\n      請輸入您的選擇(0,1,2,3):");scanf("%d",&k);
switch(k)
{
case 0:{printf("\n    s輸入(0 0)結束:");
	t=creat_bt0();
	inorder(t);
	   }break;
case 1:{printf("\n按照先序的次序輸入數據,對空孩子也要輸入0");
	t=creat_bt1();
	inorder(t);
	   }break;
case 2:{printf("\n中序遞歸遍歷 inorder:");inorder(t);
	   }break;
case 3:exit(0);
}
printf("\n---------");
}while(k>=0&&k<5);
printf("\n                再見!");scanf("%d",&z);
return 0;
}
BNode *creat_bt0(){
	BNode *t,*p,*v[20];
	printf("\n i data=?");scanf("%d%d",&i,&e);
	while(i!=0&&e!=0)
	{p=(BNode *)malloc(sizeof(BNode));
	p->data=e;p->lch=NULL;p->rch=NULL;
	v[i]=p;
	if(i==1)t=p;
	else {
		j=i/2;
		if(i%2==0)v[j]->lch=p;else v[j]->rch=p;
	}
	printf("\n i data=?");scanf("%d%d",&i,&e);
	}
	return(t);
}
BNode *creat_bt1(){
	BNode *t;
	printf("\n data=");scanf("%d",&e);
	if(e==0)t=NULL;
	else{t=(BNode *)malloc(sizeof(BNode));
	t->data=e;
	t->lch=creat_bt1();
	t->rch=creat_bt1();
	}
	return(t);
}
void inorder(BNode *p)
{if(p){printf("%3d",p->data);
inorder(p->lch);
inorder(p->rch);
}
}