USTC机试—//算法求解：根据文件中的先序序列创建一棵树然后中序输出深度小于depth/2的结点,其中零代表叶子结点，depth就是遍历树的深度

//算法求解：根据文件中的先序序列创建一棵树然后中序输出深度小于depth/2的结点,其中零代表叶子结点，depth就是遍历树的深度
#include<stdio.h>
#include<queue>
using namespace std;
#define N 100
struct Node{
  Node *lchild;
  Node *rchild;
  char c;
}E[N];
int loc;
char s[N];
Node *create(){//静态分配一个结点方法
     E[loc].lchild=E[loc].rchild=NULL;
	 return &E[loc++];
}
int i=0;
Node *preCreate(char s[]){//先序建立一颗树
	if(s[i]=='\0'||s[i]=='0')return NULL;//如果到结尾或者是遇到叶子结点返回空
    Node *p=create();
	p->c=s[i++];
	p->lchild=preCreate(s);
    p->rchild=preCreate(s);
	return p;
}
int depth(Node *T){//递归确定树的高度
    if(T==NULL)return 0;
	int left=1;
	int right=1;
    left+=depth(T->lchild);
	right+=depth(T->rchild);
	return left>right?left:right;
}
void depthCreate(Node *p,int depth){//保存新的高度为depth的树
	if(p!=NULL){
		if(depth==0){p->lchild=p->rchild=NULL;}
		else{depthCreate(p->lchild,depth-1);depthCreate(p->rchild,depth-1);}
	}else
		return;
}
FILE *fp1,*fp2;
void inOrder(Node *p){//中序遍历输出一棵树的内容
	if(p->lchild!=NULL)inOrder(p->lchild);
	fprintf(fp2,"%c",p->c);
    if(p->rchild!=NULL)inOrder(p->rchild);
}
int main(){
fp1=fopen("3.in","r");
fp2=fopen("3.out","w");
fscanf(fp1,"%s",s);
Node *p=preCreate(s);
int len=depth(p);
depthCreate(p,len/2);
inOrder(p);
fclose(fp1);
fclose(fp2);//ps为啥我老是忘记这个。。。
return 0;
}