题目描述
编一个程序，读入用户输入的一串先序遍历字符串，根据此字符串建立一个二叉树（以指针方式存储）。
例如如下的先序遍历字符串：
ABC##DE#G##F###
其中“#”表示的是空格，空格字符代表空树。建立起此二叉树以后，再对二叉树进行中序遍历，输出遍历结果。
输入
输入包括1行字符串，长度不超过100。
输出
可能有多组测试数据，对于每组数据，
输出将输入字符串建立二叉树后中序遍历的序列，每个字符后面都有一个空格。
每个输出结果占一行。
样例输入
a#b#cdef#####
a##
样例输出
a b f e d c
a 分析：给出的序列是前序遍历序列，可以用栈来保存节点，模拟前序遍历。注意退栈时，如果当前栈顶元素的右孩子已经填充过（不管是‘#’还是字母），就要继续退栈。
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <string>
#include <vector>
#include <cstdio>
#include <queue>
#include <stack>
#include <ctime>
#include <cmath>
#include <map>
#include <set>
#include<unordered_map>
#define INF 0x3f3f3f3f
#define db1(x) cout<<#x<<"="<<(x)<<endl
#define db2(x,y) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<endl
#define db3(x,y,z) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<endl
#define db4(x,y,z,a) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<endl
#define db5(x,y,z,a,r) cout<<#x<<"="<<(x)<<", "<<#y<<"="<<(y)<<", "<<#z<<"="<<(z)<<", "<<#a<<"="<<(a)<<", "<<#r<<"="<<(r)<<endl
using namespace std;typedef struct node
{char val;struct node *left,*right;int flag_l,flag_r,flag;//三个标志分别标志左孩子、右孩子、自己是否已经填充
}node;void Free(node *root)
{if(root->left!=NULL)Free(root->left);if(root->right!=NULL)Free(root->right);free(root);return;
}void mid_order(node *root)
{if(root==NULL)return;mid_order(root->left);printf("%c ",root->val);mid_order(root->right);return;
}int main(void)
{#ifdef testfreopen("in.txt","r",stdin);//freopen("out.txt","w",stdout);clock_t start=clock();#endif //testchar pre[1100];while(~scanf("%s",pre)){stack<node*>sta;node *root=(node*)malloc(sizeof(node));root->flag_l=root->flag_r=root->flag=0;root->left=root->right=NULL;sta.push(root);int len=strlen(pre);for(int i=0;i<len;++i){node *temp=sta.top();if(pre[i]!='#')//不为空{if(temp->flag==0)temp->val=pre[i],temp->flag=1;//自己还没填，先填自己else if(temp->flag_l==0)//自己填了，填左子树{node *p=(node*)malloc(sizeof(node));p->val=pre[i];p->flag_l=p->flag_r=0,p->flag=1;p->left=p->right=NULL;temp->flag_l=1,temp->left=p;sta.push(p);//把左孩子进栈，接下来填左子树}else if(temp->flag_r==0)//自己、左孩子都填了，填右子树{node *p=(node*)malloc(sizeof(node));p->val=pre[i];p->flag_l=p->flag_r=0,p->flag=1;p->left=p->right=NULL;temp->flag_r=1,temp->right=p;sta.push(p);//把右孩子进栈，接下来填右子树}}else//为空。自己肯定不为空，因为空节点不会进栈{if(temp->flag_l==0)temp->flag_l=1;//左子树先为空else if(temp->flag_r==0)//左子树已经有了，右子树为空{temp->flag_r=1;//出栈要一直出到右子树还没填的节点while(!sta.empty()&&sta.top()->flag_r==1)sta.pop();}}}mid_order(root);printf("\n");Free(root);}#ifdef testclockid_t end=clock();double endtime=(double)(end-start)/CLOCKS_PER_SEC;printf("\n\n\n\n\n");cout<<"Total time:"<<endtime<<"s"<<endl; //s为单位cout<<"Total time:"<<endtime*1000<<"ms"<<endl; //ms为单位#endif //testreturn 0;
}
