3.29周六晚上树上问题专题测总结
comcnSBhhh · · 算法·理论
T1
题意分析：
题目描述
给定一棵树，输出树的根
root ，孩子最多的结点max 以及他的孩子。输出格式
第一行：树根：
root ；第二行：孩子最多的结点
max ；第三行
max 的孩子（按编号由小到大输出）。
依此我们可以知道：本题给出一棵树的父子关系，让我们建树，再找出根和孩子最多的节点。
错误分析
#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;
}总体来看就是没有使用方便找儿子的儿子表示法，是用模拟来做的。
正确代码实现
#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
题意分析：
题目描述
给出一个二叉树的中序遍历和后序遍历，求出二叉树的前序遍历
依此我们可以知道：这就是我们在初赛练过但没考做过的题目给出一个二叉树的中序遍历和后序遍历，求出二叉树的前序遍历。
错误分析
#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;
}用两个搜索分别处理根节点两边的左右子树，但并不能将它们关联起来，没有联系。
正确代码实现
#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 的结点，并指出是第几个结点。例：如图二叉树的数据文件的数据格式如下:
输入格式
第一行
n 为二叉树的结点个数；第二行
x 表示要查找的结点的值；接下来给定
n 列，第一列数据是各结点的值，第二列数据是左儿子结点编号，第三列数据是右儿子结点编号。
依此我们可以知道：这题就是给出一棵树的中序遍历，让我们找点权等于
错误分析
没交代码(￣▽￣)"
正确代码实现
#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;
}