pta数据结构day9

总结：写了三题，花费半天，准备先把leetbook的二叉树先写一遍，因为pta没有最优解，写起来逻辑并不顺畅。

先看树种统计，比较另外2题简单；

题目详情 - 案例4-1.6 树种统计 (pintia.cn)

#include<iostream>
#include<map>
#include<string>
using namespace std;
 
int main() {
	map<string, int>mp;
	int n;
	cin >> n;
	cin.get();//blank
	string s;
	for (int i = 0; i < n; i++) {
		getline(cin, s);
		map<string, int>::iterator it = mp.find(s);//原来有这个元素，统计个数+1；
		if (it != mp.end()) {
			it->second += 1;
		}
		else {//没有这个元素，创建并初始个数为1
			mp.insert(make_pair(s, 1));
		}
	}
	cout.setf(ios_base::fixed);
	cout.precision(4);
	for (map<string, int>::iterator i = mp.begin(); i != mp.end(); i++) {
		cout << i->first << ' ' << (i->second)*100.0/n<<'%' << endl;
	}
	return 0;
}

第二题是树的同构，考察递归的逻辑，可以参考mooc视频多写几次；

题目详情 - 基础实验4-2.1 树的同构 (pintia.cn) 

#include<iostream>
using namespace std;
#define NULL -1
struct node {
	char data;
	int left, right;
}p[10],q[10];
int input(node p[],int n) {
	int check[10]={0},root=NULL;
	char ch;
	for (int i = 0; i < n; i++) {
		cin.get();//blank
		cin >> p[i].data;
		cin >> ch;
		if (ch == '-') {
			p[i].left = -1;
		}
		else {
			p[i].left = ch - '0';
			check[p[i].left] = 1;
		}
		cin >> ch;
		if (ch == '-') {
			p[i].right = -1;
		}
		else {
			p[i].right = ch - '0';
			check[p[i].right] = 1;
		}
	}
	for (int i = 0; i < n; i++) {
		if (check[i] == 0) {
			root = i;
		}
	}
	return root;
}
bool is_tonggou(int r1,int r2) {
	if (r1 == NULL && r2 == NULL) {
		return 1;
	}
	else if ((r1 == NULL && r2 != NULL) || (r1 != NULL && r2 == NULL)) {
		return 0;
	}
	else if (p[r1].data != q[r2].data) {
		return 0;
	}
	else if ((p[r1].left == NULL) && (q[r2].left == NULL)) {
		return is_tonggou(p[r1].right, q[r2].right);
	}
	else if ((p[r1].left != NULL) && (q[r2].left != NULL)&&(p[p[r1].left].data==q[q[r2].left].data)) {
		return is_tonggou(p[r1].left, q[r2].left) && is_tonggou(p[r1].right, q[r2].right);
	}
	else {
		return is_tonggou(p[r1].left, q[r2].right) && is_tonggou(p[r1].right, q[r2].left);
	}
}
int main() {
	int n,m,root1,root2;
	cin >> n;
	root1=input(p,n);
	cin >> m;
	if (n != m) {
		cout << "No\n";
		return 0;
	}
	root2=input(q,m);
	bool flag = is_tonggou(root1,root2);
	if (flag) {
		cout << "Yes\n";
	}
	else {
		cout << "No\n";
	}
	return 0;
}

最后是目录树，比较复杂，需要再写一次；

题目详情 - 基础实验4-2.6 目录树 (pintia.cn)