pat 1090,树的遍历,层序,先根遍历,利用缓存来优化,“以土地换和平”

2/22/2017来源:ASP.NET技巧人气:1013

树是一种常见的数据结构,二叉树是它的特殊形态,有关树的知识参考《数据结构》的课本。

本文以pat1090为例,给出树的双亲表示法,孩子表示法,给出树的层序遍历,给出树的先根遍历。

并对pat1090部分case的超时给出分析,和相应的解决措施。

一、分析题目

对于题目的输入,显然双亲表示法最为直观,采用vector<int> parents容器来表达这棵树,然后计算出最深的叶子节点,记此深度为maxm,count记录具有该深度的叶子节点的个数。

 double temp = pow((1 + r / 100.0), (double)maxm);  double finalPRice = P*temp;  printf("%.2f %d\n", finalPrice, count);

稍加运算,就可以得到最贵的finalPrice。

其中 P 为原本的价格。

r 为上一级“供销商”到下面的“供销商”后,价格提升的百分率。

二、不分主次的DFS求深度

最naive的做法是对于任意节点,求其树高,找到最深的maxm,并记录其个数,即count。

#include<stdio.h>
#include<vector>
using std::vector;
#include<math.h>

vector<int> parents;
int findRoot(int x, int &deep) {
	return parents[x] == -1 ? x : findRoot(parents[x], ++deep);
}//findRoot

int main() {
	int N(-1);
	double P(0.0), r(0.0);
	scanf("%d%lf%lf", &N, &P, &r);
	parents.assign(N, -1);
	for (int i = 0; i<N; i++)scanf("%d", &parents[i]);
	int maxm(-1), count(-1);
	for (int i(0); i<N; ++i) {
		int deep(0);
		findRoot(i, deep);
		if (deep>maxm) {
			maxm = deep;
			count = 1;
		}
		else if (deep == maxm) count++;
	}//for i
	double temp = pow((1 + r / 100.0), (double)maxm);
	double finalPrice = P*temp;
	printf("%.2f %d\n", finalPrice, count);
	return 0;
}//main很多case都超时了,显而易见。

没必要求所有的结点的deep,也就是for(int i(0);i<N;++i)中的部分结点应该过滤掉。

三、过滤非终端结点

改进如下,定义marks数组来记录非终端结点。

#include<stdio.h>
#include<vector>
using std::vector;
#include<math.h>

vector<int> parents;
int findRoot(int x, int &deep) {
	return parents[x] == -1 ? x : findRoot(parents[x], ++deep);
}//findRoot

int main() {
	int N(-1);
	double P(0.0), r(0.0);
	scanf("%d%lf%lf", &N, &P, &r);
	parents.assign(N, -1);
	vector<bool> marks(N,false);
	for (int i(0); i < N; ++i) {
		scanf("%d", &parents[i]);
		if (parents[i] == -1)continue;
		marks[parents[i]] = true;
	}//for i
	int maxm(-1), count(-1);
	for (int i(0); i<N; ++i) {
		if (marks[i] == true)continue;
		int deep(0);
		findRoot(i, deep);
		if (deep>maxm) {
			maxm = deep;
			count = 1;
		}
		else if (deep == maxm) count++;
	}//for i
	double temp = pow((1 + r / 100.0), (double)maxm);
	double finalPrice = P*temp;
	printf("%.2f %d\n", finalPrice, count);
	return 0;
}//main

但还是有一个超时。

原因是对于不同的叶结点,它们到根的路径上是有重叠的。

而findRoot函数在求解deep的时候,又重走了那些公共的路径,造成耗时。

四、采用dp思想来缓存计算结果

首先想做出如下改进,先利用deeps数组来缓存某些中间结果,使得findRoot省去公共路径的求解。

 

利用了vector<int>deeps来存储树深的信息,有点dp的意思,但是还是有超时。

#include<stdio.h>
#include<vector>
using std::vector;
#include<math.h>

vector<int> parents;
vector<int> deeps;
int findRoot(int x) {
	int deep(0);
	while (deeps[x] == -1) {
		x = parents[x];
		deep++;
	}
	return deeps[x] + deep;
}//findRoot

int main() {
	int N(-1);
	double P(0.0), r(0.0);
	scanf("%d%lf%lf", &N, &P, &r);
	parents.assign(N, -1);
	deeps.assign(N, -1);
	for (int i(0); i<N; ++i) {
		scanf("%d", &parents[i]);
		if (parents[i] == -1)deeps[i] = 0;
	}//for i
	for (int i(0); i<N; ++i) {
		int deep = findRoot(i);
		deeps[i] = deep;
	}//for i
	int maxm(-1), count(-1);
	for (int i(0); i<N; ++i) {
		int deep = deeps[i];
		if (deep>maxm) {
			maxm = deep;
			count = 1;
		}
		else if (deep == maxm) count++;
	}//for i
	double temp = pow((1 + r / 100.0), (double)maxm);
	double finalPrice = P*temp;
	printf("%.2f %d\n", finalPrice, count);
	return 0;
}//main优化失败,如果超时是由于重复访问树的结点造成的,只要保证树的结点只被遍历一次,就可以了。

五、树的层序遍历

树的层序遍历正好满足只遍历一次,而且还能记录树的高度。

树的表示法要改成“孩子法”,vector<vector<node>> nodes(N)来存储。

#include<stdio.h>
#include<vector>
using std::vector;
#include<math.h>
#include<queue>
using std::queue;

struct node {
	int ID;
	int deep;
	node(int ID0 = 0) :ID(ID0) {
		deep = 0;
	}//node
};

void BFS(const int &root, const vector<vector<node> > &nodes, int &maxDeep, int &count) {//node---int
	queue<node> Q_buf;
	Q_buf.push(node(root));
	while (Q_buf.empty() == false) {
		node temp = Q_buf.front();
		Q_buf.pop();
		if (nodes[temp.ID].size() == 0) {
			if (maxDeep == -1 || temp.deep > maxDeep) {
				maxDeep = temp.deep;
				count = 1;
			}
			else if (temp.deep == maxDeep) count++;
			continue;
		}//if
		int size = (int)nodes[temp.ID].size();
		for (int i(0); i < size; ++i) {
			node chd = nodes[temp.ID][i];
			chd.deep = temp.deep + 1;//chd.deep++;wrong
			Q_buf.push(chd);
		}//for i
	}//while
	return;
}//BFS

int main() {
	int N(-1);
	double P(0.0), r(0.0);
	scanf("%d%lf%lf", &N, &P, &r);
	vector<vector<node>> nodes(N);
	int root(-1);
	for (int i(0); i<N; ++i) {
		int temp(-1);
		scanf("%d", &temp);
		if (temp == -1) {
			root = i;
			continue;
		}//if
		nodes[temp].push_back(node(i));
	}//for i
	int count(1), maxDeep(-1);
	BFS(root, nodes, maxDeep, count);
	//printf("%d %d\n",maxDeep,count);
	printf("%.2f %d\n", P*pow((1 + r / 100.0), (double)maxDeep), count);
	return 0;
}

完美通过所有case。

六、树的先根遍历

既然采用“孩子法”来表示树 ,也可以先根遍历,同样是只访问树中结点一次,并且记录下所有结点的深度。

树的层序遍历,核心部分代码是BFS的,那么树的先根遍历,核心部分代码就是DFS的,此处的DFS并不需要写递归。

而是采用一种比较简单的做法,将BFS中的queue换成stack,就完成了核心代码的编写。

(灵感来源于二叉树的先序遍历的递归和非递归实现)

将BFS里面的queue改成stack就是先根遍历了,可以调节一下每个结点的子树遍历次序,就是for(int i(0);i<size;++i)可以改为for(int i(size-1);i>=0;--i)。


void DFS(const int &root, const vector<vector<node> > &nodes, int &maxDeep, int &count) {//node---int
	stack<node> Q_buf;
	Q_buf.push(node(root));
	while (Q_buf.empty() == false) {
		node temp = Q_buf.top();
		Q_buf.pop();
		if (nodes[temp.ID].size() == 0) {
			if (maxDeep == -1 || temp.deep > maxDeep) {
				maxDeep = temp.deep;
				count = 1;
			}
			else if (temp.deep == maxDeep) count++;
			continue;
		}//if
		int size = (int)nodes[temp.ID].size();
		for (int i(0); i < size; ++i) {
			node chd = nodes[temp.ID][i];
			chd.deep = temp.deep + 1;//chd.deep++;wrong
			Q_buf.push(chd);
		}//for i
	}//while
	return;
}//DFS

二叉树遍历的递归和非递归实现,见。。。