- 总时间限制: 1000ms 内存限制: 65536kB
- 描述
一棵树的镜面映射指的是对于树中的每个结点，都将其子结点反序。例如，对左边的树，镜面映射后变成右边这棵树
。
a a / | / | b c f ===> f c b / / d e e d
我们在输入输出一棵树的时候，常常会把树转换成对应的二叉树，而且对该二叉树中只有单个子结点的分支结点补充一个虚子结点“$”，形成“伪满二叉树”。
例如，对下图左边的树，得到下图右边的伪满二叉树
a a / | / b c f ===> b $ / / d e $ c / d f / $ e
然后对这棵二叉树进行前序遍历，如果是内部结点则标记为0，如果是叶结点则标记为1，而且虚结点也输出。
现在我们将一棵树以“伪满二叉树”的形式输入，要求输出这棵树的镜面映射的宽度优先遍历序列。
输入
输入包含一棵树所形成的“伪满二叉树”的前序遍历。
第一行包含一个整数，表示结点的数目。
第二行包含所有结点。每个结点用两个字符表示，第一个字符表示结点的编号，第二个字符表示该结点为内部结点还是外部结点，内部结点为0，外部结点为1。结点之间用一个空格隔开。
数据保证所有结点的编号都为一个小写字母。输出输出包含这棵树的镜面映射的宽度优先遍历序列，只需要输出每个结点的编号，编号之间用一个空格隔开。
样例输入
9 a0 b0 $1 c0 d0 $1 e1 f1 $1
样例输出
a f c b e d
#include <cstdio> #include <stack> #include <queue> using namespace std; struct node{ char x; node *lchild; node *rchild; }tree[1002]; int loc,n; char temp[3]; node* create(){ //生成一个新的结点，并将其孩子结点置为NULL tree[loc].lchild = NULL; tree[loc].rchild = NULL; return &tree[loc++]; } node *build(){ //该题输入为伪满二叉树的前序遍历，利用0、1标志来识别外结点和内结点 scanf("%s",temp); node *p = create(); p->x = temp[0]; if(temp[1] == '0' && p->x != '$'){ //if(loc != n) //因为已经给出01标志了，并且是伪满二叉树，所以这道题目的n(树的结点个数)信息冗余。 p->lchild = build(); //if(loc != n) p->rchild = build(); } return p; } void Print(node *p){ //输出该树的镜像翻转 stack<node *> s; queue<node *>Q; while(p != NULL){ //此处是关键，根据“左孩子右兄弟”的特点，一直向右遍历，将树同一层的结点都放在栈内 //printf("push:%c.",p->x); if(p->x != '$') s.push(p); p = p->rchild; } while(!s.empty()){ //将栈内的结点依次弹出，压入队列，完成镜像翻转的功能 Q.push(s.top()); s.pop(); } while(!Q.empty()){ p = Q.front(); Q.pop(); printf("%c ",p->x); if(p->lchild != NULL){ p = p->lchild; while(p != NULL){ //同理，上面是处理根节点的，因为那时队列还为空，这里是处理剩下的全部结点 //printf("push:%c ",p->x); if(p->x != '$') s.push(p); p = p->rchild; } while(!s.empty()){ Q.push(s.top()); s.pop(); } } } return; } void BFS(node *p){ //测试用的，实际上没调用 queue<node *> Q; Q.push(p); while(!Q.empty()){ p = Q.front(); Q.pop(); printf("%c ",p->x); if(p->lchild != NULL) Q.push(p->lchild); if(p->rchild != NULL) Q.push(p->rchild); } } int main(){ loc = 0; scanf("%d",&n); node *root; root = build(); Print(root); return 0; }