Description
已知二叉树的一个按前序遍历输入的字符序列，如abc,de,g,f, (其中,表示空结点)。请建立二叉树，并输出建立二叉树的前序遍历序列、中序遍历序列、后序遍历序列、层次遍历序列、深度、叶子数。
Input
多组测试数据，对于每组测试数据，输入一个长度小于５０的按前序遍历输入的字符序列。
Output
对于每组测试数据，第1行输出其前序遍历序列、第2行输出其中序遍历序列、第3行输出其后序遍历序列、第4行输出其层次遍历序列、第5行输出其深度、第6行输出其叶子数。
Sample
Input
abc,de,g,f,
Output
abcdegf
cbegdfa
cgefdba
abcdefg
5
3
#include<bits/stdc++.h>using namespace std;typedef struct node{char data;struct node *l, *r;} Tree;char pre[55];int cnt, leaves;Tree *creat(){Tree *root;if(pre[cnt] == ','){cnt++;root = NULL;}else{root = new Tree;root->data = pre[cnt++];root->l = creat();root->r = creat();}return root;}void preoreder(Tree *root){if(root){printf("%c", root->data);preoreder(root->l);preoreder(root->r);}}void midoreder(Tree *root){if(root){midoreder(root->l);printf("%c", root->data);midoreder(root->r);}}void posoreder(Tree *root){if(root){posoreder(root->l);posoreder(root->r);printf("%c", root->data);}}void cengxu(Tree *root)//模拟队列{Tree * que[1000];int i = 0, j = 0;que[i++] = root;while(i > j){if(que[j]){que[i++] = que[j]->l;que[i++] = que[j]->r;printf("%c", que[j]->data);if(que[j]->l == NULL && que[j]->r == NULL)leaves++;}j++;}}/*void cengxu(Tree *root)//STL{Tree *temp;queue<Tree *>q;q.push(root);while(!q.empty()){temp = q.front();q.pop();if(temp){if(!temp->l && !temp->r)leaves++;printf("%c", temp->data);if(temp->l)q.push(temp->l);if(temp->r)q.push(temp->r);}}}*/int depth_bintree(Tree *root){int de = 0;if(root){int left_depth = depth_bintree(root->l);int right_depth = depth_bintree(root->r);de = left_depth > right_depth ? left_depth + 1 : right_depth + 1;}return de;}int main(){while(~scanf("%s", pre)){cnt = 0;leaves = 0;Tree *root = creat();preoreder(root);printf("\n");midoreder(root);printf("\n");posoreder(root);printf("\n");cengxu(root);printf("\n");printf("%d\n", depth_bintree(root));printf("%d\n", leaves);}return 0;}
