树
今天我们来学习
树
如果一张图中只存在直接的父子关系,会构成一张特殊的图,而这张特殊的图就被我们称为树。
树的特征
- 每个节点只会有一个唯一的父亲。
- 如果一棵树有
n 个节点,那这棵树一定只有n-1 条边,因为树没有形成环。
而我们通常用边表示父子关系。
根结点
在一棵树中,有一个特定的结点称之为根,根本身是没有父亲结点的。
因此树可以分为两类
- 无根树,任意一个结点都能当做根。
- 有根树,指定点为根。
树的度
树跟图一样,也有度。
树的度:父亲结点的直接儿子数。
当指定根结点后,除了根结点,别的结点都只有一个父亲。一个结点可能有若干个子结点,没有子结点的结点称之为叶子结点。树上的所有结点一定连通,且没有环。
连通:任意选取两个结点都可以从一个结点到另一个结点。
建树的方式
父子表示法:
用数组记录每个结点的父亲。
孩子表示法
运用动态数组
树的深度和子树
深度
深度表示从根结点到叶子结点经历的层数就是树的深度,依题目要求,根结点深度不固定。
子树
选定树中任意一个结点作为根,以这个点为根的树即是这棵树的子树。
讲子树就要现将树的大小了。
- 树的大小:所有结点的数量。
- 子树的大小:找到一个结点作为根,这个子树之内结点数量。
求深度和子树的通用代码(树的模版)
void dfs(int u,int f){
dep[u]=dep[f]+1;//dep数组记录每个结点的深度
siz[u]=1;//siz数组记录每个结点的子树大小
for(int i=0;i<g[u].size();i++){
int v=G[u][i];
if(v!=f){//不重复走
dfs(v,u);
siz[u]+=siz[v];//让儿子把儿子的儿子和儿子的儿子的儿子...报上来
}
}
}列题
学完上面的内容了,相信你对数树已经有了一定的认知,所以来试试下面这道题把题。
是不是很简单内,看完上面,我们知道了根结点是没有父亲的。因此我们只需要找到即在输入中出现过,又没有父亲的结点。儿子最多的直接去
代码
#include<bits/stdc++.h>
#include<vector>
#include<queue>
using namespace std;
vector<int> g[1005];
bool vis[1005];
bool t[1005];
int main(){
int n,m;
cin>>n>>m;
for(int i=1;i<=m;i++){
int x,y;
cin>>x>>y;
g[x].push_back(y);
vis[y]=1;
t[x]=1;
t[y]=1;
}
int gen=0,maxn=0,x=0;
for(int i=1;i<=1000;i++){
if(!vis[i] && t[i]){
gen=i;
}
if(g[i].size()>maxn){
x=i;
maxn=g[i].size();
}
}
cout<<gen<<endl;
cout<<x<<endl;
sort(g[x].begin(),g[x].end());
for(int i=0;i<g[x].size();i++){
cout<<g[x][i]<<' ';
}
return 0;
}恭喜你,已经掌握树的度了,接下了是树的深度。
树的深度
这道题其实就是一棵树,你的深度越小,你在公司里的地位越高。地位最高的就是没有上司的了。由于没有上司的人不止一位,所以这道题中的树也不止一棵,所以不能一次搜索就完工,每次遇到
代码
#include<bits/stdc++.h>
#include<vector>
using namespace std;
int dep[1000005];
vector<int> g[1000005];
int z[1000005];
int maxn;
void dfs(int u,int f){
dep[u]=dep[f]+1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v!=f){
dfs(v,u);
}
}
return;
}
int main(){
int n;
cin>>n;
for(int i=1;i<=n;i++){
cin>>z[i];
if(z[i]!=-1){
g[z[i]].push_back(i);
g[i].push_back(z[i]);
}
}
for(int i=1;i<=n;i++){
if(z[i]==-1){
dfs(i,0);
}
}
for(int i=1;i<=n;i++){
maxn=max(maxn,dep[i]);
}
cout<<maxn;
return 0;
}好了万事俱备只欠"子树"。
这时候就会有人问了:这道题的根结点都不确定,那我们要怎么计算子树个数呢?是不是还得正着求一次子树,在反着求一次子树呢?其实这都不算事,等最后在告诉你们(#^.^#)
此时我们先按1为根结点,求出所有点的子树个数。
输出答案时,会得到两个点的子树,此时会有两种情况。
- 子树大的包含了子树小的。
- 两个子树没有相交。
此时不管是哪种情况,都满足两端的国家,一端是子树个数小的,而另一端就是除了子树个数小的以外的结点(
代码
#include<bits/stdc++.h>
#include<vector>
using namespace std;
int n;
long long l[1000005],r[1000005],c[1000005];
vector<int> g[1000005];
int siz[1000005];
void dfs(int u,int f){
siz[u]=1;
for(int i=0;i<g[u].size();i++){
int v=g[u][i];
if(v==f)continue;
dfs(v,u);
siz[u]+=siz[v];
}
return;
}
int main(){
cin>>n;
for(int i=1;i<n;i++){
cin>>l[i]>>r[i]>>c[i];
g[l[i]].push_back(r[i]);
g[r[i]].push_back(l[i]);
}
dfs(1,0);//以1作为根结点的子树
long long sum=0;
for(int i=1;i<n;i++){
int minn=min(siz[l[i]],siz[r[i]]);//获取子树小的作为一边
int k=n-minn;//获得另一边
sum+=abs(k-minn)*c[i];
}
cout<<sum;
return 0;
}