关于树的遍历和题目

2025-03-08 约 819 字预计阅读 2 分钟

https://bing.ee123.net/img/rand?artid=146049474

关于树的遍历和题目

用链式前向星实现孩子表示法

const int N = 1e5 + 10;
int id, e[2*N], ne[2*N], h[N];//哨兵位h存的是节点，ne和e两个数组存储的
//是父与子的关系，每条边都要存两遍，所以数组的大小要开两倍！！！
void add(int a, int b)
{
	id++;
	e[id] = a;
	ne[id] = h[a];
	h[a] = id;
}
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i <= n; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
}

深度优先遍历–DFS

法一：用vector实现

const int N = 1e5 + 10;
vector<int> edges[N];
bool st[N];
void dfs(int u)
{
	cout << u << " ";
	st[u] = true;
	for (auto v : edges[u])
	{
		if (!st[v])
		{
			dfs(v);
		}

	}
}
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	dfs(1);
}

法二：用链式前向星

const int N = 1e5 + 10;
int h[N], e[2 * N], ne[2 * N],id;
bool st[N];
void add(int a, int b)
{
	id++;
	e[id] = b;
	ne[id] = h[a];
	h[a] = id;
}
void dfs(int u)
{
	cout << u << " ";
	st[u] = true;
	for (int i = h[u]; i; i = ne[i])
	{
		int v = e[i];
		if (!st[v])
			dfs(v);
	}
}
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	dfs(1);
}

宽度优先遍历–BFS

法一：

#include <vector>
#include <queue>
using namespace std;
const int N = 1e5 + 10;
vector<int> edges[N];
bool st[N];
void bfs(int u)
{
	queue<int> q;
	q.push(1);
	st[1] = true;
	while (q.size())
	{
		auto u = q.front();
		q.pop();
		cout << u << " ";
		for (auto v : edges[u])
		{
			if (!st[v])
			{
				st[v] = true;
				q.push(v);
			}
		}
	}
}
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		edges[a].push_back(b);
		edges[b].push_back(a);
	}
	bfs(1);
	return 0;
}

法二：

const int N = 1e5 + 10;
int h[N], e[2 * N], ne[2 * N], id;
bool st[N];
void bfs(int u)
{
	queue<int> q;
	q.push(u);
	st[u] = true;
	cout << u << " ";
	for (int i = h[u]; i; i = ne[i])
	{
		int v = e[i];
		if (!st[v])
		{
			q.push(v);
			st[v] = true;
		}
	}
}
void add(int a, int b)
{
	id++;
	e[id] = b;
	ne[id]=h[a];
	h[a] = id;
}
int main()
{
	int n;
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int a, b;
		cin >> a >> b;
		add(a, b);
		add(b, a);
	}
	bfs(1);
	return 0;
}

二叉树问题

#include <iostream>
#include <vector>
#include <queue>
using namespace std;
const int N = 110;
int n;
vector<int> edges[N];
int fa[N], dist[N];
int dfs(int u)
{
	int ret = 0;
	for (auto v : edges[u])
	{
		ret = max(ret, dfs(v));
	}
	return ret + 1;
}
int bfs()
{
	queue<int> q;
	q.push(1);
	int ret = 0;
	while (q.size())
	{
		int sz = q.size();
		ret = max(ret, sz);
		while (sz--)
		{
			int u = q.front();
			q.pop();
			for (auto v : edges[u])
			{
				q.push(v);
			}
		}
	}
	return ret;
}
int main()
{
	cin >> n;
	for (int i = 1; i < n; i++)
	{
		int u, v;
		cin >> u >> v;
		edges[u].push_back(v);
		fa[v] = u;
	}
	cout << dfs(1) << endl;
	cout << bfs() << endl;
	int x, y;
	while (x != 1)
	{
		dist[fa[x]] = dist[x] + 1;
		x = fa[x];
	}
	int len = 0;
	while (y != 1 && dist[y] == 0)
	{
		len++;
		y = fa[y];
	}
	cout << dist[y] * 2 + len << endl;
	return 0;
}

已知前序，中序遍历求后序遍历

string a,b;
void dfs2(int l1, int r1, int l2, int r2)
{
	if (l1 > r1) return;
	int p = l1;
	while (a[p]!= b[l2])
		p++;
	dfs2(l1, p - 1, l2 + 1, l2 + p - l1);
	dfs2(p + 1, r1, l2 + p - l1 + 1, r2);
	cout << b[l2];
}
int main()
{
	cin >> a >> b;
	dfs2(0, a.size() - 1, 0, b.size());
	return 0;
}

目录

关于树的遍历和题目

关于树的遍历和题目