1.学习总结
1.1树结构思维导图
1.2 树结构学习体会
- 总的来说，树这章的内容比较多，先是介绍树的概念，然后通过树转化成二叉树，重点是对二叉树的学习。
- 二叉树首先是学习二叉树的建立，二叉树建立有层次建树，前中序建树，后中序建树；遍历有层次遍历，先序遍历，中序遍历，后序遍历，而遍历有递归和非递归两种方式
- 因为学习内容较多，加之假期的放松，导致对树的掌握并不是很好，只能利用课余时间把没能及时掌握的知识吃透。
2.PTA实验作业
题目1：求二叉树高度
设计思路
求树高度函数{
如果BT==NULL 空树返回0 //递归出口
否则{
取BT->Left做函数参数求左子树高度赋值给m
取BT->Right做函数参数求左子树高度赋值给n
如果（m>n）返回m+1
否则返回n+1
}
}
代码截图
PTA提交列表说明。
- 本题无问题
题目二： 还原二叉树
设计思路
主函数{
输入两个字符数组
初始化树Tree
调用还原函数recover()
输出 树高度
}
recover函数{
如果树空 返回NULL;
初始化树bt
先序首个字符赋值给bt根节点
for i=0 to N{
再中序中寻找先序首字符的位置
break；
}
左子树递归法建树
右子树递归法建树
}
求高度函数{
如果树空 返回0；
l=递归计算左子树高度
r=递归计算右子树高度
返回max[l,r]
}
代码截图
PTA提交列表说明。
- 再编译器上可以运行但是答案错误，我先提交上去，得出不是答案错误，而是段错误，应该不是计算高度函数错误，于是我添加查看调试
发现前序的第一字符不是A，二是p？意识到字符数组输入后有问题，仔细看，发现数组的输入中数组第一个位置给设成1了，修改后即正确
题目三：jmu-ds-表达式树
设计思路
建表达式树函数{
建立树s栈和字符op栈
while(str[i]不为0){
如果不是操作符{
新建节点T，数据域赋值str[i]
节点T进s栈
}
否则{
判断op栈顶字符与str[i]的优先级{
小于：str[i]进栈
等于：处在栈顶字符
大于：把op的栈顶赋值给t的数据域，连续出栈s的两个栈顶作为t的左右孩子，在将T进s栈
}
}
}
while(op栈顶不是#) {
op栈顶元素赋值给T的数据域
出栈s的栈顶赋值给T的左孩子
如果(s不空) {
出栈s的栈顶赋值给T的右孩子
}
T进s栈
T=s栈顶
}
}
计算表达式树函数{
如果(左右子树均不空){
把T->data转换成数字
}
a，b分别用由T的左右子树用递归法算出
判断{
+：返回a+b
-：返回a-b
*：返回a*b
/；{
如果b<1：直接退出
否则返回：a/b
}
}
}
代码截图
PTA提交列表说明。
3.截图本周题目集的PTA最后排名
我的得分
- 155
阅读代码
树的存储结构如下：
typedef int ElemType;
typedef struct BiTNode{
ElemType data;
struct BiTNode *lchild,*rchild;
}BiTNode,*BiTree;
复制一颗树
bool CopyTreeIsOK(BiTree p){
if(CopyTree(p)==NULL)
return false;
return true;
}
BiTree CopyTree(BiTree p){
if(!p) return NULL;
BiTree q=new BiTNode;
q->data=p->data;
q->lchild=CopyTree(p->lchild);
q->rchild=CopyTree(p->rchild);
return q;
}
- 这是一个复制一颗二叉树的算法，代码中先判断树是为空，然后通过递归法分别将左右子树复制到另一颗树上，最后返回复制完的树
5. 代码Git提交记录截图
