DS博客作业05--树
1.本周学习总结
1.思维导图
2.谈谈你对树结构的认识及学习体会
树就是非线性数据结构
我觉得最难得还是对于递归的理解与应用吧，同样的一个目标比如，遍历树，如果用非递归来做的话
代码量很多但是如果用递归的方法来计算的话，就只需短短几行。递归的确具有很高的简洁与高效性。
2.PTA实验作业
2.1题目1：6-4 jmu-ds-表达式树
输入一行中缀表达式，转换一颗二叉表达式树，并求解.
表达式只包含+，-，*，/，（，）运算符，操作数只有一位，且为整数(有兴趣同学可以考虑负数小数，两位数做法)。按照先括号，再乘除，后加减的规则构造二叉树。
转换二叉树如下：
2.1.1设计思路（伪代码）
建表达式二叉树
建op栈，op.push('#')
初始化根节点栈：stacktree栈
while(表达式未结束)
if(ch==操作数)
then 生成一个只有根结点的子树T stacktree.push(T)
if(ch==运算符)
then
while(ch<op栈顶运算符) 栈顶优先级高，则
创建一个树结点T，数据为op.top()
stacktree弹出2个根结点T1，T2
T->lchild=T1,T->rchild=T2
stacktree.push(T)
if(ch>op顶运算符） op.push(ch)
if(ch==op顶运算符） 则op.pop()
计算表达式树
double sum=0
if(T不为空）
then
if(左右子树不为空）
then 返回对应数值
递归左右子树得到a,b
switch(结点值）
case +：计算并返回a+b
case - : 计算并返回a-b
case * : 计算并返回a*b
case / :
if(除数为0）
then 直接输出错误并退出
else 计算并返回a/b
2.1.2代码截图
2.1.3本题PTA提交列表说明
Q:没有考虑括号两个括号相遇时要出栈
2.2题目1:修理牧场
农夫要修理牧场的一段栅栏，他测量了栅栏，发现需要N块木头，每块木头长度为整数Li个长度单位，于是他购买了一条很长的、能锯成N块的木头，即该木头的长度是Li的总和。
但是农夫自己没有锯子，请人锯木的酬金跟这段木头的长度成正比。为简单起见，不妨就设酬金等于所锯木头的长度。例如，要将长度为20的木头锯成长度为8、7和5的三段，第一次
锯木头花费20，将木头锯成12和8；第二次锯木头花费12，将长度为12的木头锯成7和5，总花费为32。如果第一次将木头锯成15和5，则第二次锯木头花费15，总花费为35（大于32）。
请编写程序帮助农夫计算将木头锯成N块的最少花费。
2.2.1设计思路（伪代码）
定义n和一个降序的优先队列q
定义长度为n的数组a，以及int型的变量 wpl=0
输入n
输入n个数，赋给数组a，以及进队q
while 队列的长度大于1
定义min=取队顶，出队列
定义pmin=取队顶，出队列
将两个值相加，再进队
wpl+=min+pmin
end while
输出wpl
2.2.2代码截图
2.2.3本题PTA提交列表说明
Q：考虑q.size()的范围时出错，导致结果错了
2.3.题目1:6-2 中序输出度为1的结点
本题要求实现一个函数，按照中序遍历的顺序输出给定二叉树中度为1的结点。
2.3.1设计思路（伪代码）
if BT结点为空，返回
ifBT结点不空
递归遍历左孩子
判断度是否为1//左孩子空右孩子不空或左孩子不空右孩子空
是 输出
不是 end if
递归遍历右孩子
end if
2.3.2代码截图
2.3.3本题PTA提交列表说明
这题其实没什么大问题，就是学了c++会容易遗忘以前c的注意点，然后再编译器里疯狂找错误
3.阅读代码
3.1 题目
给出一串数字，然后判断是不是先增后减
3.2 解题思路
两个变量交替，flag判断开始是否是上升，如果不是，那么就不成立，
up=1代表现在是上升区段，反之，递减区段，ans记录段数
3.3 代码截图
3.4 学习体
巧妙运用flag来控制增减，然后用if来做比较