A3阶段 第四课 树

2025年6月28日

学习时长

约1.6小时

难度

A3阶段/CSP-J

标签

数据结构

讲师

王骏峣

线性数据结构

包括数组、栈、队列、向量、链表等

特征：若干相同数据类型的元素排成一行

树

有关定义：

树是一种树型数据结构
树的元素叫节点
连接节点的线叫边
根节点没有前驱节点，叶子节点没有后继节点
所以由n个节点和(n-1)条边构成的连通结构称为树

有一个确定的根节点的树叫有根树，没有明确根节点的树叫无根树

树的有关概念

父节点和子节点：若某节点能向下生成一些节点，那么该节点为生成节点的父节点,生产节点为该节点的子节点
祖先节点：从某节点出发，沿着根节点前进，路径上经过的所有节点都是该节点的祖先节点
节点的度：一个节点子节点的数量，成为节点的度
节点的深度：根的深度为1，根节点的子节点深度为2，以此类推，特别的，有时根节点深度视为0
树高：树中深度最大的节点的深度
k叉树：节点的度最多为k的树，常用的有二叉树
子树：从某节点出发，向下扩展所产生的树，成为该节点为根的子树

树的性质

除根节点外，其余节点都有一条连向父节点的边，所以n个节点的树有n-1条边
任意两点之间不经过重复边的路有且仅有一条，这条路的长度也被称为这两个节点的距离

C++中的树

树的存储

  1. 在C++中存储一棵树，需要将每个节点的相邻节点保存起来
  2. 一个节点可能有很多相邻节点，但总的相邻节点对数为2*(n-1)，联想到使用vector数组（vector<int> e[N];）

树的常见输入格式

给定一个正整数n，表示节点个数
接下来(n-1)行，每行两个整数u、v，代表存在一条连接u、v的边
这里每一条边都是一组相邻关系，e[u].push_back(v);e[v].push_back(u);


代码：

树的存储
vector<int> e[N];
int main(){
  cin>>n;
  for(int i = 1;i < n;i ++){//注意n-1次
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
}

树的遍历（深度优先遍历）

  1. 递归实现的深度优先遍历
  2. 从根节点出发，安照深度优先的顺序依次进行遍历

代码实现：

树的遍历
void dfs(int u,int fa){
  //遍历当前节点u，父节点为fa
  cout << u << " ";
  for(int v : e[u])
  {//遍历u节点所有相邻节点编号
    if(v == fa)
      continue;
    dfs(v,u);
  }
}
//主函数调用dfs(1,0);

注意，代码中的fa变量是必须的，避免子节点调用父节点导致死循环，除非保存的相邻节点关系都是父节点指向子节点

树的遍历过程中还可以维护一些额外信息

常见的有节点的深度de[N]和每个节点为根的子树大小sz[N]

树的遍历
void dfs(int u,int fa){
  //遍历当前节点u，父节点为fa
  cout << u << " ";
  sz[u] = 1;
  for(int v : e[u])
  {//遍历u节点所有相邻节点编号
    if(v == fa)
      continue;
    de[v] = de[u]+1;
    dfs(v,u);
    sz[u] += sz[v];
  }
}
//主函数调用dfs(1,0);

例题

第一题 猫猫和企鹅

前往

解析：
n个居住区抽象为点，n-1条道路抽象为边
从每一个居住区出发都可以到达任意一个居住区 等价于连通
这样的结构就是树
题意：
有多少个节点距离节点1不超过d
以1号点为根，设de[1]=0，则i号点到1的距离就等于de[i]
最后求有多少个de[i] <= d

例题1
#include <bits/stdc++.h>
const int N = 100005;
using namespace std;
int n,d,u,v,de[N],ans;
vector <int> e[N];
void dfs(int u,int fa){
  for(int v:e[u])
  {
    if(v == fa) continue;
    de[v] = de[u] + 1;
    if(de[v] <= d){
      ++ans;
      dfs(v,u);
    }
  }
}
int main(){
  cin >> n >> d;
  for(int i = 1;i < n;i ++){
    cin >> u >> v;
    e[u].push_back(v);
    e[v].push_back(u);
  }
  dfs(1,0);
  cout << ans;
}

第二题 Power Strip

前往

题意：
给定n个插排以及每个插排上充电器的数量
插排之间构成了树
求每个插排向多少个充电器供电，插排i向某个充电器供电的定义为点从插座流向充电器的过程中经过了插排i
解析：
插排i向某个充电器供电，当且仅当充电器所在的插排在以i为根的子树中
把插排上的充电器数量当作该插排的权值
题目询问等价于询问每个点为根的子树权值之和
自底向上进行统计类似与统计子树大小sz[]
建树时只需要保存父节点指向子节点的边

例题2
#include <bits/stdc++.h>
const int N = 100005;
using namespace std;
int n,m,k,s,t,x;
long long w[N];
vector <int> e[N];
void dfs(int u){
  for(int v:e[u])
  {
    dfs(v);
    w[u] += w[v];
  }
}
int main(){
  cin >> n;
  for(int i = 2;i <= n;i ++){
    cin >> x;
    e[x].push_back(i);
  }
  for(int i = 1;i <= n;i ++)
    cin >> w[i];
  dfs(1);
  for(int i = 1;i <= n;i ++)
    cout << w[i];
}

带权边

当边有长度时，，需要额外保存边的长度

带权边
vector <pair<int,int>> e[N];

使用带权边的树的遍历

使用带权边树的遍历
void dfs(int u,int fa){
  //遍历当前节点u，父节点为fa
  cout << u << " ";
  for(auto i : e[u])
  {//遍历u节点所有相邻节点编号
    int v = i.first, l = i.second;
    if(v == fa)
      continue;
    dfs(v,u);
  }
}
//主函数调用dfs(1,0);

使用auto和双重后尖括号（>>）需要C++11以上标准，需要添加编译选项“-std=c++11”

第三题 [NOI2011] 道路修建

前往

题意：
给定一棵树，定义一条边的代价为边的长度乘以两端点的个数之差的绝对值
求n-1条边的代价之和 解析：
以一个点为根进行遍历

例题3
#include <bits/stdc++.h>
#define ll long long;
const int N = 100005;
using namespace std;
int n,d,u,v,sz[N],k;
ll ans;
vector <pair<int,int>> e[N];
void dfs(int u,int fa){
  sz[u] = 1;
  for(auto i:e[u])
  {
    int v = i.first,l = i.second;
    if(v == fa) continue;     dfs(v,u);
    ans += (long long)l * abs(n - 2 * sz[v]);
    sz[u] += sz[v];
  }
}
int main(){
  cin >> n;
  for(int i = 1;i < n;i ++){
    cin >> u >> v >> k;
    e[u].push_back({v,k});
    e[v].push_back({u,k});
  }
  dfs(1,0);
  cout << ans;
}

二叉树

有关的定义和特征

  1. 二叉树：所有节点的度都不大于2的树
  2. 满二叉树：除最后一层无任何子节点外，每一层上的结点都有两个子节点的二叉树
    性质：第k层有2^k个结点
  3. 完全二叉树：除最后一层外，其他每层节点都是满的，且最后一层节点按从左往右顺序排列
  4. 儿子节点和兄弟节点：二叉树的每个节点最多只有两个子节点，称为左儿子和右儿子，且它们互称为兄弟节点
  5. 可以方便地用数组存储，即从上到下，从左到右存储为a[1]、a[2]、a[3]...

真题

(CSP2020入门级第一轮)独根树的高度为1，具有61个节点的完全二叉树高度是()
A.7
B.8
C.5
D.6

正确答案：D

(NOIP2018普及组初赛)根节点深度为0，一棵深度为h的满k(k>1）叉树，即除最后一层无任何子节点外，每一层上的结点都有k个子节点的树，共有()个节点
A.[k^(h+1)-1]/(k-1)
B.k^(h-1)
C.k^h
D.[k^(h-1)]/(k-1)

正确答案：A

(CSP2023入门级第一轮)根节点高度为1，一颗拥有2023个节点的三叉树高度至少为
A.6
B.7
C.8
D.9

正确答案：C

第四题 医院设置

前往

题意：
给定一棵二叉树，点有点权，需要找到一个点，满足其他点的权值乘以到该点的距离之和尽量小
求这个最小值(n <= 100) 解析：
首先忽略二叉树，考虑普通树怎么做
枚举在点i建医院
以i为根遍历整棵树，其他点到i的距离就等于深度
以每一个点为根遍历一遍树，算出答案后取最小值，时间复杂度O(n^2)

例题3
#include <bits/stdc++.h>
const int N = 105;
using namespace std;
int n,m,k,u,v,ans,w[N],de[N];
vector <int> e[N];
void dfs(int u,int fa){
  ans += de[u] * w[u];
  for(int v:e[u])
  {
    if(v == fa) continue;
    de[v] += de[u] + 1;
    dfs(v,u);
  }
}
int main(){
  cin >> n;
  for(int i = 1;i <= n;i ++){
    cin >> w[i] >> u >> v;
    if(u){
      e[i].push_back(u);
      e[u].push_back(i);
    }
    if(v){
      e[i].push_back(v);
      e[v].push_back(i);
    }
  }
  int mi = 0x3f3f3f3f;
  for(int i = 1;i <= n;i ++){
    ans = 0;
    de[i] = 0;
    dfs(i,0);
    mi = min(mi,ans);
  }
  cout << mi;
}

总结

  1. 由n个节点和n-1条边构成的连通结构称为树
  2. 一般用vector存储树
  3. 对于一条边<u,v>，如果能确定父节点为u，子节点为v，那么执行e[u].push_back(v)
  4. 否则同时执行e[u].push_back(v);e[v].push_back(u);
  5. 树的遍历使用递归写法的DFS，可同时维护de[]和sz[]