pat 1090，樹的遍歷，層序，先根遍歷，利用緩存來優(yōu)化，“以土地?fù)Q和平”

2019-11-08 02:13:01

字體：大中小

供稿：網(wǎng)友

樹是一種常見的數(shù)據(jù)結(jié)構(gòu)，二叉樹是它的特殊形態(tài)，有關(guān)樹的知識(shí)參考《數(shù)據(jù)結(jié)構(gòu)》的課本。

本文以pat1090為例，給出樹的雙親表示法，孩子表示法，給出樹的層序遍歷，給出樹的先根遍歷。

并對(duì)pat1090部分case的超時(shí)給出分析，和相應(yīng)的解決措施。

一、分析題目

對(duì)于題目的輸入，顯然雙親表示法最為直觀，采用vector<int> parents容器來表達(dá)這棵樹，然后計(jì)算出最深的葉子節(jié)點(diǎn)，記此深度為maxm，count記錄具有該深度的葉子節(jié)點(diǎn)的個(gè)數(shù)。

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

稍加運(yùn)算，就可以得到最貴的finalPrice。

其中 P 為原本的價(jià)格。

r 為上一級(jí)“供銷商”到下面的“供銷商”后，價(jià)格提升的百分率。

二、不分主次的DFS求深度

最naive的做法是對(duì)于任意節(jié)點(diǎn)，求其樹高，找到最深的maxm，并記錄其個(gè)數(shù)，即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);}//findRootint 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都超時(shí)了，顯而易見。
沒必要求所有的結(jié)點(diǎn)的deep，也就是for(int i(0);i<N;++i)中的部分結(jié)點(diǎn)應(yīng)該過濾掉。
三、過濾非終端結(jié)點(diǎn)
改進(jìn)如下，定義marks數(shù)組來記錄非終端結(jié)點(diǎn)。
#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);}//findRootint 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但還是有一個(gè)超時(shí)。
原因是對(duì)于不同的葉結(jié)點(diǎn)，它們到根的路徑上是有重疊的。
而findRoot函數(shù)在求解deep的時(shí)候，又重走了那些公共的路徑，造成耗時(shí)。
四、采用dp思想來緩存計(jì)算結(jié)果
首先想做出如下改進(jìn)，先利用deeps數(shù)組來緩存某些中間結(jié)果，使得findRoot省去公共路徑的求解。
 
利用了vector<int>deeps來存儲(chǔ)樹深的信息，有點(diǎn)dp的意思，但是還是有超時(shí)。#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;}//findRootint 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優(yōu)化失敗，如果超時(shí)是由于重復(fù)訪問樹的結(jié)點(diǎn)造成的，只要保證樹的結(jié)點(diǎn)只被遍歷一次，就可以了。
五、樹的層序遍歷
樹的層序遍歷正好滿足只遍歷一次，而且還能記錄樹的高度。
樹的表示法要改成“孩子法”，vector<vector<node>> nodes(N)來存儲(chǔ)。
#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;}//BFSint 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。
六、樹的先根遍歷
既然采用“孩子法”來表示樹 ，也可以先根遍歷，同樣是只訪問樹中結(jié)點(diǎn)一次，并且記錄下所有結(jié)點(diǎn)的深度。
樹的層序遍歷，核心部分代碼是BFS的，那么樹的先根遍歷，核心部分代碼就是DFS的，此處的DFS并不需要寫遞歸。
而是采用一種比較簡(jiǎn)單的做法，將BFS中的queue換成stack，就完成了核心代碼的編寫。
（靈感來源于二叉樹的先序遍歷的遞歸和非遞歸實(shí)現(xiàn)）
將BFS里面的queue改成stack就是先根遍歷了，可以調(diào)節(jié)一下每個(gè)結(jié)點(diǎn)的子樹遍歷次序，就是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二叉樹遍歷的遞歸和非遞歸實(shí)現(xiàn)，見。。。