首页 > 代码库 > uva 11234(二叉树、线性表)
uva 11234(二叉树、线性表)
题解:可以根据输入的字符串画一个二叉树出来,然后层次遍历一下就和输出结果顺序一样,所以根据输入把大写字母当做两个小写字母的根节点,将节点即运算结果当做另一个小写字母放进栈里,和另一个字母组建生成新的树放进栈里,直到最后的的根节点也放进了栈里,开始层次遍历,用数组模拟队列进行遍历,注意因为结果的顺序是从右到左,所以注意遍历的方向问题。
#include <cstdio> #include <stack> #include <queue> #include <cstdlib> #include <cstring> using namespace std; const int N = 10005; struct Node { char c; Node* left; Node* right; Node() { left = right = NULL; } }; char ans[N]; stack<Node*> s; void bfs() { int front = 0, rear= 1; int n = 0; Node* q[N]; Node* root = s.top(); q[0] = root; while (front < rear) { Node* u = q[front++]; ans[n++] = u->c; if (u->right != NULL) q[rear++] = u->right; if (u->left != NULL) q[rear++] = u->left; } return; } int main() { int t, n; char a[N]; scanf("%d", &t); while (t--) { scanf("%s", a); n = strlen(a); for (int i = 0; i < n; i++) { if (a[i] <= 'z' && a[i] >= 'a') { Node* u = (Node*) malloc(sizeof(Node)); u->left = u->right = NULL; u->c = a[i]; s.push(u); } else { Node* u = (Node*) malloc(sizeof(Node)); u->left = s.top(); s.pop(); u->right = s.top(); s.pop(); u->c = a[i]; s.push(u); } } bfs(); for (int i = n - 1; i >= 0; i--) printf("%c", ans[i]); printf("\n"); while (!s.empty()) s.pop(); } return 0; }
uva 11234(二叉树、线性表)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。