学号 20182315 《数据结构与面向对象程序设计》第九周学习总结

教材学习内容总结

树的遍历：

（1）先序遍历：先访问根，再访问左右子树。

（2）中序便利：先遍历左子树，再访问根节点，再访问右子树。

（3）后序遍历：先便利左子树，再遍历右子树，最后遍历根节点。

三种遍历方式用递归方式实现代码相差不大，在存放数字时存在细微差别。

if(temp==null) return; System.out.print(temp.element+" "); diqian(temp.left); diqian(temp.right);
if(temp==null) return; diqian(temp.left); System.out.print(temp.element+" "); diqian(temp.right);
if(temp==null) return; diqian(temp.left); System.out.print(temp.element+" "); diqian(temp.right);

树的实现：

（1）数组实现：将数据放置于数组中，用数组下标定义数据的先后，用数组将树的理想构图逻辑化。比如：根节点存放于下标为n的位置，左子树在（2n+1）的位置，右子树在（2*（n+1））的位置。缺点是对空间略有浪费。

（2）链表实现：建立一个节点链表，将每个节点设立左节点和右节点，在构造树时，声明左子树，右子树的节点进行连接。要找某个节点时，也可以用a.next来寻找，以a.next!=null来作为循环结束的的条件。

决策树：决策树构造方法很简单，只需存入你想输出的字符串，在树类构造方法里多设置几个构造方法来设置，通过调用不同的构造方法来实现节点的定义，左子树或右子树的建立，左右子树都有的建立。但作用极大，在以后的app建设中必然会用到决策树来寻找最适合的答案。

二叉查找树：即用循环寻找要找的元素，原理简单，注意：二叉树有一共同特点，即先确定左子树，再确定右函数。
二叉树删除：删除要分三种情况

（1）删除叶子结点：直接找到到删除的节点的父节点，使父节点的相应左右子树等于null。
用子节点代替他。

(2)删除含一个子结点的结点（左或右）：直接用子节点代替他。

（3）删除含左右两个结点的结点：此种类最为复杂，我的方案是先将树中序遍历，取待删除结点前面的一个元素，再在树中寻找这个结点。将这个结点删除，再将待删结点的值改为先前找到的值。

教材学习中的问题和解决过程

问题1：在用数组定义树的时候，进行树排序的时候常常会因为不知道树的结点有几个字节点而陷入困境。
问题1解决办法：如果有两次子节点，就要比较两次后来我统一将比较设为比较两次，如此一来，该三角每一结点都会进行两次比较，这样固然效率可以会有损失，改良方法我会在日后学习中慢慢发现。
问题2：对于多次运用的递归方法，不明确其使用方法，及优势。
问题2解决办法：经学习，递归的思想在于将问题规模变得更小，自己调用自己，但要明确有一个结束递归的条件。在递归参数传入的时候，应谨慎设置参数变化。

代码调试中的问题和解决过程

问题1：在代码实际编写过程中，我发现结点的父节点难以确定。
问题1解决办法：后来我在查找过程中加了一行代码，将结点的前一个节点记录下来，每次都会记录，这样就解决了问题。

但后来我发现无法确定使左边来的还是右边来的，于是我就加入一个判断语句。通过r3的值来选择。

问题2：在方法中，我将要进行操作的结点作为形参放入方法中（以 node T为例），然后对T.left进行操作，但是我返回到主程序后，发现主函数的树并没有发生变化。
问题2解决办法：
第一步：通过调试我发现在方法里，树的确变化了，证明错误不在我的代码思路上。
第二步：经过我的实验发现，若直接对结点T进行操作，主程序里的树是可以变化的。因此，我意识到只有对形参本身进行操作，才会将操作保存到主程序中，若用形参去调用其他方法，这个变化不会保存。

只有这样才能将改变保存到主程序。

问题3：
问题3解决办法：此处二者不能直接赋值，查找原因之后发现发现，temp.element的类型为object型的

代码托管

上周考试错题总结

In a array-based implementation of a queue that stores the front of the queue at index 0 in the array, the dequeue operation is ___________________.

A
.
impossible to implement

B
.
has several special cases

C
.
O(n)

D
.
O(n2)

E
.
none of the above

解析：在应用了删除操作之后，需要线性时间将队列的所有元素向下移动一个索引。

结对及互评

基于评分标准，我给本博客打分：13分。得分情况如下：

正确使用Markdown语法加1分：
模板中的要素齐全加1分
教材学习中的问题和解决过程, （加4分）
代码调试中的问题和解决过程, （加2分）
周五前发博客的加1分
进度条中记录学习时间与改进情况的加1分
错题学习深入的加1分
结对学习情况真实可信的加1分
感想，体会不假大空的加1分

点评过的同学博客和代码

本周结对学习情况
- 20182323

其他（感悟、思考等，可选）

二叉树的学习，更多在于思考如何将理想化为现实。如果没有思路，可以先把树画出来，把要进行的操作写出来，这样就使思路更清晰。

学习进度条

目标	5000行	30篇	400小时
第一周	200/200	2/2	20/20
第二周	300/500	2/4	18/38
第三周	500/1000	3/7	22/60
第四周	300/1300	2/9	30/90
第五周	500/1000	3/7	22/60
第六周	700/1300	2/9	22/90
第七周	1300/1000	3/7	30/60
第八周	1200/1500	3/7	30/60
第九周	1000/1500	3/7	30/60

计划学习时间:20小时
实际学习时间:22小时

节点

20182315邹家伟第九周学习总结