首页 > 代码库 > uva 11234(二叉树、线性表)

uva 11234(二叉树、线性表)

2024-07-13 10:53:40   214人阅读

题解：可以根据输入的字符串画一个二叉树出来，然后层次遍历一下就和输出结果顺序一样，所以根据输入把大写字母当做两个小写字母的根节点，将节点即运算结果当做另一个小写字母放进栈里，和另一个字母组建生成新的树放进栈里，直到最后的的根节点也放进了栈里，开始层次遍历，用数组模拟队列进行遍历，注意因为结果的顺序是从右到左，所以注意遍历的方向问题。
#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(二叉树、线性表)


联系
我们