• 日期: 2026-08-17
  • 标签: 程序员

1.引入：树和图的关系

  • 图：由节点和边组成的结构，边可以有方向（有向图）也可以没有方向（无向图）

  • 树：一种特殊的图——连通且无环的无向图

换句话说，树是最简单的图。树有\(N\)个节点和\(N-1\)条边，任意两个节点之间有且仅有一条简单路径。

正因为树的这种特殊性质，很多图上的问题在树上会变得简单很多。但反过来说，树的遍历和存储方式，完全适用于一般的图。

2.图的存储方式

在做题之前，我们要首先掌握图的两种存储方式

2.1邻接矩阵

用一个二维数组\(e[u][v]\)表示\(u\)到\(v\)是否有边\((1\)表示有边，\(0\)表示无边\()\)。

例：

图：

files


邻接矩阵：
1节点 2节点 3节点 4节点 5节点 6节点
1节点 1//自己
与自己
连通		 1//1节点
与2节点
连通		 0 0 0 1
2节点 1 1 0 0 1 0
3节点 0 0 1 1 0 0
4节点 1 0 1 1 0 0
5节点 0 1 0 0 1 0
6节点 1 0 0 0 0 1

代码实现：

#include
using namespace std;
int n,m;
int g[105][105];//定义数组
int main(){
    cin>>n>>m;//输入
    for(int i=1;i<=m;i++){
        int u,v;
        cin>>u>>v;//输入有边的两个节点
        g[u][v]=1;//标记
        g[v][u]=1;
    }
    for(int i=1;i<=n;i++){
        for(int j=1;j<=n;j++){
            cout<

2.2邻接表

用 vector 数组存储每个节点的所有邻居。

代码实现：

#include
using namespace std;
int n,m;
vectore[1005];//定义
int main() {
    scanf("%d%d",&n,&m);//输入
    for(int i=0;i


3.树的遍历

3.1dfs

从根节点出发，沿着一条路径走到最深处，再回溯。

核心代码：

void dfs(int u,int fa) //u表示当前节点，fa表示当前节点的父节点
    for(int v:e[u]) {//枚举此节点的所有子节点（包括父节点）
        if(v==fa) continue;//特判父节点
        dfs(v,u);//继续向下走
    }
}

3.2bfs

BFS按层遍历，用队列实现。

核心代码:

void bfs(int s) {//传入根节点
    queueq;//定义队列
    q.push(s);//加入队列
    vis[s]=1;//标记根节点已访问
    while(!q.empty()) {//队列非空
        int u=q.front();
        q.pop();
        for(int v:e[u]) {//枚举所有子节点
            if(!vis[v]) {//未被访问
                vis[v]=1;//标记已访问
                q.push(v);//加入队列
            }
        }
    }
}

4.二叉树

二叉树是一种特殊的树，每个节点最多有两个子节点（左孩子和右孩子）。

4.1三种遍历方法

  • 前序遍历：按照根左右的顺序遍历
void dfs1(int now) {//now为当前节点
    cout<
  • 中序遍历：按照左根右的顺序遍历
void dfs2(int now) {
    int a=e[now].front(),b=e[now].back();//a为左孩子，b为右孩子
    if(a!=0) dfs2(a);//枚举左子树
    cout<
  • 后序遍历：按照左右根的顺序遍历
void dfs3(int now) {
    for(int i:e[now]) {//枚举左孩子和右孩子
        if(i==0) continue;
        dfs3(i);//继续枚举
    }
    cout<

4.2根据遍历序列还原树

已知前序+中序求后序，是二叉树的经典问题。

核心原理： 前序的第一个字符是根，在中序中找到根的位置，左边是左子树，右边是右子树。

代码实现：

#include
using namespace std;
string s1,s2;
void f(string a,string b) {//上传剩余的前序和中序遍历
    if(a.size()==0) {//空
        return ;
    } 
    int pos=0;
    while(b[pos]!=a[0]) pos++;//寻找当前子树的根节点在中序遍历中的位置
    f(a.substr(1,pos),b.substr(0,pos));//左边
    f(a.substr(pos+1),b.substr(pos+1));//右边
    cout<>s1>>s2;//输入前序遍历和中序遍历
    f(s1,s2);//开始递归
    return 0;
}

5.最近公共祖先lca

在一棵树中，节点\(u\)和节点\(v\)的\(LCA\)，就是这两个节点在树上的所有公共祖先中，深度最深的那个（即离它们最近的）。

5.1暴力lca

核心逻辑： 把两个节点“往上提”，提到同一深度，再一起往上走，第一次相遇的位置就是 LCA。


代码实现：

#include
using namespace std;
int n,m,s;
vectore[500005];
int fa[500005],dep[500005];
void dfs(int now,int f) {//标记父节点
    fa[now]=f;//标记
    dep[now]=dep[f]+1;//记录深度
    for(int i:e[now]) {//枚举所有子节点
        if(i==f) continue;//特判
        dfs(i,now);//继续枚举子树
    }
}
int main() {
    cin>>n>>m>>s;//s为根节点编号
    for(int i=1;i>x>>y;
        e[x].push_back(y);//存储
        e[y].push_back(x);
    }
    dep[0]=0;
    dfs(s,0);//标记
    for(int i=1;i<=m;i++) {
        int a,b;cin>>a>>b;//输入两个节点
        if(dep[b]

时间复杂度： \(O(N)\) 每次查询


6.树形dp入门

树形\(DP\)是在树上做动态规划，通常采用后序遍历（先算子节点，再算父节点）。

经典题：没有上司的舞会

题目描述

某大学有 \(n\) 个职员，编号为 \(1\ldots n\)。

他们之间有从属关系，也就是说他们的关系就像一棵以校长为根的树，父结点就是子结点的直接上司。

现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 \(r_i\)，但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。

所以，请你编程计算，邀请哪些职员可以使快乐指数最大，求最大的快乐指数。

输入格式

输入的第一行是一个整数 \(n\)。

第 \(2\) 到第 \((n + 1)\) 行，每行一个整数，第 \((i+1)\) 行的整数表示 \(i\) 号职员的快乐指数 \(r_i\)。

第 \((n + 2)\) 到第 \(2n\) 行，每行输入一对整数 \(l, k\)，代表 \(k\) 是 \(l\) 的直接上司。

输出格式

输出一行一个整数代表最大的快乐指数。

输入输出样例 #1

输入 #1

7
1
1
1
1
1
1
1
1 3
2 3
6 4
7 4
4 5
3 5

输出 #1

5

说明/提示

数据规模与约定

对于 \(100\%\) 的数据，保证 \(1\leq n \leq 6 \times 10^3\)，\(-128 \leq r_i\leq 127\)，\(1 \leq l, k \leq n\)，且给出的关系一定是一棵树。

解题方法

  • 状态定义：
dp[u][0]：u 不参加时，子树的最大快乐值
dp[u][1]：u 参加时，子树的最大快乐值
  • 状态转移：
dp[u][0]+=max(dp[v][0],dp[v][1]);//参加(u为v的直属上司)
dp[u][1]+=dp[v][0]; //不参加
  • 代码实现：
#include
using namespace std;
int n;
vectore[6005];
int a[6005];
int dp[6005][2];
int d[6005];
void dfs(int now) {
    dp[now][0]=0;//不参加
    dp[now][1]=a[now];//参加
    for(int i:e[now]) {
        dfs(i);//枚举子节点
        dp[now][0]+=max(dp[i][0],dp[i][1]);
        dp[now][1]+=dp[i][0];//状态转移
    }
}
int main() {
    cin>>n;
    for(int i=1;i<=n;i++) cin>>a[i];
    for(int i=1;i>u>>v;
        e[v].push_back(u);
        d[u]++;
    }
    int rt=0;//找根
    for(int i=1;i<=n;i++) {
        if(d[i]==0) {//没有父节点
            rt=i;
            break;//找到后立即退出
        }
    }
    dfs(rt);
    cout<

7.树的直径

树的直径就是树上最远的两个节点的距离

  • 状态定义：
dp[now][0]//经过now节点的最长链长度
dp[now][1]//经过now节点的次长链长度
  • 状态转移：
if 候选值>dp[now][0]：
   dp[now][1]=dp[now][0];   // 原来的最长变成次长
   dp[now][0]=候选值;       // 更新最长
else if 候选值>dp[now][1]：
   dp[now][1]=候选值;      // 更新次长
  • 代码实现：
#include
using namespace std;
int n;
vectore[100005];//邻接表
int dp[100005][2];//dp数组
void dfs(int now,int fa) {
    dp[now][0]=dp[now][1]=0;
    for(int i:e[now]) {//枚举子节点
        if(i==fa) continue;//特判
        dfs(i,now);//继续枚举
        if(dp[i][0]+1>dp[now][0]) {//状态转移方程
            dp[now][1]=dp[now][0];
            dp[now][0]=dp[i][0]+1;
        }
        else if(dp[i][0]+1>dp[now][1]) {
            dp[now][1]=dp[i][0]+1;
        }
    }
}
int main() {
    cin>>n;
    for(int i=1;i>u>>v;//输入节点
        e[u].push_back(v);//更新邻接表
        e[v].push_back(u);
    }
    dfs(1,0);//1节点为根
    int ans=INT_MIN;//寻找最大值
    for(int i=1;i<=n;i++) {//枚举
        ans=max(dp[i][0]+dp[i][1],ans);
    }
    cout<

8.推荐练习题目

"

原文地址: https://www.cveoy.top/t/topic/qHmm 著作权归作者所有。请勿转载和采集!

免费AI点我,无需注册和登录