20162315 2017-2018-1 《程序设计与数据结构》第7周学习总结

教材学习内容总结

本周学习了教材第十六章，关于树的内容。

• 树：由一组结点及一组边构成，结点用来保存元素，边表示结点之间的联系。树是非线性结构。
• 结点的分类：父结点，子结点，兄弟结点，根节点，叶结点，内部结点。
• 树的其他元素：高度（深度），度，层。
• 遍历树的四种方法：先序遍历，中序遍历，后序遍历，层序遍历。
• 二叉树上第i层上的结点数目最多为2^（i-1）(i>=1)
• 深度为k的二叉树至多有2^k-1个结点（i>=1）
• 包含n个结点的二叉树的高度至少为log2（n+1）
  -在任意一棵二叉树中，若终端结点的个数为n0，度为2的结点数为n2，则n0=n2+1.

• 除了知道先后序树的表达式，其他两两组合可以确定一个树。

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

• 问题1：在课本中和上课提到的用中先序表达式确定二叉树，中后序表达式确定是二叉树的方法不是很熟练。
• 问题1解决方案：在下课之后多看了几个，总结出来的经验是：先序和后序表达式可以找出根节点，然后在中序表达式中通过根节点的位置将表达式断为两个部分，即二叉树的左右子节点的部分，然后用同样的方法进行递归操作。
• 问题2：继上个问题，为什么先序和后序表达式不能确定一个二叉树？

• 问题2解决方案：下课后我自己又尝试了几个练习，参阅了网上的类似的问题的答案后有了自己的想法：先序和后序放到一起只能找到父结点，而不能在中序表达式中通过父结点的位置把子结点分离，所以没办法确定一个二叉树。

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

• 问题1：上星期没发现ArrayStack中的pop方法存在问题，导致测试中只有peek方法（因为这个测试中不涉及pop操作）测试成功。
• 问题1解决方案：跟袁逸灏交流后我发现在这个方法里我在输出出栈的那个元素的时候错误地将倒数第一个元素输出成了初始容量减一位置的元素（初始容量为10，假如我只输入了4个元素那么pop方法得到的元素为空），修改后我利用表示size的公有的变量count达到了目的。

本周结对学习情况

• • 结对学习内容
    • 在数组实现栈中，我们讨论了关于pop方法的实现问题，感谢袁逸灏同学的帮助让我发现我错误地调用了容量这个变量（实际上应该调用数组当前长度）。我更加重视了数组的容量与当前长度的区别。

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

这周我充分认识到了单元测试，单步追踪的重要性。一个方法的一个变量写错了，可能导致单元测试中多个测试不通过。自己无法判断和修改的错误一定要及时请教。

学习进度条

	代码行数（新增/累积）	博客量（新增/累积）	学习时间（新增/累积）
目标	5000行	30篇	400小时
第一周	66/200	1/1	6/10
第二三周	370/400	1/2	12/18
第四五周	400/800	1/3	24/42
第六七周	800/1600	2/5	36/54