0202303实验8 《数据结构与面向对象程序设计》实验报告
# 20202303 2021-2022-1 《数据结构与面向对象程序设计》实验8报告
课程：《程序设计与数据结构》
班级：2023
姓名：马岚
学号：20202303
实验：王志强
实验日期：2021年11月。
强制/可选：强制
## 1.实验内容
参考教材PP16.1，完成链树LinkedBinaryTree (getright，contains，tostring，preorder，postorder)的实现
用JUnit或者自己的驱动类测试自己的LinkedBinaryTree，提交测试代码的截图，应该是全屏的，包含自己的学生证信息。
将代码推送到代码宿主平台的下一个类。
基于LinkedBinaryTree，可以基于(中间顺序，一阶)序列构造唯一二叉树。树的功能，如给出中间顺序HDIBEMJNAFCKGL和后面顺序ABDHIEJMNCFGKL，构建了附图中的树。
使用JUnit或者自己编写的驱动类测试自己实现的功能，提交测试代码截图，应该是全屏的，包含自己的学生证信息。
将代码推送到代码宿主平台的下一个类。
自己设计并实现一个决策树。
提交测试代码运行的截图，应该是全屏的，包含您自己的学生证信息。
将代码推送到代码宿主平台的下一个类。
输入中缀表达式，用树将中缀表达式转换为后缀表达式，输出后缀表达式和计算结果(如果不用树，正常打分。如果用树，即使有小问题，酌情满分)
提交测试代码运行的截图，应该是全屏的，包含您自己的学生证信息。
## 2.实验过程和结果
(1)参考教材PP16.1，完成链树LinkedBinaryTree (getright，contains，tostring，preorder，postorder)的实现。
用JUnit或者自己的驱动类测试自己的LinkedBinaryTree，提交测试代码的截图，应该是全屏的，包含自己的学生证信息。
将代码推送到代码宿主平台的下一个类。
根据类中现有的方法完成剩余的方法。例如，getRight可以指getLeft，preorder，postorder可以指order。剩下的包含，isEmpty可以通过调用BTNode中的方法来完成。
接下来是考试代码的通过(学生证考试):
(2)基于LinkedBinaryTree，实现基于(中间顺序，一阶)序列的唯一二叉树的构建。树的功能，如给出中间顺序HDIBEMJNAFCKGL和后面顺序ABDHIEJMNCFGKL，构建了附图中的树。
用JUnit或者自己编写的驱动类测试自己实现的功能，提交测试代码截图，应该是全屏的，包含自己的学生证字母。
将代码推送到代码宿主平台的下一个类。
该程序的基本原理是，通过知道优先级和中间优先级、中间优先级和后优先级，可以建立唯一的二叉树。然而，无法确定已知的前序和后序，因为左右子树可能不同。构造的基本思想：先序序列的第一个节点必须是根节点，所以先在先序序列中找到同一个根节点，并将其分为左右子树。然后，采取类似的步骤。顺序序列的第二个元素是左子树的第一个节点，然后在顺序序列中以它为中心划分左子树和右子树，以此类推。在构造了左边的整个子树之后，用同样的原理构造右边的子树。
代码：
公共BTNode构造(char[] pre，char[]in){ 0
if(pre . length==0 | | in . length==0){ 0
返回null
}
BTNodeCharacter树=新的BTNodeCharacter(pre[0])；
int index=search(0，in.length，in，tree . GetElement())；
tree . set left(construct(arrays . copy ofrange(pre，1，index 1)，Arrays.copyOfRange(in，0，index)))；
tree.setRight(构造(Arrays.copyOfRange(pre，index 1，pre.length)，
Arrays.copyOfRange(in，index 1，in . length))；
返回树；
}
public int search(int start，int end，char[] inOrders，char data){ 0
for(int I=start；我结束了；I){ 0
if(数据==inOrder
s[i]) {
return i;
}
}
return -1;
}
(3)自己设计并实现一颗决策树
- 提交测试代码运行截图，要全屏，包含自己的学号信息
- 课下把代码推送到代码托管平台
测试代码：
（4）输入中缀表达式，使用树将中缀表达式转换为后缀表达式，并输出后缀表达式和计算结果（如果没有用树，正常评分。如果用到了树，即使有小的问题，也酌情给满分）
- 提交测试代码运行截图，要全屏，包含自己的学号信息
先通过中缀表达式构建出一棵树，然后以后序遍历这棵树，得到的就是后缀表达式
## 3. 实验过程中遇到的问题和解决过程
- 问题1：在程序编写中，IDEA证书过期了，真的无语。。。。。
- 问题1解决方案：利用现代网络的发达技术，终于换成了无限循环式使用，怒赞网络这个宽阔的平台。
- 问题2：在编写过程中，教材代码中的ArrayIterator类无法识别
- 问题2解决方案：通过网络搜索以及搜索，发现把这个方法的定义类型为ArrayList就可以啦。
- 问题3：在测试过程中，发现最开始的编写与自己预期的出现顺序不一致，过不了。
- 问题3解决方案：在对象调用完方法后，再调用toString()方法，将两者结合起来，比如文上的e.inorder().toString()
## 其他
感悟：树的结构其实大部分在离散里也接触过，虽然但是，我万万没想到要把这个东西做成程序，虽然有课本，但耐不住本人脑子有限，在实践方面还差缺火候，尤其是在许多方法补充的方面，特别吃力，而且写出来也其实没咋记住和理解，尤其是递归算法，要了老命了，还是希望下次难度低一点，我会之后努力实践，然后继续加油！
## 参考资料
- 《Java程序设计教程（第九版）》
- 《Java软件结构与数据结构（第四版）》
- 网页搜索资料：https://blog.csdn.net/qq_26219679/article/details/79647221
- 网页搜索资料：https://blog.csdn.net/weixin_30384217/article/details/99115000
- 云班课：https://www.cnblogs.com/rocedu/p/6371262.html
内容来源网络，如有侵权，联系删除，本文地址：https://www.230890.com/zhan/121793.html
