数据结构－树－『代码模板』

发表于 | 阅读次数:
字数统计: 170 字

有关于树这个数据结构，可以探讨的的东西有很多，但这篇博客是有关于树结构的一些代码模板，进行一下总结。

无根树转有根树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
//有根树转无根树
vector<int> G[MAXN];	//用vector存图
inline void Read_Tree()
{
	int u,v;
	scanf("%d",&n);
	for (int i=0;i < n-1; i++)
	{
		scanf("%d%d", &u, &v);
		G[u].push_back(v);
		G[v].push_back(u);
	}
}

inline void dfs(int u,int fa)	//转换为以 u 为根的子树，u 的父节点为fa
{
	int d = G[u].size();
	for (int i = 0; i < d; i++)
	{
		int v = G[u][i];
		if (v != fa)	dfs(v, p[v] = u);
	}
}