专栏文章

3.29周六晚上树上问题专题测总结

ccomcnSBhhh
算法·理论参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@mipqpi41
此快照首次捕获于
2025/12/03 16:23
3 个月前
此快照最后确认于
2025/12/03 16:23
3 个月前
查看原文

T1

题意分析：

题目描述

给定一棵树，输出树的根rootroot，孩子最多的结点maxmax以及他的孩子。

输出格式

第一行：树根：rootroot；
第二行：孩子最多的结点maxmax；
第三行maxmax的孩子（按编号由小到大输出）。
依此我们可以知道：本题给出一棵树的父子关系，让我们建树，再找出根和孩子最多的节点。

错误分析

CPP
#include<bits/stdc++.h>
using  namespace std;
int cnt[1007];
int fa[1007];
int ans=0;
int s_ans[1007];
int vis[1007];
int main()
{
//	freopen("t1_2.in","r",stdin);
//	freopen("t1_2.ans","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		fa[i]=-1;
	}
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		fa[y]=x;
	}
	int maxx=0,z_maxx=0;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(fa[i]==j)
			{
				cnt[j]++;
			}
			if(fa[i]==-1)
			{
				ans=i;
			}
			if(cnt[j]>maxx)
			{
				maxx=cnt[j];
				z_maxx=j;
			}
		}
	}
	int a=0;
	cout<<ans<<endl;
	cout<<z_maxx<<endl;
	for(int i=1;i<=n;i++)
	{
		for(int j=1;j<=n;j++)
		{
			if(fa[i]==z_maxx)
			{
				if(vis[i]==0)
				{
					s_ans[++a]=i;
					vis[i]=1;
				}
		    }
		}
	}
	for(int i=1;i<=a;i++)
	{
		cout<<s_ans[i]<<' ';
	}
	return 0;
}
总体来看就是没有使用方便找儿子的儿子表示法，是用模拟来做的。

正确代码实现

CPP
#include<bits/stdc++.h>
using  namespace std;
int cnt[1007];
int in[1007];
vector<int>op[1007];
int root;
int maxx,p;
int vis[1007];
int main()
{
//	freopen("t1_2.in","r",stdin);
//	freopen("t1_2.ans","w",stdout);
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++)
	{
		int x,y;
		cin>>x>>y;
		op[x].push_back(y);
		in[y]++;
		vis[x]=vis[y]=1;
	}
	for(int i=1;i<=1000;i++)
	{
		if(in[i]==0&&vis[i]==1)
		{
			root=i;
		}
	}
	for(int i=1;i<=1000;i++)
	{
		int siz=op[i].size();
		if(siz>maxx)
		{
			maxx=siz;
			p=i;
		}
	}
	sort(op[p].begin(),op[p].end());
	cout<<root<<endl<<p<<endl;
	for(int i=0;i<op[p].size();i++)
	{
		cout<<op[p][i]<<' ';
	}
	return 0;
}

T2

题意分析：

题目描述

给出一个二叉树的中序遍历和后序遍历，求出二叉树的前序遍历
依此我们可以知道：这就是我们在初赛练过但没考做过的题目给出一个二叉树的中序遍历和后序遍历，求出二叉树的前序遍历。

错误分析

CPP
#include<bits/stdc++.h>
using  namespace std;
string z,h;
int len;
int a;
void dfs1(char root)
{
	int len_z=z.size();
	string l=z;
	if(l.size()==0)
	{
		return;
	}
	for(int i=0;i<l.size();i++)
	{
		if(l[i]==root)
		{
			a=i;
		}
	}
	l=l.substr(0,a);
	int len_l=l.size();
	string cnt="";
	for(int i=0;i<len;i++)
	{
		for(int j=0;j<len_l;j++)
		{
			if(h[i]==l[j]&&h[i]!=root)
			{
				cnt+=h[i];
			}
		}
	}
	int len1=cnt.size();
	cout<<cnt[len1-1];
	z=z.substr(0,len_z-2);
	dfs1(cnt[len1-1]);
}
void dfs2(char root)
{
	int len_z=z.size();
	string r=z;
	if(r.size()==0)
	{
		return;
	}
	for(int i=0;i<r.size();i++)
	{
		if(r[i]==root)
		{
			a=i;
		}
	}
	r=r.substr(a,len-1);
	int len_r=r.size();
	string cnt="";
	for(int i=0;i<len;i++)
	{
		for(int j=0;j<len_r;j++)
		{
			if(h[i]==r[j]&&h[i]!=root)
			{
				cnt+=h[i];
			}
		}
	}
	int len1=cnt.size();
	cout<<cnt[len1-1];
	z=z.substr(0,len_z-2);
	dfs2(cnt[len1-1]);
}
int main()
{
    //freopen("T2.in","r",stdin);
	//freopen("T2.out","w",stdout);
	cin>>z>>h;
	len=h.size();
	char root=h[len-1];
	cout<<root;
	dfs1(root);
	dfs2(root);
	return 0;
}
用两个搜索分别处理根节点两边的左右子树，但并不能将它们关联起来，没有联系。

正确代码实现

CPP
#include<bits/stdc++.h>
using  namespace std;
string z,h;
int len;
int a;
void dfs(string z,string h)
{
	if(z.size()==0)
	{
		return;
	}
	len=h.size();
	char root=h[len-1];
	int pos=z.find(root);
	int l1=pos;
	int l2=len-pos-1;
	cout<<root;
	dfs(z.substr(0,l1),h.substr(0,l1));
	dfs(z.substr(pos+1,l2),h.substr(pos,l2));
}
int main()
{
    //freopen("T2.in","r",stdin);
	//freopen("T2.out","w",stdout);
	cin>>z>>h;
	dfs(z,h);
	return 0;
}

T3

题意分析：

题目描述

已知一棵二叉树用邻接表结构存储，中序查找二叉树中值为 x 的结点，并指出是第几个结点。例：如图二叉树的数据文件的数据格式如下: https://typora-code.oss-cn-shenzhen.aliyuncs.com/image-20250328192435024.png

输入格式

第一行nn为二叉树的结点个数；
第二行xx表示要查找的结点的值；
接下来给定nn列，第一列数据是各结点的值，
第二列数据是左儿子结点编号，第三列数据是右儿子结点编号。
依此我们可以知道：这题就是给出一棵树的中序遍历，让我们找点权等于xx的节点

错误分析

没交代码(￣▽￣)"

正确代码实现

CPP
#include<bits/stdc++.h>
using  namespace std;
struct node
{
	int v;
	int l,r;
}q[100007];
int n,x;
int ans;
void dfs(int u)
{
	if(q[u].l)
	{
		dfs(q[u].l);
	}
	ans++;
	if(x==q[u].v)
	{
		cout<<ans<<"\n";
		exit(0);
	}
	if(q[u].r)
	{
		dfs(q[u].r);
	}
	return;
}
int main()
{
    //freopen("xx.in","r",stdin);
	//freopen("xx.out","w",stdout);
	cin>>n>>x;
	for(int i=1;i<=n;i++)
	{
		cin>>q[i].v>>q[i].l>>q[i].r;
	}
	dfs(1);
	return 0;
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...