20220118二叉树
上午一直在查二叉树的资料,包括看大话数据结构这本书里关于二叉树的内容。收获很少,一方面写二叉树的语言有很多不是c,另一方面,包括书中都没有完整的代码,我看懂了意思但是就是不会写代码。下午上课也是,我听懂了但是还是写不出代码来,只能多写题来提升了。
新二叉树
题目描述
输入一串二叉树,输出其前序遍历。
输入格式
第一行为二叉树的节点数 nn。(1 \leq n \leq 261≤n≤26)
后面 nn 行,每一个字母为节点,后两个字母分别为其左右儿子。
空节点用 *
表示
输出格式
二叉树的前序遍历。
输入输出样例
输入 #1
6
abc
bdi
cj*
d**
i**
j**
输出 #1
abdicj
-
#include<bits/stdc .h>
-
using namespace std;
-
struct node{
-
char lc,rc,fa;
-
}tree[100000];
-
void f(char s) //按前序输出,父左右的顺序递归
-
{
-
cout<<s;
-
if (tree[s].lc!='*') f(tree[s].lc);
-
if (tree[s].rc!='*') f(tree[s].rc);
-
}
-
int main()
-
{
-
int n;
-
char c,head;
-
cin>>n; //输入结点数
-
for (int i=1;i<=n;i ){
-
cin>>c;
-
if (i==1) head = c; //head是根结点
-
cin>>tree[c].lc>>tree[c].rc; //中间结点
-
tree[tree[c].lc].fa = c; //父子关系
-
tree[tree[c].rc].fa = c;
-
}
-
f(head);
-
return 0;
-
}
搭配购买
题目描述
明天就是母亲节了,电脑组的小朋友们在忙碌的课业之余挖空心思想着该送什么礼物来表达自己的心意呢?听说在某个网站上有卖云朵的,小朋友们决定一同前往去看看这种神奇的商品,这个店里有 nn 朵云,云朵已经被老板编号为 1,2,3,...,n1,2,3,...,n,并且每朵云都有一个价值,但是商店的老板是个很奇怪的人,他会告诉你一些云朵要搭配起来买才卖,也就是说买一朵云则与这朵云有搭配的云都要买,电脑组的你觉得这礼物实在是太新奇了,但是你的钱是有限的,所以你肯定是想用现有的钱买到尽量多价值的云。
输入格式
第一行输入三个整数,n,m,wn,m,w,表示有 nn 朵云,mm 个搭配和你现有的钱的数目。
第二行至 n 1n 1 行,每行有两个整数, c_i,d_ici,di,表示第 ii 朵云的价钱和价值。
第 n 2n 2 至 n 1 mn 1 m 行 ,每行有两个整数 u_i,v_iui,vi。表示买第 u_iui 朵云就必须买第 v_ivi 朵云,同理,如果买第 v_ivi 朵就必须买第 u_iui 朵。
输出格式
一行,表示可以获得的最大价值。
输入输出样例
输入 #1
5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2
输出 #1
1
-
#include<bits/stdc .h>
-
using namespace std;
-
int c[1000010],d[1000010],suma[1000010],sumb[1000010],v[1000010];
-
const int N=1000005; //指定并查集所能包含元素的个数(由题意决定)
-
int pre[N]; //存储每个结点的前驱结点
-
void init(int n) //初始化函数,对录入的 n个结点进行初始化
-
{
-
for(int i = 1; i <= n; i )
-
pre[i] = i; //每个结点的上级都是自己
-
}
-
-
int find(int x) //改进查找算法:完成路径压缩,将 x的上级直接变为根结点,那么树的高度就会大大降低
-
{
-
if(pre[x] == x) return x; //递归出口:x的上级为 x本身,即 x为根结点
-
return pre[x] = find(pre[x]); //此代码相当于先找到根结点 rootx,然后 pre[x]=rootx
-
}
-
-
void join(int x,int y) //合并x和y
-
{
-
int fx=find(x), fy=find(y); //寻找x和y的代表元
-
if(fx != fy) //如果不一样
-
pre[fx]=fy;
-
c[fy] =c[fx]; //累加起来
-
d[fy] =d[fx]; //任意选一个作为代表元
-
}
-
-
-
int main()
-
{
-
int n,m,w,x,y;
-
cin>>n>>m>>w;
-
init(n);
-
for(int i=1;i<=n;i ){
-
cin>>c[i]>>d[i];
-
}
-
for(int i=1;i<=m;i ){
-
cin>>x>>y;
-
join(x,y);
-
}
-
for(int i=1;i<=n;i ){
-
if(find(i)==i)
-
for(int j=w;j>=c[i];j--)
-
v[j]=max(v[j],v[j-c[i]] d[i]);
-
}
-
cout<<v[w];
-
return 0;
-
}
这篇好文章是转载于:学新通技术网
- 版权申明: 本站部分内容来自互联网,仅供学习及演示用,请勿用于商业和其他非法用途。如果侵犯了您的权益请与我们联系,请提供相关证据及您的身份证明,我们将在收到邮件后48小时内删除。
- 本站站名: 学新通技术网
- 本文地址: /boutique/detail/tanhgggffh
系列文章
更多
-
photoshop保存的图片太大微信发不了怎么办
PHP中文网 06-15 -
《学习通》视频自动暂停处理方法
HelloWorld317 07-05 -
Android 11 保存文件到外部存储,并分享文件
Luke 10-12 -
word里面弄一个表格后上面的标题会跑到下面怎么办
PHP中文网 06-20 -
photoshop扩展功能面板显示灰色怎么办
PHP中文网 06-14 -
微信公众号没有声音提示怎么办
PHP中文网 03-31 -
excel下划线不显示怎么办
PHP中文网 06-23 -
excel打印预览压线压字怎么办
PHP中文网 06-22 -
TikTok加速器哪个好免费的TK加速器推荐
TK小达人 10-01 -
怎样阻止微信小程序自动打开
PHP中文网 06-13