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

本文以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);}//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都超时了，显而易见。
没必要求所有的结点的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);}//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
但还是有一个超时。
原因是对于不同的叶结点，它们到根的路径上是有重叠的。
而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;}//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优化失败，如果超时是由于重复访问树的结点造成的，只要保证树的结点只被遍历一次，就可以了。
五、树的层序遍历
树的层序遍历正好满足只遍历一次，而且还能记录树的高度。
树的表示法要改成“孩子法”，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;}//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。
六、树的先根遍历
既然采用“孩子法”来表示树 ，也可以先根遍历，同样是只访问树中结点一次，并且记录下所有结点的深度。
树的层序遍历，核心部分代码是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二叉树遍历的递归和非递归实现，见。。。