当前位置：首页 > ops >正文

关于树（按序遍历，搜索，LCA）

ops 2025/7/27 7:37:29

When thunder clouds start pouring down

Light a fire they can’t put out

Carve your name into those shining stars

He said: "Go venture far beyond the shores

Don’t forsake this life of yours

I’ll guide you home no matter where you are"

————Avicii

这是一篇迟到的博客。上周学树🌳的时候基本都是按照别人的思路，没有一点自己的理解。不同题之间建树、解题方法也是五花八门，所以上篇关于树的博客也比较潦草。经过萌新联赛我感觉那道关于树的题还是完全能写的，所以对树又更深的探索了一下，于是写下这篇博客。当然，这篇博客也是相对基础，算是来到了树的根节点吧。之后得向上爬呀~

简单了解

关于树的题，解题方法真是五花八门。就光一个建树就给我弄的眼花缭乱（l、r 数组，结构体，邻接表····）。我建议还是按照自己的习惯确定一种建树的方法。需要注意的是：树也分为很多种，二叉树，多叉树，有向树，无向树····在有些条件下一些方法是受限制的。比如要建无向树或多叉树的话l、r数组、结构体就显得有些笨拙。因为每个分叉都要有单独的变量去存。我的建议是尽量用邻接表去存，说人话就是vector q[N]。反正对于我来说，正是通过这种建树方式才让我对树在后面的推进更进一步。当然，这个也要根据题型来定，结构体处理二叉树问题还是比较好用的，可以直接存储左右节点、父节点、深度等等···下面就从最基本的建树和搜索来简单说一下。

建树

分别以邻接表和结构体的方法来演示：

for(int i=1; i<n; i++)
{int u,v;cin >> u >> v;q[u].push_back(v);//没说有向q[v].push_back(u);
}

for(int i=1; i<n; i++)
{cin >> u >> v;if(!t[u].l) t[u].l=v;//优先插入左节点else t[u].r=v;t[v].f=u;//更新父节点
}

搜索

接下来简单说一下搜索。搜索可以说是树的灵魂了，只要有树那么必有搜索。因为树的结构比较复杂，树上有很多信息无法直接获取，需要通过搜索来获取相关的信息。关于搜索的方式先展示一下比较基础的。

void dfs(int x, int d)//当前节点,当前深度
{dep=max(dep,d);if(t[x][0] != 0)//子节点不为叶子节点就继续向下搜dfs(t[x][0],d+1);if(t[x][1] != 0)dfs(t[x][1],d+1);
}
void solve()
{cin >> n;for(int i=1; i<=n; i++)//建树{cin >> l >> r;t[i].push_back(l);t[i].push_back(r);}dfs(1,1);//节点,当前深度cout << dep;
}

本题是求解树的最大深度，用到了最基本的树的DFS搜索。需要注意的是，本题建的是有向边的树，下面看一下无向边的。

void dfs(int u, int fa)//当前节点和父节点
{for(auto v:q[u])//继续搜索{if(v!=fa)dfs(v,u);}
}
for(int i=1; i<n; i++)
{int u,v;cin >> u >> v;q[u].push_back(v);//没说有向q[v].push_back(u);
}

可以看出来，由于无向边是双向的，可能会往回遍历。所以在搜索的时候需要同时传递此时的节点和父节点，在进行下一次搜索的时候注意判断下一个搜索的节点不能是自己的父节点，不然会产生死循环。

经过前面的简单介绍应该对树也建立起初步的框架了，下面就来几道相关的题目

按序遍历

二叉树的遍历(前中后序)

来源：https://www.luogu.com.cn/problem/B3642

思路

首先先对树的遍历规则进行梳理：

前序遍历：根、左、右
中序遍历：左、根、右
后序遍历：左、右、根

非常的模板，下面直接看代码

代码

void dfs(int x)//前序,根左右
{if(a) cout << x << ' ';//前序,根左右if(q[x][0]) dfs(q[x][0]);if(b) cout << x << ' ';//中序,左根右if(q[x][1]) dfs(q[x][1]);if(c) cout << x << ' ';//后序,跟左右
}void solve()
{cin>>n;for(int i=1;i<=n;i++){cin >> l >> r;q[i].push_back(l);q[i].push_back(r);}a=0,b=0,c=0;a=1,dfs(1),a=0,cout << endl;b=1,dfs(1),b=0,cout << endl;c=1,dfs(1);
}

为了避免冗余我进行了一些处理，可能不是特别的直观

搜索

其实每个题都沾点搜索，我就拿点经典吧。

新二叉树

来源：https://www.luogu.com.cn/problem/P1305

vector<char> q[50];
void dfs1(char ch)
{cout << ch;if(q[ch][0]!='*') dfs1(q[ch][0]);if(q[ch][1]!='*') dfs1(q[ch][1]);
}void solve()
{cin >> n;string s1;cin >> s1;char c=s1[0];//开始的节点必须是根节点,所以单独处理一下q[c].push_back(s1[1]);q[c].push_back(s1[2]);for(int i=1; i<n; i++){cin >> s;q[s[0]].push_back(s[1]);q[s[0]].push_back(s[2]);}dfs1(c);
}

二叉树问题

来源：[P3884 JLOI2009] 二叉树问题 - 洛谷

BFS

void BFS()
{memset(a,0,sizeof(a));//广搜一定要标记a[x]=1;queue<dist> q;q.push({x,0});//BFS模板while(!q.empty()){auto f=q.front();q.pop();if(f.pos==y)//到达目标点{cout << f.step;break;}int le=t[f.pos].l;int ri=t[f.pos].r;int fa=t[f.pos].f;int step=f.step;if(le&&!a[le])//存在此节点且没有走过{a[le]=1;q.push({le,step+1});}if(ri&&!a[ri]){a[ri]=1;q.push({ri,step+1});}if(fa&&!a[fa])//向上走加两步{a[fa]=1;q.push({fa,step+2});}}
}

DFS

void dfs(int x)
{if(a[x]) return ;//走过的就不走了a[x]=1;int le=t[x].l,ri=t[x].r,de=t[x].d;maxd=max(maxd,de);//更新深度w[de]++;if(le)//如果有左节点就继续搜{t[le].d=de+1;dfs(le);}if(ri){t[ri].d=de+1;dfs(ri);}
}

最近共同祖先（LCA）【倍增法】

对照一道例题来看：P3379 【模板】最近公共祖先（LCA） - 洛谷

关键概念：

节点深度：从根节点到该节点的路径长度
公共祖先：同时是两个节点祖先的节点
最近公共祖先：所有公共祖先中深度最大的节点

示例树：

        1/   \2     3/ \   / \4   5 6   7/ \8   9

节点 8 和 5 的 LCA 是 2
节点 6 和 7 的 LCA 是 3
节点 4 和 9 的 LCA 是 4

朴素算法思路与局限性

朴素算法步骤：

将较深的节点向上移动，直到与另一个节点深度相同
同时向上移动两个节点，直到相遇

示例：查找节点 8 和 5 的 LCA

        1/   \2     3/ \   / \4   5 6   7/ \8   9

节点 8 的深度是 4，节点 5 的深度是 3
将节点 8 向上移动一步，到达节点 4（深度 3）
同时向上移动节点 4 和 5，一步后到达节点 2，相遇
LCA 是节点 2

时间复杂度：每次查询 O (h)，h 是树的高度。最坏情况下（链状树）为 O (n)。

局限性：当树的高度很大时效率较低，尤其在需要处理大量查询时。

倍增法的核心思想：二进制优化

其实，在背包九讲中也有一个是用二进制进行优化，可见它真的有用😄

核心思想：预先计算每个节点的 2^k 级祖先，利用二进制分解的思想快速跳跃。

为什么选择 2 的幂次？

任何整数都可以表示为 2 的幂次之和（例如：13 = 8 + 4 + 1 = 2³ + 2² + 2⁰）
通过预处理 2 的幂次级祖先，可以在 O (log n) 时间内完成任意步数的跳跃

预处理数组：
定义f[u][k]表示节点 u 的第 2^k 级祖先。例如：

f[u][0]是 u 的父节点
f[u][1]是 u 的祖父节点（2 级祖先）
f[u][2]是 u 的曾祖父节点（4 级祖先）

预处理递推公式：

f[u][k] = f[f[u][k-1]][k-1]

示例树的预处理结果：

        1/   \2     3/ \   / \4   5 6   7/ \8   9

节点 8 的预处理数组：
- f[8][0] = 4（父节点）
- f[8][1] = 2（祖父节点）
- f[8][2] = 1（曾祖父节点）
- f[8][3及以上] = 0（超出树的高度）

倍增法预处理过程详解

预处理步骤：

通过 DFS 遍历树，记录每个节点的深度和父节点
利用递推公式计算每个节点的 2^k 级祖先

DFS 过程示例：

        1/   \2     3/ \   / \4   5 6   7/ \8   9

从根节点 1 开始 DFS
处理节点 1：
- depth[1] = 0
- f[1][0] = 0（根节点的父节点为虚拟节点 0）
处理节点 2：
- depth[2] = 1
- f[2][0] = 1
- 计算 2 的 2^k 级祖先：
  - f[2][1] = f[f[2][0]][0] = f[1][0] = 0
处理节点 4：
- depth[4] = 2
- f[4][0] = 2
- 计算 4 的 2^k 级祖先：
  - f[4][1] = f[f[4][0]][0] = f[2][0] = 1
  - f[4][2] = f[f[4][1]][1] = f[1][1] = 0
依此类推，处理所有节点

预处理代码片段：

void dfs(int u, int fa)//当前节点和父节点
{dep[u]=dep[fa]+1;//当前节点的深度为父节点+1f[u][0]=fa;//2^0(1)级祖先是自己的父节点for(int i=1; i<=lim; i++)//2^(i-1)级祖先的2^(i-1)级祖先是2^k级祖先f[u][i]=f[f[u][i-1]][i-1];for(auto v:q[u])//继续搜索{if(v!=fa)dfs(v,u);}
}

倍增法查询过程详解

查询步骤：

将较深的节点提升到与另一个节点相同的深度
同时向上提升两个节点，每次尝试最大的 2^k 步
最终两个节点会停在 LCA 的下一层，返回其父节点

示例：查找节点 8 和 5 的 LCA

        1/   \2     3/ \   / \4   5 6   7/ \8   9

步骤 1：调整深度
- 节点 8 深度 4，节点 5 深度 3
- 需要将节点 8 提升 1 步
- 分解 1 为 2^0，即提升 2^0 步
- 节点 8 → 节点 4，深度变为 3
步骤 2：同时提升
- 节点 4 和 5 深度相同，开始同时提升
- 尝试最大的 k=2：
  - f[4][2] = 1，f[5][2] = 1，相同，不提升
- 尝试 k=1：
  - f[4][1] = 2，f[5][1] = 2，相同，不提升
- 尝试 k=0：
  - f[4][0] = 2，f[5][0] = 2，相同，不提升
- 此时节点 4 和 5 重合，直接返回
结果：LCA 是节点 2

查询代码片段：

int LCA(int x, int y)
{if(dep[x]>dep[y]) swap(x,y);//确保y比x更深,便于处理for(int i=lim; i>=0; i--)//将两点拉到同一深度{if(dep[f[y][i]]>=dep[x])//如果y的2^i级祖先没超过x就往上跳y=f[y][i];}if(x==y) return x;for(int i=lim; i>=0; i--)//一起往上跳,跳到共同祖先{if(f[y][i]!=f[x][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}

复杂度分析

时间复杂度：

预处理：O (n log n)
单次查询：O (log n)

空间复杂度：O (n log n)（存储 f 数组）

适用场景：

静态树结构（树结构不频繁变化）
需要处理大量 LCA 查询

与朴素算法对比：

算法	预处理时间	单次查询时间	适用场景
朴素算法	O(n)	O(h)	少量查询，小树
倍增法	O(n log n)	O(log n)	大量查询，大树

完整代码

// Problem: P3379 【模板】最近公共祖先（LCA）
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3379
// Memory Limit: 512 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second 
#define endl '\n'
const int INF = 1e18;
const int N = 5e5+5;
int a[N];
int f[N][30];//代表x的第2^i级祖先,最多5e5,20个就够
int dep[N];
vector<int> q[N];//用来存树
string s;
int n,m,k;
int lim;
void dfs(int u, int fa)//当前节点和父节点
{dep[u]=dep[fa]+1;//当前节点的深度为父节点+1f[u][0]=fa;//2^0(1)级祖先是自己的父节点for(int i=1; i<=lim; i++)//2^(i-1)级祖先的2^(i-1)级祖先是2^k级祖先f[u][i]=f[f[u][i-1]][i-1];for(auto v:q[u])//继续搜索{if(v!=fa)dfs(v,u);}
}
int LCA(int x, int y)
{if(dep[x]>dep[y]) swap(x,y);//确保y比x更深,便于处理for(int i=lim; i>=0; i--)//将两点拉到同一深度{if(dep[f[y][i]]>=dep[x])//如果y的2^i级祖先没超过x就往上跳y=f[y][i];}if(x==y) return x;for(int i=lim; i>=0; i--)//一起往上跳,跳到共同祖先{if(f[y][i]!=f[x][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}
void solve()
{cin >> n >> m >> k;for(int i=1; i<n; i++){int u,v;cin >> u >> v;q[u].push_back(v);//没说有向q[v].push_back(u);}lim=log2(n)+1;dfs(k,0);//根节点为k,假设其父节点为0for(int i=1; i<=m; i++){int x,y;cin >> x >> y;cout << LCA(x,y) << endl;}return ;
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T=1;// cin >> T;while(T--) solve();return 0;
}

总结

倍增法通过预处理每个节点的 2^k 级祖先，利用二进制分解的思想，将 LCA 查询的时间复杂度从 O (h) 优化到 O (log n)，是处理静态树 LCA 问题的高效方法。

核心要点：

预处理数组f[u][k]存储节点 u 的第 2^k 级祖先
递推公式：f[u][k] = f[f[u][k-1]][k-1]
查询时通过二进制分解快速跳跃

题目回顾(优化之前题目)

别急，还没完！学了这个最近共同祖先之后，我突发奇想，那我是不是可以用这个方法往之前那个题：二叉树问题上面套一下？

题目重现：JLOI2009] 二叉树问题 - 洛谷

简单分析

回顾一下：那个题我们求两点的代价的时候是用的BFS进行暴力搜索。如果说我们直接求出他们的共同祖先，是不是就直接可以通过共同祖先分别与他们两个的距离用O(1)直接计算出两点的距离了？并且！BFS是有局限性的，它只能求解固定的两点之间的距离。如果题上说给q次询问，每次给出x,y让你求两点到达所需的步骤，这你不炸了吗？难道每次都进行搜索吗？

看一下原来的DFS函数：

void dfs(int x)
{if(a[x]) return ;//走过的就不走了a[x]=1;int le=t[x].l,ri=t[x].r,de=t[x].d;maxd=max(maxd,de);//更新深度w[de]++;if(le)//如果有左节点就继续搜{t[le].d=de+1;dfs(le);}if(ri){t[ri].d=de+1;dfs(ri);}
}

可以看到，这个搜索中只是统计了深度以及进行下一步搜索，那我为何不顺便让它把祖先数组F和深度数组dep给预处理出来呢？于是就变成了下面这样：

void dfs(int u)
{if(a[u]) return ;//走过的就不走了a[u]=1;int le=t[u].l,ri=t[u].r;int fa=t[u].f,de=t[u].d;maxd=max(maxd,de);//更新深度w[de]++;
//——————————————————————————————————————————————下面开始处理共同祖先dep[u]=dep[fa]+1;//当前节点的深度为父节点+1f[u][0]=fa;//2^0(1)级祖先是自己的父节点for(int i=1; i<=lim; i++)//2^(i-1)级祖先的2^(i-1)级祖先是2^k级祖先f[u][i]=f[f[u][i-1]][i-1];if(le)//如果有左节点就继续搜{t[le].d=de+1;dfs(le);}if(ri){t[ri].d=de+1;dfs(ri);}
}

step计算

最后计算所需步骤的时候就非常的简单了：

cin >> x >> y;int lca=LCA(x,y);int step=(dep[x]-dep[lca])*2+(dep[y]-dep[lca]);cout << step;

完整代码

// Problem: P3884 [JLOI2009] 二叉树问题
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P3884
// Memory Limit: 128 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pii pair<int, int>
#define fi first
#define se second 
#define endl '\n'
const int INF = 1e18;
const int N = 1e6+5;
int a[N];//标记数组
int n,m;
int u,v;
int x,y;
string s;
int maxd,maxw;//最大深度、宽度
int w[N],dep[N];//宽度数组
int f[N][30];//代表x的第2^i级祖先,最多5e5,20个就够
int lim;
struct tree
{int l;//左节点int r;//右节点int f;//父节点int d;//此时的深度
}t[105];
struct dist//广搜的结构体
{int pos;int step;
};
void dfs(int u)
{if(a[u]) return ;//走过的就不走了a[u]=1;int le=t[u].l,ri=t[u].r;int fa=t[u].f,de=t[u].d;maxd=max(maxd,de);//更新深度w[de]++;
//——————————————————————————————————————————————下面开始处理共同祖先dep[u]=dep[fa]+1;//当前节点的深度为父节点+1f[u][0]=fa;//2^0(1)级祖先是自己的父节点for(int i=1; i<=lim; i++)//2^(i-1)级祖先的2^(i-1)级祖先是2^k级祖先f[u][i]=f[f[u][i-1]][i-1];if(le)//如果有左节点就继续搜{t[le].d=de+1;dfs(le);}if(ri){t[ri].d=de+1;dfs(ri);}
}
int LCA(int x, int y)
{if(dep[x]>dep[y]) swap(x,y);//确保y比x更深,便于处理for(int i=lim; i>=0; i--)//将两点拉到同一深度{if(dep[f[y][i]]>=dep[x])//如果y的2^i级祖先没超过x就往上跳y=f[y][i];}if(x==y) return x;for(int i=lim; i>=0; i--)//一起往上跳,跳到共同祖先{if(f[y][i]!=f[x][i]){x=f[x][i];y=f[y][i];}}return f[x][0];
}
void solve()
{cin >> n;for(int i=1; i<n; i++){cin >> u >> v;if(!t[u].l) t[u].l=v;//优先插入左节点else t[u].r=v;t[v].f=u;//更新父节点}t[1].d=1;lim=log2(n)+1;dfs(1);//开始深搜for(int i=1; i<=n; i++)//找最大宽度	maxw=max(maxw,w[i]);cout << maxd << endl;cout << maxw << endl;cin >> x >> y;int lca=LCA(x,y);//找共同祖先int step=(dep[x]-dep[lca])*2+(dep[y]-dep[lca]);//直接计算所需步数cout << step;
}
signed main()
{ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);int T=1;// cin >> T;while(T--) solve();return 0;
}