1.本周学习总结（0--2分）
1.思维导图
2.谈谈你对树结构的认识及学习体会。
-
本周学习了树和二叉树这一结构，对于之前的结构来说，我觉得难了很多，首先这个结构有孩子结点，兄弟结点，双亲结点等， 首先从创建树的结构来说就复杂了很多，在对树的很多操作中用到了很多递归的算法，这对于本来之前递归算法就不太理解的我来说挺难的，而且一旦程序写错了，递归算法很不容易发现错误，所以在写树的相关程序的时候，最重要的我觉得还是整个思路的问题，有些递归算法不太容易想出来，而一旦想出来问题就变得简单很多了。
-
二叉树有先序，中序，后序遍历等遍历树的方法，其中还有相关的转换，这个问题感觉很难，理解三种的转化还挺容易，但是代码的实现特别难写...感觉要看好多好多遍才能记住...总结就是这章的知识点挺多的
2.PTA实验作业（6分）
2.1 6-4 jmu-ds-表达式树 (25 分)
2.1.1设计思路（伪代码）
void InitExpTree(BTree &T,string str) //建表达式的二叉树
{
定义一个栈s存放数字
定义一个栈op 存放运算符
‘#’进op栈；
while遍历str 给树结点赋值
{
If str[i]为数字
{
新建树结点T=new BiTNode;
T->data=str[i++]；T的左右孩子都置为空
T入s栈;
}
else是运算符
{
switch调用precede函数比较op栈顶和str[i]
{
case'<'：str[i++]入栈op
case'='：op栈出栈
case'>'：
新建结点T，T->data=op.top()
T->rchild=s.top();s栈出栈
T->lchild=s.top();s栈出栈
新建的T结点入s栈
op栈出栈
}
}
while(op栈顶元素不是'#') //把树结点的关系连起来
{
新建结点T;
T->data=op.top();op栈出栈
T->rchild=s.top(); s栈出栈
T->lchild=s.top()；s栈出栈
T结点进s栈
}
}
double EvaluateExTree(BTree T)计算表达式树
{
定义a，b
if 树T不空
if 左右孩子都为空 return T->data-'0';
a=EvaluateExTree(T->lchild)
b=EvaluateExTree(T->rchild)
switch T->data
case'+'：return a+b
case'-'：rerurn a-b
case'*'：return a*b
case '/'：
if b==0 输出divide 0 error!
else return a/b
}
2.1.2代码截图
2.1.3本题PTA提交列表说明
- Q1：这题刚开始没有什么思路，不明白具体怎样把表达式建成树
- A1：查了一下思路，主要是建两个栈s和op分别用来存放数字和运算符，遇到数字就赋给树结点T然后入s栈，遇到运算符和之前栈的题目差不多，要比较与op栈顶的符号的先后级，小于直接进op栈，大于则要先把op栈顶的运算符与s栈中元素的关系建立，然后再将T进s栈。等于直接op栈出栈，如此建立树，然后计算输出。
2.2.题目2：7-1 还原二叉树 (25 分)
2.2.1设计思路（伪代码）
#include<iostream>
#include<stdio.h>
#include<string>
using namespace std;
定义字符型数组 str1[110],str2[110];
int main()
{
int n;
输入结点个数n;
输出str1 str2;
输出二叉树高度
return 0;
}
int dfs(char a[],char b[],int m)
{
if m==0
return 0;//没有节点，为空树
end if
int i;
for i=0 to i<m
{
if b[i]==a[0] //找到根节点在中序的位置
break;
}
end for
int c=dfs(a+1,b,i)+1;//左子树的深度
int d=dfs(a+i+1,b+i+1,m-i-1)+1;//右子树的深度
int h;
if c>d
h=c++;
else
h=d++;
return h;
}
2.2.2代码截图（注意，截图，截图，截图。不要粘贴博客上。）
2.2.3本题PTA提交列表说明。
- Q1：这题的主要问题就是思路上还原二叉树厅容易，但是在代码实现上不是很容易想到，运用了递归算法
- A1：主要还是对递归算法不是很熟悉，先找到树根，中序序列的树根前面的字符串是其左子树，后面是右子树。再将左子树和右子树的序列分别作为一棵树进入递归，对其重复找出树根和左右子树的处理，每次记录下当前左右子树的深度，最后返回最大深度
2.3.题目3：7-5 jmu-ds-输出二叉树每层节点 (22 分)
2.3.1设计思路（伪代码）
main函数和建树函数CreatTree(string str, int &i)
void LevelOrder(BinTree BT) //层次遍历
{
定义BinTree型队列qt;
int level,flag;
定义BinTree结构体curNode,lastNode;
curNode=lastNode=BT;
if BT==NULL
输出NULL
return ;
else
BT进队
while(队qt不为空)
{
if curNode==lastNode
{
level++;
用flag控制换行
lastNode=qt.back();
}
end if
curNode=qt.front();
输出curNode->Data
if curNode->Left不为空
curNode->Left进队qt
if curNode->Right非空
curNode->Right进队qt
qt队出队
}
}
2.3.2代码截图（注意，截图，截图，截图。不要粘贴博客上。）
2.3.3本题PTA提交列表说明。
- 实际上是二叉树的层次遍历，先将根结点A入队，然后出队，访问A，将A的左右孩子BC入队，出队，然后再访问BC的左右孩子，按照以上方法，入队，出队，访问并将他的左右孩子入队，直到队列为空。
3、阅读代码（-2--2分）
3.1 题目寻找重复的子树
给定一棵二叉树，返回所有重复的子树。对于同一类的重复子树，你只需要返回其中任意一棵的根结点即可。
两棵树重复是指它们具有相同的结构以及相同的结点值
下面是两个重复的子树：
3.2 解题思路
通过map记录每颗子树先序遍历或者后序遍历的结果， 找到所有遍历结果相同的子树。
3.3 代码截图
3.4 学习体会
- 这题的话还是用到的递归算法，还有hash数组，同时结构不同的子树单纯的后序或是先序遍历可能结果一样，可以做一下特殊处理，即空树的遍历结果为某个特殊字符，这样一颗树的遍历结果就被唯一限定了
- 看了挺多力扣上的题，大部分其实都用到很巧妙的递归算法，代码很简练，所以在递归上的思路和理解运用上还要多多练习。