DS博客作业05--树
目录
1.本周学习总结
1.1思维导图
SRE实战 互联网时代守护先锋，助力企业售后服务体系运筹帷幄！一键直达领取阿里云限量特价优惠。
1.2谈谈你对树结构的认识及学习体会
树结构还是很有意思的，因为以前总是要写很多代码，现在到了树的结构，大多数都是直接用递归，代码量少（个别题目除外）。其实最主要的就是二叉树，不管是树还是森林，都可以转换成二叉树，在这个基础上进行操作，其中印象最深的的就是目录树了，虽然说操作起来有点麻烦，但是看到最终的结果还是十分有成就感的。但是结合之前知识点的题目又有点力不足的感觉，例如表达式树，究其原因应该是没有复习的锅了。树在生活中还是很多的，不仅仅是方便查找和存储数据，同时其中的哈夫曼树又可以用于数据的加密，涉及到一点密码学的内容，真的是很有意思了。
2.PTA实验作业
2.1.题目1：朋友圈
某学校有N个学生，形成M个俱乐部。每个俱乐部里的学生有着一定相似的兴趣爱好，形成一个朋友圈。一个学生可以同时属于若干个不同的俱乐部。根据“我的朋友的朋友也是我的朋友”这个推论可以得出，如果A和B是朋友，且B和C是朋友，则A和C也是朋友。请编写程序计算最大朋友圈中有多少人。
输入格式：
输入的第一行包含两个正整数N（≤30000）和M（≤1000），分别代表学校的学生总数和俱乐部的个数。后面的M行每行按以下格式给出1个俱乐部的信息，其中学生从1~N编号：第i个俱乐部的人数Mi（空格）学生1（空格）学生2 … 学生Mi
输出格式：
输出给出一个整数，表示在最大朋友圈中有多少人。
2.1.1设计思路
//对于每个朋友圈，我们设立一个boss，代表这个朋友圈的头头
//并且设立一个全局数组用来存储每个人对应的boss信息
//我们想得到的结果是朋友圈中所有人的boss是同一个人
全局变量：circle数组//用于存储boss信息
find函数：int x //这是传参，下同，函数功能是查找x的boss
查找x在circle中的boss，如果x本身就是一个boss，返回x；
如果不是，继续递归find(circle[x])，一级一级地找x的最终boss，并将boss的值返回，赋予circle[x]
//将返回的boss的值赋予circle[x]很重要，因为所有圈中的boss可能合并导致boss改变
返回x的boss
unit函数：int person1,int person2//功能：联合person1和person2所在的朋友圈
find函数查找person1的boss
find函数查找person2的boss
如果两人的boss不相同，就让person2的boss做person1的boss的小弟
//也就是令person2的boss在数组中对应的值为person1的boss
main函数：
cin >> m,n
根据m对circle数组初始化
while(n--)//读入朋友圈
读取第一个人bigBoss作为这个朋友圈的boss
读入剩下的所有人，并用unit函数将他们联合为一个朋友圈
//在未联合之前，每个人都是自己的boss
static int result[]//统计每个boss小弟人数
int max = 0//最大值
for i = 1 to m:
int b = i 的boss
result[b]++
if result[b] > max:
max=result
cout << max
题外话：其实这道题我在树的PTA里面是没有写的，因为我以为考试后题组还会开放。。就只记了思路，并未实践
。不过我在固定题目集里面找到了这道题，并用下面的代码成功通过。
2.1.2代码截图
2.1.3本题PTA提交列表说明
WA：第一次提交出错是因为我在unit函数中令person2的boss等于person1，而未对两者的boss进行操作。导致这两个小弟谜之叛变。。。。
2.2.题目2：修理牧场
2.2.1设计思路
这道题目其实就是个阉割版的哈夫曼树生成，因为你不需要最后的树结构，所以这道题目其实可以只用一个数组解决
main函数：
int wood数组
for i = 1 to n:
读入每根木头的长度
sort函数对wood数组进行快速排序//毕竟C++有，就直接用了。不然冒泡半天
for i = 0 to n-2:
将wood[i]和wood[i+1]相加得到和plus
sum += plus //sum为总消费
将和按照升序插入到后面的数组中//本想着这里也用sort但是后面实验了发现会超时
cout << sum
2.2.2代码截图
2.2.3本题PTA提交列表说明
2.3.题目3：家谱处理
人类学研究对于家族很感兴趣，于是研究人员搜集了一些家族的家谱进行研究。实验中，使用计算机处理家谱。为了实现这个目的，研究人员将家谱转换为文本文件。下面为家谱文本文件的实例：
John
Robert
Frank
Andrew
Nancy
David家谱文本文件中，每一行包含一个人的名字。第一行中的名字是这个家族最早的祖先。家谱仅包含最早祖先的后代，而他们的丈夫或妻子不出现在家谱中。每个人的子女比父母多缩进2个空格。以上述家谱文本文件为例，John这个家族最早的祖先，他有两个子女Robert和Nancy，Robert有两个子女Frank和Andrew，Nancy只有一个子女David。在实验中，研究人员还收集了家庭文件，并提取了家谱中有关两个人关系的陈述语句。下面为家谱中关系的陈述语句实例：
John is the parent of Robert
Robert is a sibling of Nancy
David is a descendant of Robert研究人员需要判断每个陈述语句是真还是假，请编写程序帮助研究人员判断。
输入格式：
输入首先给出2个正整数N（2≤N≤100）和M（≤100），其中N为家谱中名字的数量，M为家谱中陈述语句的数量，输入的每行不超过70个字符。名字的字符串由不超过10个英文字母组成。在家谱中的第一行给出的名字前没有缩进空格。家谱中的其他名字至少缩进2个空格，即他们是家谱中最早祖先（第一行给出的名字）的后代，且如果家谱中一个名字前缩进k个空格，则下一行中名字至多缩进k+2个空格。在一个家谱中同样的名字不会出现两次，且家谱中没有出现的名字不会出现在陈述语句中。每句陈述语句格式如下，其中X和Y为家谱中的不同名字：
X is a child of Y
X is the parent of Y
X is a sibling of Y
X is a descendant of Y
X is an ancestor of Y输出格式：
对于测试用例中的每句陈述语句，在一行中输出True，如果陈述为真，或False，如果陈述为假。
2.3.1设计思路
这题同样也是在固定题目集过的
cin不能读入空格，所以这里得用getline，还有就是存储在map的时候是不能带空格的，然后string没有trim这样的去空格函数，所以就只好自己写一个
//读取人物关系信息
map<string, string> relation
stack<string> family
while(1)
读取一个人名name
if 空栈:
直接入栈
continue
if 栈顶是 name的父亲：
relation[name] = 栈顶//建立关系
入栈name
else
不断退栈直到栈顶是name的父亲
relation[name] = 栈顶
入栈name//解决输入的问题，采用递归
solve函数：string name1,name2,re//re是关系
switch(re[0])
case c:判断name2是否是name1的父亲，返回判断结果//判断是不是儿子
case p:同上//判断是不是父母
case s:同上//判断是不是兄弟
case a:GrandSearch(name1,name2,re)//判断是不是祖先
case d:GrandSearch(name2,name1,re)//判断是不是祖孙
GrandSearch函数：
if name1是唯一的祖先：
return false
if name1的父亲是name2：
return true
else return GrandSearch(name1的父亲，name2)//递归函数不好讲，，就是不断找name1的父亲，直到找不到或者name1的父亲就是name2为止
2.3.2代码截图
2.3.3本题PTA提交列表说明
WA：之所以一直过不去是因为我以为每一行的空格与下一行的空格相差只有2，0，-2，所以没有用if包括进去，其实不止，还可能是任何负偶数，如下面的David和上一行的Nancy就差了6，修改一下if语句的条件就好辣
John
Robert
Frank
Andrew
Nancy
David
3.阅读代码
3.1 题目
3.2 解题思路
3.3 代码截图
3.4 学习体会
4. 上机考试（不计分）
果然表达式树还是没掌握好啊
问题1：
讲真的我也不知道自己怎么写出这东西来的，我当时就坐在那眼睁睁看着给t->data赋值‘1’，结果t->data里面的数据变成’?‘，然后心里充满了'?????????????'
问题2：
一直卡在第一个问题，所以这个错误我也没有去找，就是将两个数和一个运算符合成一棵树时忘记把运算符也出栈了。。
以上
