uva 11234 Expressions 表达式 建树+BFS层次遍历

题目给出一个后缀表达式,让你求从下往上的层次遍历。

思路:结构体建树,然后用数组进行BFS进行层次遍历,最后把数组倒着输出就行了。

uva过了,poj老是超时,郁闷。

代码:

#include <cstdio>
#include <cstring>
#include <cstdlib> const int maxn = 10001;
char str[maxn];
int p; struct Node {
char data;
Node* l;
Node* r;
}; Node* build() {
Node* u = (Node*) malloc (sizeof(Node*));
u -> data = str[p];
p--;
if (str[p] >= 'A' && str[p] <= 'Z')
u -> l = build();
else
u -> l -> data = str[p];
p--;
if (str[p] >= 'A' && str[p] <= 'Z')
u -> r = build();
else
u -> r -> data = str[p];
return u;
} int main() {
int t;
while (scanf("%d", &t) != EOF) {
scanf("%s", str);
p = strlen(str) - 1;
Node* root = build();
int rear = 0, front = 0;
Node* q[maxn];
q[rear++] = root;
while (rear > front) {
if (q[front]) {
if (q[front] -> r)
q[rear++] = q[front] -> r;
if (q[front] -> l)
q[rear++] = q[front] -> l;
front++;
}
else
front++;
}
for (int i = rear - 1; i >= 0; i--)
printf("%c", q[i]->data);
printf("\n");
}//while
}
上一篇:Android自定义组件系列【8】——遮罩文字动画


下一篇:UVA 548(二叉树重建与遍历)