20182319 2019-2020-1 《数据结构与面向对象程序设计》实验八报告

@
课程：《程序设计与数据结构》
班级： 1823
姓名： 彭淼迪
学号：20182319
实验教师：王志强
实验日期：2019年11月7日
必修/选修： 必修

1.实验内容

• 参考教材PP16.1,完成链树LinkedBinaryTree的实现（getRight,contains,toString,preorder,postorder）
  用JUnit或自己编写驱动类对自己实现的LinkedBinaryTree进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息
  课下把代码推送到代码托管平台

• 基于LinkedBinaryTree，实现基于（中序，先序）序列构造唯一一棵二?树的功能，比如给出中序HDIBEMJNAFCKGL和后序ABDHIEJMNCFGKL,构造出附图中的树
  用JUnit或自己编写驱动类对自己实现的功能进行测试，提交测试代码运行截图，要全屏，包含自己的学号信息
  课下把代码推送到代码托管平台

• 自己设计并实现一颗决策树
  提交测试代码运行截图，要全屏，包含自己的学号信息
  课下把代码推送到代码托管平台

• 输入中缀表达式，使用树将中缀表达式转换为后缀表达式，并输出后缀表达式和计算结果（如果没有用树，正常评分。如果用到了树，即使有小的问题，也酌情给满分）
  提交测试代码运行截图，要全屏，包含自己的学号信息

2. 实验过程及结果

这一次主要学习的是一些关于树的知识，首先学习的是LinkedBinaryTree，然后是决策树，接着又对中缀表达式的知识进行了一些了解。

实验一：

• LinkedBinaryTree，即我们一般说的二叉树的链式实现形式，对于一个普通的二叉树就是把一些数直接分成左右两边放进去就好了。然后再加上一点什么别的方法实现，算是比较常规的操作吧。
  

实验二

其实关于这个实验，我们上课的时候也已经讲过了，我们可以利用先序来确定一下根是什么，然后再利用这个根来在中序中找到什么是左子树的东西，什么是右子树的东西，然后再递归一下就可以了。

实验三

对于这个决策树，我想设计的是一个类似于二分查找的游戏。

实验四：

这个比较适合用栈来做。

3. 实验过程中遇到的问题和解决过程

• 问题1：书上用到了一些数组迭代器，但我们在使用的时候发现库里是没有add这个方法的。
• 问题1解决方案：对于这个问题，我的想法是，如果我们不能直接用它的话，那么如果我们还是要用到它的话就得用别的办法来实现，首先，我认为可以自己帮它写一个来补充那个库，当然，这个难度或许稍微有点大，于是，有了第二个方法，就是我们可以用别的东西来代替这个迭代器，比如我在这里使用的就是链表来代替它。
  
• 问题2：在实验的过程中我需要用到一些substring的方法，因为其中我的分割不是特别的规整，所以我用的时候特别容易越界。
• 问题2解决方案：在加了一些中间过程输出代码之后经过仔细的比对，发现一共有两种可能的情况会导致这种地赴越界，一个是我没有计算好这个结束所以这个直接越界了，另一个是我没有分割好上一个，于是在下一个的时候因为没有匹配的元素而间接越界。于是，重新分析，再次计算解决了一部分问题，剩下的靠一点一点试出来了。

原文：https://www.cnblogs.com/ydfy/p/11877390.html