Description
已知二叉树的一个按先序遍历输入的字符序列,如abc,de,g,f, (其中,表示空结点)。请建立二叉树并按中序和后序的方式遍历该二叉树。
Input
连续输入多组数据,每组数据输入一个长度小于50个字符的字符串。
Output
每组输入数据对应输出2行:
第1行输出中序遍历序列;
第2行输出后序遍历序列。
Sample
Input
abc,de,g,f,
Output
cbegdfa
cgefdba
Hint
#include<bits/stdc++.h>using namespace std;typedef struct node{char data;struct node *l, *r;} Tree;char a[55];int cnt;Tree *creat(){Tree *root;if(a[cnt] == ','){cnt++;root = NULL;}else{root = new Tree;root->data = a[cnt++];root->l = creat();root->r = creat();}return root;}void mid(Tree *root){if(root){mid(root->l);printf("%c", root->data);mid(root->r);}}void pos(Tree *root){if(root){pos(root->l);pos(root->r);printf("%c", root->data);}}int main(){while(~scanf("%s", a)){cnt = 0;Tree *root = creat();mid(root);printf("\n");pos(root);printf("\n");}}