PAT甲级专题-树的遍历

甲级PTA 1004

输出每一层的结点，邻接表vector建树后、用dfs、bfs都可以边搜边存当前层的数据，

#include<bits/stdc++.h>

using namespace std;

const int maxn = 110;

int n, m;

vector<int> g[maxn];

int ans[maxn];

int deep = 0;

void dfs(int x, int depth) {

	if (g[x].size() == 0) {

		if (depth > deep) deep = depth;

		ans[depth]++;

		return;

	}

	for (int i = 0; i < g[x].size(); i++) {

		dfs(g[x][i], depth + 1);

	}

}

int main() {

	cin >> n >> m;

	for (int i = 1; i <= m; i++) {

		int id,k;

		cin >> id;

		cin >> k;

		for (int j = 1; j <= k; j++) {

			int id2;

			cin >> id2;

			g[id].push_back(id2);

		}

	}

	dfs(1, 0);

	for (int i = 0; i <= deep; i++) {

		if (i != deep) cout << ans[i] << " ";

		else cout << ans[i];

	}

	return 0;

}

甲级PTA 1020

中序、后序序列，找出层次遍历的序列

前置知识，中序后序序列来建树、中序后序序列找出前序序列

//中序 后序  找 前序

/*

void build(int root, int start, int end) {

	if (start > end) return;

	if (root < 1) return;

	int pos = start;

	while (pos < end && iorder[pos] != porder[root]) pos++;

	pre[++idx] = porder[root];

	//cout << porder[root] << endl;

	build(root - (end - pos + 1), start, pos - 1);

	build(root - 1, pos + 1, end);

}

*/

本题代码

#include<bits/stdc++.h>

using namespace std;

const int maxn = 50;

int n;

int porder[maxn];

int iorder[maxn];

int a[maxn];

int idx = 0;

int deep = 0;

vector<int> v[maxn];

int ans[maxn];

//后序 中序 在递归时 使用vector存下当前一层的数，因为按左子树优先递归，所以存的序列符合题意

void build(int root, int start, int end, int depth) {

	if (start > end) return;

	int pos = start;

	while (pos < end && iorder[pos] != porder[root]) pos++;

	v[depth].push_back(porder[root]);

	if (depth > deep) deep = depth;

	//cout << "depth = " << depth << " " << porder[root] << endl;

	build(root - (end - pos + 1), start, pos - 1, depth + 1);

	build(root - 1, pos + 1, end, depth + 1);

}

int main() {

	cin >> n;

	for (int i = 1; i <= n; i++) cin >> porder[i];

	for (int i = 1; i <= n; i++) cin >> iorder[i];

	//build(n, 1, n, 1, n);

	//build(n, 1, n);

	build(n, 1, n, 1);

	int num = 1;

	for (int i = 1; i <= deep; i++) {

		for (int j = 0; j < v[i].size(); j++) {

			ans[num++] = v[i][j];

		}

	}

	for (int i = 1; i <= n; i++) {

		if (i == n) cout << ans[i];

		else cout << ans[i] << " ";

	}

	return 0;

}

甲级PTA 1053

找出路径长度等于 S 的路径，按结点权值的字典序排列

vector按权值大的优先存树的边、dfs搜索边搜边存答案。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1010;

vector<int> g[maxn];

int w[maxn];

int n, m;

ll s;

int path[maxn];

vector<int> ans[maxn];

int len = 0;

struct node {

	int v;

};

void dfs(int x, int depth) {

	path[depth] = w[x];

	if (g[x].size() == 0) {

		ll temp = 0;

		for (int i = 0; i <= depth; i++) temp += path[i];

		if (temp == s) {

			for (int i = 0; i <= depth; i++) ans[len].push_back(path[i]);

			len++;

		}

		return;

	}

	for (int i = 0; i < g[x].size(); i++) {

		dfs(g[x][i], depth + 1);

	}

}

bool cmp(int a,int b) {

	return w[a] > w[b];

}

node temp[1010];

int main() {

	cin >> n >> m >> s;

	for (int i = 0; i < n; i++) cin >> w[i];

	for (int i = 1; i <= m; i++) {

		int id1, k, id2;

		cin >> id1 >> k;

		for (int j = 1; j <= k; j++) {

			cin >> id2;

			g[id1].push_back(id2);

		}

	}

	for (int i = 0; i < n; i++) sort(g[i].begin(), g[i].end(), cmp);

	dfs(0, 0);

	for (int i = 0; i < len; i++) {

		for (int j = 0; j < ans[i].size(); j++) {

			if (j == ans[i].size() - 1) cout << ans[i][j] << endl;

			else cout << ans[i][j] << " ";

		}

	}

	return 0;

}

甲级PTA 1079

算出，从各个叶节点 到 根的距深度（dfs），按题意计算答案。

#include<bits/stdc++.h>

using namespace std;

const int maxn = 1e5+10;

int n;

double r, p,ans = 0;

vector<int> g[maxn];

double dat[maxn];

void dfs(int x, int depth) {

	if (g[x].size() == 0) {

		ans += (dat[x] * pow(1 + r, depth));

		return;

	}

	for (int i = 0; i < g[x].size(); i++) {

		dfs(g[x][i], depth + 1);

	}

}

int main() {

	cin >> n >> p >> r;

	r = r * 0.01;

	for (int i = 0; i < n; i++) {

		int k;

		cin >> k;

		int id;

		double val;

		if (k == 0) {

			cin >> val;

			dat[i] = val;

			continue;

		}

		for (int j = 0; j < k; j++) {

			cin >> id;

			g[i].push_back(id);

		}

	}

	dfs(0, 0);

	printf("%.1f", ans * p);

	return 0;

}

甲级PTA 1086

先序、中序序列，找出后序序列

我的做法：先根据先序中序序列建树、再后序遍历找出后序序列。

先序确定根，中序划分左右子树

但是这题题目没说完善，万一有重复元素，应该就建不了树了

#include<bits/stdc++.h>

using namespace std;

const int maxn = 50;

int n;

struct node {

	int v;

	node * l, * r;

};

int pre[maxn];

int in[maxn];

int post[maxn];

int idx1 = 0, idx2 = 0,idx = 0;

stack<int> st;

node * build(int root,int il,int ir) {

	if (il > ir) return NULL;

	int pos = il;

	while (pos <= ir && in[pos] != pre[root]) pos++;

	node* Root = new node;

	Root->v = pre[root];

	Root->l = build(root+1, il, pos - 1);

	Root->r = build(root+(pos-il)+1 ,pos+1,ir);

	return Root;

}

void postOrder(node *Root) {

	if (Root == NULL) return;

	if (Root->l) postOrder(Root->l);

	if (Root->r) postOrder(Root->r);

	post[++idx] = Root->v;

}

int main() {

	cin >> n;

	while (1) {

		string ins;

		int id;

		cin >> ins;

		if (ins == "Push") {

			cin >> id;

			pre[++idx1] = id;

			st.push(id);

		}else {

			int top = st.top();

			in[++idx2] = top;

			st.pop();

		}

		if (idx1 == n && idx2 == n) break;

	}

	node* Root = new node;

	Root = build(1, 1, n);

	postOrder(Root);

	for (int i = 1; i <= n; i++) {

		if (i == n) cout << post[i];

		else cout << post[i] << " ";

	}

	return 0;

}